Hash table - tenji/ks GitHub Wiki

散列表（哈希表）

散列是一种在数据结构中使用的技术，它以允许快速访问的方式有效地存储和检索数据。它涉及使用散列函数将数据映射到散列表中的特定索引，该函数可以根据其键快速检索信息。这种方法通常用于数据库、缓存系统和各种编程应用程序中，以优化搜索和检索操作。

哈希的伟大之处在于，我们平均可以在 O(1) 时间内完成所有三个操作（搜索、插入和删除）。

一、基本概念

散列是数据结构中用于有效存储和检索数据的技术。它涉及使用哈希函数将数据项映射到固定大小的数组（称为哈希表）。以下是散列的基本术语。

  • 哈希函数（Hash Function）：你将数据项提供到哈希函数中。
  • 哈希码（Hash Code）：哈希函数对数据进行处理并给出唯一的哈希码。该哈希码通常是可用作索引的整数值。
  • 哈希表（Hash Table）：哈希码会指向哈希表中的特定位置。

散列表可以理解为二维数组吗？

哈希表可以理解为一维数组，因为只是单一的坐标。当然如果考虑到哈希碰撞，理解为二维数组也无不可。

二、哈希函数（Hash Function）

哈希函数是一个接受键（Key）并返回哈希表（Hash Table）索引（Index）的函数。哈希函数的目标是在哈希表中均匀分布键，最大限度地减少冲突（当两个键映射到同一索引时）。

三、负载因子/载荷因子（Load Factor）

散列表的载荷因子定义为： α = 填入表中的元素个数 / 散列表的长度

α 是散列表装满程度的标志因子。由于表长是定值， α 与“填入表中的元素个数”成正比，所以， α 越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之， α 越小，标明填入表中的元素越少，产生冲突的可能性就越小。

四、哈希冲突（Hash Collision）

当两个不同的键映射到哈希表中的同一索引时，就会发生哈希冲突。即使使用良好的哈希函数，也可能会发生这种情况，特别是当哈希表已满或键相似时。

哈希冲突发生的原因是什么？

  • 糟糕的哈希函数：未在哈希表中均匀分配键的哈希函数可能会导致更多冲突；
  • 高负载因子：高负载因子（键与哈希表大小的比率）会增加冲突的可能性；
  • 相似的键：值或结构相似的键更有可能发生冲突。

如何解决哈希冲突？

  • 开放寻址（Open Addressing）：又称开放定址法，如果一个哈希表位置被占用了，就去寻找下一个可用的位置，直到找到一个空槽或者遍历整个表。这种方法避免了使用额外的数据结构（比如链表）来存储相同哈希值的键值对，而是直接在哈希表中寻找下一个可用的位置。开放寻址法需要的表长度要大于等于所需要存放的元素数量，非常适用于装载因子较小（小于0.5）的散列表。在开放寻址法中，有几种常见的探测方式，用于确定下一个位置：
    • 双重哈希（Double Hashing）
    • 线性探测（Linear Probing）
    • 二次探测（Quadratic Probing）
  • 单独链表法（Separate Chaining）：也叫拉链法，将散列到同一个存储位置的所有元素保存在一个链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。
  • 罗宾汉哈希（Robin Hood Hashing）：

五、复杂度

对于查找、插入和删除操作，哈希表的平均时间复杂度为 O(1)。然而，在最坏的情况下，这些操作可能需要 O(n) 时间，其中 n 是表中元素的数量。

最坏情况指的是什么情况？为什么最坏情况的时间复杂度是 O(n)？

假设我们使用单独链表法（Separate Chaining）解决哈希冲突。那么，最坏的情况是所有 n 个元素都位于同一索引处。这个时候，链表的查找、插入和删除操作，时间复杂度都是 O(n)。

六、哈希的应用

  • 字典：实现一个字典，以便我们可以快速搜索单词；
  • 数据库索引：散列用于数据库索引。有两种流行的方法来实现索引：搜索树（B 或 B+ 树）和散列；
  • 缓存：存储经常访问的数据以便更快地检索。例如浏览器缓存，我们可以使用 URL 作为键并查找 URL 的本地存储；
  • 符号表（Symbol Tables）：将标识符映射到编程语言中的值；
  • 网络路由：确定数据包的最佳路径。

七、Java 集合中的哈希实现

HashTable

底层数据结构

...

HashSet

LinkedHashSet

HashMap

底层数据结构

  • 1.8 以前：数组 + 单链表
  • 1.8 以后：数组 + 单链表 + 红黑树（链表长度超过 8 就转化为红黑树）

HashMap 和 HashTable 有什么区别？

  1. 线程安全：HashTable 是线程安全的，HashMap 不是线程安全的，如果需要在多线程环境中使用 HashMap，可以考虑使用 ConcurrentHashMap；
  2. 空值处理：HashTable 不允许键或值为 NULL，会抛出 NPE，而 HashMap 允许键或值为 NULL；
  3. 实现方式：HashTable 基于 哈希表 + 链表 实现，而 HashMap 基于 哈希表 实现，这种差异使得 HashMap 在大多数情况下的性能优于 HashTable；
  4. 迭代器：HashTable 的迭代器是通过 Enumeration 实现的，而 HashMap 的迭代器是通过 Iterator 实现的。Iterator 比 Enumeration 更加灵活，因此 HashMap 的迭代器可以使用更多的方法；
  5. 继承关系：HashTable 继承自 Dictionary 类，而 HashMap 继承自 AbstractMap 类。由于 Dictionary 类已经被废弃，因此 Hashtable 也不再推荐使用。‌

更多关于 HashMap，传送门

LinkedHashMap

底层数据结构

  • 1.8 以后：数组 + 双链表 + 红黑树（链表长度超过 8 就转化为红黑树）

ConcurrentHashMap

更多关于 Java 集合，传送门

∞、参考链接