K&R哈希函数

Question

以下代码部分是 K&R 的简单哈希查找算法的实现。 lookup 在 table 中搜索 s，returns 是指向找到它的位置的指针，如果不存在则为 NULL：

struct hashElement *lookup(char *name){
    struct hashElement *currentStruct;
    int cmp;
    for (currentStruct = hashTable[calcIndex(name)]; currentStruct; currentStruct = currentStruct->p)
    if (cmp = strcmp(name, currentStruct->name) == 0)
        return currentStruct;
    return NULL;}

Install使用lookup判断正在安装的名称是否已经存在：

struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL){
    np = (struct nlist *) malloc(sizeof(*np));
    ...}
...}

如果lookup returns为NULL，说明hash table中没有安装name ，我应该为类型为 nlist 的新元素分配内存。

但是，基于此 np = (struct nlist *) malloc(sizeof(*np)); 如果 lookup return NULL *np 将为 NULL 分配内存。我不应该总是为 nlist 而不是 *np 分配内存大小吗？

Answer 1

*np will allocate memory for NULL if lookup return NULL.

不，那不是真的。

首先，在

  np = (struct nlist *) malloc(sizeof(*np));

the cast in not needed。也就是说

 np = malloc(sizeof(*np));

与

相同

np = malloc(sizeof(struct nlist));

因为 *np 的类型是 struct nlist。请记住，sizeof 运算符不会评估它的操作数，除非它是 VLA。

引用 C11，章节 §6.5.3.4

The sizeof operator yields the size (in bytes) of its operand, which may be an expression or the parenthesized name of a type. The size is determined from the type of the operand. The result is an integer. If the type of the operand is a variable length array type, the operand is evaluated; otherwise, the operand is not evaluated and the result is an integer constant.

K&R哈希函数

K&R hash function

c

malloc

pointers

sizeof