1

这是为了采访。他们问我什么是实现自定义哈希图的好方法。

我回答说,如果你有一个 say , n ,元素的数组。

您可以将单个键映射到索引 %n 的整数。这将允许您将密钥存储在哈希图中。但是如果发生冲突,那么您可以在自定义数组中保留一个值列表。现在,像这样在自定义 hashmap 中使用列表的最坏情况是 O(n)。所以,我建议,我们可以在列表中使用 Heap(最小堆)并调用 heapify() 来平衡它。这也会产生 logn 复杂性?

我想到的另一件事是,我可以使用具有 2-3-4 个节点的树,从而降低登录复杂性。(有点像 B+ 树)

在自定义堆实现的情况下解决冲突的任何更好的想法?

4

2 回答 2

1

最常见的是通过以下方式解决 hashmap 冲突:

  1. 双端队列(PHP 是如何做到的)
  2. 链表
  3. 实际上,只需增加散列值,直到找到不是冲突的插槽。

对于第一个示例,要使用值“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 树等)会减慢数据结构的速度,而不是帮助。

在碰撞之前,您几乎绝对会耗尽存储项目的内存,并且线性搜索的缓慢成为一个限制因素。

(编辑添加:您不必[也不应该,对于大型散列函数空间]预先分配整个散列映射。也为此使用双端队列,以便它随着散列结果数量的增长而增长.)

于 2013-04-26T15:39:24.127 回答
1

按照您的建议,通常的技巧(至少,Python 和 Java 都是这样做的)是通过将动态数组或链表放入哈希桶中来解决冲突。此外,哈希表还有一个参数,称为最大负载因子,例如 2/3。当负载因子高于其允许的最大值时(表超过 2/3 满),分配一个新的哈希表,即原来的两倍大,所有数据都被移动到新的哈希表中桌子。

虽然复制可能很昂贵,但它的成本可以通过查找来摊销。

于 2013-04-26T16:33:25.270 回答