若哈希是唯一的,但哈希表中的哈希%大小相同,会发生什么情况?

1. 例如,创建阵列

   hashtable ht[4];

2. int hash = hash_key(key);

3. 获取索引

   int index = hash % 4

4. 设置为哈希表

   ht[index] = insert_or_update(value)

key1 和 key2 有相同的散列,它们指向相同的 ht[index] 所以 separate chaining 可以解决这个问题。

具有相同散列的键进入同一个存储桶,这些键将存储在链接列表中。

例如

hash(key1): 3
hash(key2): 7
hash(key3): 11
hash(key4): 15

所以索引是3,这些具有不同散列和不同密钥的密钥进入同一个bucket

例如,这些实现:

https://gist.github.com/tonious/1377667#file-hash-c-L139

http://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)HashTables.html?highlight=%28CategoryAlgorithmNotes%29#CA-552d62422da2c22f8793edef9212910aa5fe0701_156

redis: https://github.com/antirez/redis/blob/unstable/src/dict.c#L488

nginx: https://github.com/nginx/nginx/blob/master/src/core/ngx_hash.c#L34