实现哈希表

Question

我几天前开始阅读有关实现各种数据结构的文章，碰到了哈希表的一点问题。

我对哈希表的理解是：传递一个键K给哈希函数H，它会返回一个经过哈希处理的键HK。由于可能会出现冲突，HK至少应该是一个uint32_t类型。我们有一个大小为X的数组，在这个数组中，项目存储在索引HK处。但是，这是否需要预先分配长度为至少uint32_t（或H的返回值）的数组呢？假设我们不在该数组中存储数据本身，而是存储指向数据的指针，则我们需要一个长度为uint32_t的ptr_t数组。这似乎非常浪费，在64位系统上将导致内存使用量达到： 2 ^ 32 * 8 = 34359738368字节或约32GB，仅用于数据指针的数组，这显然不是实际实现的方式。

那么我错在哪里了？

- Kim Sun-wu

---

我认为典型的实现不是使用数组，而是使用链表。 - Stephan Dollberg

我认为典型的实现不是使用链表而是数组。 - max taldykin

关于碰撞，使用哈希表时会发生碰撞。它们应该被处理而不是避免。通过合理的哈希和维度可以将它们最小化。 - stefaanv

@bamboon: 实际上，你可以使用一个链表数组进行常规实现。在发生冲突的情况下不是理想的选择，并且引用之间的局部性较差，但操作的复杂度是相当可预测的。 - Matthieu M.

@MatthieuM。嗯，是的，那是个误解，我以为他在谈论第二阶段。 - Stephan Dollberg

Answer 1

它取决于具体实现。一般有三种基本方法：

1) 使用小哈希。即使用 8 位哈希代替 32 位哈希。

2) 使用多层哈希。例如，一个 12 位哈希可以确定一个条目进入哪个"桶"，但只有在完整的 32 位哈希匹配时才会发生冲突。每个桶存储在链表或类似结构中。(也许针对在其中搜索完整的 32 位哈希进行了优化。)

3) 使用稀疏数组。这些数据结构不需要为未填充的插槽实际存储空白空间。(在实践中，它可能是完全不同的东西，如树，但它的作用类似于具有高效搜索功能的稀疏数组。)

- David Schwartz

Answer 2

你应该构建可扩展的哈希表。有一些方法可以做到这一点。阅读这篇文章会很有帮助。在这个例子中，使用了一个链表。如果没有空值了，你还需要扩展你的表。你将会遇到以下问题：如果你扩展了你的映射，你的H函数可能会为旧的K键返回新的HK值。所以你必须考虑如何解决这个问题。其中一种方法是在扩展表格时重新加载所有值。如果你不经常扩展它，这是正常的。

- shift66

---

哈希表或哈希映射是一种数据结构，它使用哈希函数将标识值（称为键）映射到它们关联的值。在哈希表中有键和哈希值。你只需要为旧键计算新值。如果没有键（即只有一组哈希值），那么你为什么还需要它呢？ - shift66

我在谈论哈希集，但是Matthieu M回答了这个问题。 - Kim Sun-wu

Answer 3

实际上，您有一些较小的、固定数量的桶数组，这些桶数组使用链接（导致链表）或探测（最差的情况是：如果哈希（x）被占用，则尝试哈希（x）+1）来解决碰撞问题。在最简单的情况下，您将uint32取模并除以桶大小。

您可以定义一个负载因子 - 一旦数组中达到N％的填充率，我们将增加数组的大小，使其翻倍，并将所有内容重新哈希到新数组中。假设，在50％和75％之间的某个地方使用。

那么，你说这不是很昂贵吗？嗯，实际上并不是。假设每次将数组大小翻倍。因此，您添加N个项目，其中最后一个触发复制。 N次添加的时间复杂度为O（1），然后进行一次O（N）复制。但是请等一下 - O（N）/ N平均为O（1），因此假设您明智地选择了负载因子，则添加的平均分摊成本仍为O（1）。

- James

---

在重新散列的情况下，如果它是一个哈希集合，即您没有原始数据可用于重新散列，会发生什么？ - Kim Sun-wu

@KimSun-wu：你可以简单地将哈希值与数据一起存储，以避免重新计算它。 - Matthieu M.

@MatthieuM。即使不扩展表，存储完整的32位哈希也可以是一种有效的访问优化；在检查相等性之前，您可以比较32位哈希值。 - James Kanze

@JamesKanze：没错！我甚至没有想过这个问题（但是，我从来没有真正实现过哈希表...） - Matthieu M.

Answer 4

哈希表的典型实现是一个链表数组。链表可以很容易地被替换为另一种数据结构，因此我们将其称为Bucket。

这个想法很简单：

class HashTable {
public:


private:
  std::vector<Bucket*> _array;
};

接下来，您需要将 HK 值 缩小，以适应数组大小，通常使用取模运算：HK % size(_array) 这将给出要使用的桶的索引。

- Matthieu M.