这个哈希函数是如何工作的？这些数字是随机的吗？

我正在阅读K & R的“The C Programming Language”一书。在“结构”一章，“表查找”（第144页）的子主题下，我发现这个哈希生成函数这个哈希函数是如何工作的？这些数字是随机的吗？

#define HASHSIZE 101 

struct nlist { 
    struct nlist *next; 
    char *name; 
    char *defn; 
} 

static struct nlist *hashtab[HASHSIZE]; 

unsigned hash(char *s) 
{ 
    unsigned hashval; 

    for (hashval = 0; *s != '\0'; s++) 
     hashval = *s + 31 * hashval; 
    return hashval % HASHSIZE; 
}

我不明白的是什么这个功能实际上不会。

我认为它为给定的字符串（char * s）生成一个唯一的地址（作为hashtab的索引）。

但我认为两个不同的字符串可以被赋予相同的索引，因为（hashval％HASHSIZE）是给定的地址（203％101 = 405％101 = 1）。

为什么HASHSIZE 101和hashval乘以31？为什么不是100或32？

来源

2015-11-08 0xEDD1E

我不明白的是这个函数实际上做了什么？

它基本上散列串由char *s指针所指向，直到它遇到的字符串，该字符串由空字符'\0'标记的结束。换句话说，它计算（或地图）一个给定的输入字符串为一个整数值。

你也可以看到，它通过在字符串中通过每个字符会（即s++），使得这一功能的时间复杂度线性依赖于字符串长度--or O(N)做到这一点 - 而且，它避免了用最终模数运算生成一个超出数组范围的值。

我认为它为给定的字符串（char * s）生成一个唯一的地址（作为hashtab的索引）。

它需要的输入值（即，字符串被散列），并使用它来找出其中所述字符串应该被放置在阵列内的索引。所以在技术上不会产生地址，因为函数不会返回指针。单词偏移量在这里会更准确。

但我认为两个不同的字符串可以给予相同的索引，因为（hashval％HASHSIZE）是给定的地址（203％101 = 405％101 = 1）。

是的。这被称为冲突。编写有助于避免冲突的散列函数并不容易。在大多数讨论中，您将看到冲突解决方法以处理这些情况。

例如，一种方法可以是把每个数组元素到一个指针，其中发生了冲突的元件（即散列索引值相同）被附加到一个链表。还有其他方法，但这是一个不同的讨论。

理想的情况下，perfect hash functions将被使用，因为他们保证从未产生了两个不同投入相同的散列值，使得冲突解决不必要的。

有关于这些主题的书籍章节，主要涉及到搜索，所以您可能想要给读者一个阅读。

为什么HASHSIZE是101并且hashval乘以31（为什么不是100或32）？

由于101和31是素号码和因此不太可能落得乘以/除以自己变成同一个桶中作为先前，和不同的，串产生碰撞。

来源

2015-11-08 08:53:32 ray

散列函数通常可能为不同的字符串生成相同的散列值。这就是为什么需要collision resolution。

关于HASHSIZE和hashval的值：我不是哈希函数的专家，但在我阅读的少数人中，所使用的数字是凭经验获得的。你可以阅读answer这个主题，这可能对你有所帮助。

来源

2015-11-08 08:55:21

这个哈希函数是如何工作的？这些数字是随机的吗？

回答

相关问题