最常见的是通过以下方式解决 hashmap 冲突:
- 双端队列(PHP 是如何做到的)
- 链表
- 实际上,只需增加散列值,直到找到不是冲突的插槽。
对于第一个示例,要使用值“world”存储键“hello”,您将通过散列函数获取整数 hashmap 键(假设 C/C++ 实现):
// the following is given: that there is some object "myvalue"
// where myvalue.value = "world", and myvalue.key = "hello".
int hash_key = hash(myvalue.key); //myvalue.key = "hello", as given
然后将该值插入到索引处的双端队列元素中hash_key
:
hash_map[hash_key].push_back(myvalue);
您hash_map
的双端队列的 N 索引数组在哪里,并且myvalue
是要插入的对象(请注意,myvalue
应该将其自己的key
成员设置为“hello”,以便稍后检索)。
要在哈希映射中查找项目,您需要对键(“hello”)进行哈希处理,然后遍历双端队列直到找到该项目。如果散列函数的摘要空间足够大(例如,32 位无符号整数 = 40 亿个唯一散列结果)并且散列函数给出均匀分布,那么发生冲突的几率足够小(2 分之一 ^ 32)你的双端队列可能只有 1 或 2 个项目(即使你存储 2^33 个项目),而且更高级的结构(AVL 树、RB 树等)会减慢数据结构的速度,而不是帮助。
在碰撞之前,您几乎绝对会耗尽存储项目的内存,并且线性搜索的缓慢成为一个限制因素。
(编辑添加:您不必[也不应该,对于大型散列函数空间]预先分配整个散列映射。也为此使用双端队列,以便它随着散列结果数量的增长而增长.)