c - K&R哈希函数

Question

以下代码部分是 K&R 的简单哈希查找算法的实现。 lookup 在表中搜索 s，并返回指向找到它的位置的指针，如果不存在则返回 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;}

安装使用查找来确定正在安装的名称是否已经存在:

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

如果lookup返回NULL，则意味着哈希表中没有安装name，我应该为类型为nlist的新元素分配内存。

但是，基于此np = (struct nlist *) malloc(sizeof(*np)); *如果查找返回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.