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 回答