关于android:如何实现一个优秀的-HashTable-散列表

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。

前言

大家好，我是小彭。

在前几篇文章里，咱们聊到了 Java 中的几种线性表构造，包含 ArrayList、LinkedList、ArrayDeque 等。明天，咱们来探讨另一种罕用的根底数据结构，同时也是“面试八股文”的规范题库之一 —— 散列表（Hash Table）。

同时，在后续的文章里，咱们将以 Java 语言为例，剖析规范库中实现的散列表实现，包含 HashMap、ThreadLocalMap、LinkedHashMap 和 ConcurrentHashMap。请关注。

小彭的 Android 交换群 02 群曾经建设啦，扫描文末二维码进入~

思维导图：

1. 什么是散列表？

散列表是基于散列思维实现的 Map 数据结构，散列思维是散列表的外围个性，也就做哈希算法或 Hash 算法。散列算法是一种将“任意长度的输出数据”映射为“固定长度的特征值”的算法，输入的特征值就是散列值。

用一个表格总结散列算法的次要性质：

将散列思维利用到散列表数据结构上时，就是通过 hash 函数提取键（Key）的特征值（散列值），再将键值对映射到固定的数组下标中，利用数组反对随机拜访的个性，实现 O(1) 工夫的存储和查问操作。

事实上，个别不会间接应用 hash 函数计算后的散列值作为数组下标。例如 Java Object#hashCode() 散列值是 int 类型，值域足足有 2^32 的容量，咱们不可能创立这么大的数组。

最简略的做法是将散列值对数组长度取余后再取绝对值：|hash % length|。如果数组长度 length 是 2 的整数幂，还能够等价替换成位运算：hash & (length - 1)，不论被除数是正负后果都是负数。 不仅将取余运算替换为位运算，而且缩小了一次取绝对值运算，进步了索引的计算效率。

10  % 4 = 2
-10 % 4 = -2      // 正数
10  & (4 - 1) = 2
-10 & (4 - 1) = 2 // 负数 

散列表示意图

提醒： 尽管咱们将取余运算优化为位运算，然而为了便于了解，咱们在后文中仍然形容为逻辑上的“取余”运算。

2. 散列表无奈防止的抵触问题

因为 Hash 算法会将十分大甚至无穷大的输出值域映射到“固定长度的特征值”，所以 Hash 算法肯定是压缩映射。例如，MD5 的输入散列值为 128 位，SHA256 的输入散列值为 256 位，这就存在 2 个不同的输出产生雷同输入的可能性。这就是散列抵触或哈希抵触（Hash Collision）问题。

事实上，在散列表的设计中存在 2 次散列抵触：

• 第 1 次 – hash 函数的散列抵触： 这是个别意义上的散列抵触；
• 第 2 次 – 散列值取余转数组下标： 实质上，将散列值转数组下标也是一次 Hash 算法，也会存在散列抵触。同时，这也阐明 HashMap 中同一个桶中节点的散列值不肯定是雷同的。

其实，散列抵触只有用鸽巢原理（又称：抽屉原理）就很好了解了，假如有 10 个鸽巢，现有 11 只鸽子，无论调配如许均匀，也必定有一个鸽巢里有两只甚至多只鸽子。举一个间接的例子，Java 中的字符串 "Aa" 与 "BB" 的就存在散列抵触。

散列抵触举例

String str1 = "Aa";
String str2 = "BB";
System.out.println(str1.hashCode());  // 2112
System.out.println(str2.hashCode());  // 2112 散列抵触 

因为咱们无奈防止散列抵触，所以只能保障散列表不会因为散列抵触而失去正确性。罕用的散列抵触解决办法有 2 类：

• 凋谢寻址法： 例如 ThreadLocalMap；
• 拆散链表法： 例如 HashMap。

3. 凋谢寻址法

凋谢寻址（Open Addressing）的核心思想是： 在呈现散列抵触时，在数组上从新探测出一个闲暇地位。经典的探测办法有线性探测（Linear Probing）、平方探测（Quadratic Probing）和双散列探测（Double Hashing Probing）。

3.1 线性探测

线性探测是最根本的探测办法，在 Java 实现线程部分存储的 ThreadLocal 类中的散列表，就是基于线性探测的散列表。ThreadLocal 咱们会在后续专栏文章会探讨，请关注。

• 增加键值对： 先将散列值取余映射到数组下标，而后从数组下标地位开始探测与指标 Key 相等的节点。如果找到，则将旧 Value 替换为新 Value，否则沿着数组程序线性探测。直到线性探测遇到闲暇地位，则阐明节点不存在，须要增加新节点。如果在增加键值对后数组没有闲暇地位，就触发扩容；
• 查找键值对： 查找相似。也是先将散列值映射到数组下标，而后从数组下标地位开始线性探测。直到线性探测遇到闲暇地位，则阐明节点不存在；
• 删除键值对： 删除相似。因为查找操作在遇到闲暇地位时，会认为键值对不存在于散列表中，如果删除操作时“真删除”，就会使得一组间断段产生断层，导致查找操作生效。因而，删除操作要做“假删除”，删除操作只是将节点标记为“Deleted”，查找操作在遇到“Deleted”标记的节点时会持续向下探测。

凋谢寻址法示意图

线性探测的毛病是“一次汇集”问题： 不仅会让散列抵触的键值对汇集，还会让本来没有散列抵触但地位被占用的节点被迫汇集在一起，升高了增加和查找效率。最坏状况下，有可能须要线性探测整张散列表能力找到指标地位。

3.2 平方探测法

平方探测与线性探测相似，区别在于： 线性探测的探测指针是一个线性序列，而平方探测的探测指针是一个平方序列。应用平方探测并不能齐全解决“汇集”问题，但相比于线性探测汇集景象有所削弱。

须要特地留神， 平方探测法必须要求数组的长度必须是 4k+3 型素数， 能力保障可能探测残缺个数组空间，否则会呈现数组有闲暇地位，但平方探测找不到的状况，此时扩容显得没有必要。

3.3 双散列探测

双散列探测的核心思想是：提供一组散列函数，在遇到计算失去的数组下标地位被占用，则应用下一个散列函数从新计算，直到找到闲暇地位。

比照下 3 种办法的探测步骤：

• 线性探测： hash(key) + 0，hash(key) + 1，hash(key) + 2，hash(key) + 3…
• 平方探测： hash(key) + 0^2，hash(key) + 1^2，hash(key) + 2^2，hash(key) + 3^2…
• 双散列探测： hash(key)，hash1(key)，hash2(key)，hash3(key)…

4. 拆散链表法

拆散链表法（Separate Chaining）的核心思想是： 在呈现散列抵触时，将抵触的元素增加到同一个桶（Bucket / Slot）中，桶中的元素会组成一个链表，或者跳表、红黑树等动静数据结构。

相较之下，链表法是更罕用且更稳固的抵触解决办法，咱们相熟的 Java HashMap 就是基于拆散链表法的实现。HashMap 咱们会在后续专栏文章会探讨，请关注。

• 增加键值对： 先通过散列函数将散列值映射到数组下标，而后沿着链表寻找节点的 Key 和增加的 key 相等的节点。如果找到，则将旧 Value 替换为新 Value，如果找不到，则创立在链表上新建节点；
• 查找键值对： 查找与增加的步骤相似，也是先将散列值映射到数组下标，而后沿着链表寻找节点的 Key 和增加的 key 相等的节点。如果找不到，则阐明键值对不存在于散列表中；
• 删除键值对： 删除键值对不须要“假删除”，与增加和查找相似，也是先将散列值映射到数组下标，而后沿着链表寻找节点的 Key 和增加的 key 相等的节点。如果找到，则将节点从链表上移除。

拆散链表法示意图

5. 影响散列表性能的因素

从下面的内容咱们逐步明确， 散列表操作的工夫复杂度并不是相对的 O(1)。 它与地址沉积的个数 K 或链表的长度 K 无关，也就是 O(K)。尽管 O(K) 也是常数工夫复杂度，但并不是固定的常数。在极其状况下，当所有的数据都沉积在一起，或者所有数据都映射到雷同的链表中时，工夫复杂度就会从 O(1) 进化到 O(n)。

换句话说，影响散列表性能的关键在于“散列抵触的产生概率”，抵触概率越低，工夫复杂度越靠近于 O(1)。 那么，哪些因素会影响抵触概率呢？次要有 3 个：装载因子、抵触解决办法、散列函数。

5.1 因素 1 – 装载因子和扩容

了解了凋谢地址法和拆散链表法两种抵触解决办法后，咱们会发现： 无论应用哪种办法，随着散列表中元素越来越多，闲暇地位越来越少，就会导致散列抵触的产生概率越来越大，使得散列表操作的均匀工夫会越来越大。为了形容散列表的装满水平，咱们定义 装载因子 (Load Factor) = 散列表中键值对数目 / 散列表的长度。

• 在基于凋谢寻址法的散列表中： 装载因子的最大值是 1（数组装满），装载因子为 1 时无奈增加新元素，必须扩容；
• 在基于拆散链表法的散列表中： 容许装载因子超过 1（拉长出很长的链表），装载因子为 1 时，扩容并不是必须的。

 装载因子 = 散列表中键值对数目 / 散列表的长度 

扩容实质上是扩充了散列算法的输入值域，扩充输入值域能够间接升高抵触概率。事实上，个别不会等到装载因子靠近 1 时再扩容，而是设置一个处于 (0, 1) 之间的 装载因子下限（扩容阈值）。 例如，在 HashMap 中设置的默认装载因子下限是 0.75。

当散列表的装载因子大于扩容阈值时，就会触发扩容操作，并将原有的数据搬运到新的数组上。与一般数组相比，散列表的动静扩容不再是简略的数据搬运，因为数组的长度变动了，公式 hash & (length - 1) 的计算的下标地位也变了，所以这一扩容过程也叫“再散列”（不要和双散列探测混同）。

散列表的扩容过程

当增加操作触发扩容时，须要破费 O(n) 工夫再散列和搬运数据，那么散列表的工夫复杂度还是 O(1) 常数工夫吗？对于这种大部分操作工夫复杂度很低，只有个别情况下工夫复杂度会进化，而且这些操作之间存在很强烈的程序关系的状况，就很适宜用 “均摊工夫复杂度剖析” 了。咱们将破费 O(n) 工夫的那一次插入操作的工夫均摊到随后的屡次 O(1) 工夫插入操作上，那咱们从整体看，增加数据的均摊工夫复杂度就是 O(1)。

以上是从算法剖析的角度，从工程剖析的角度看，事件还没这么简略。 在大数据场景下，如果旧散列表中有 1 GB 数据，那么扩容操作就是对 1 GB 的数据量做再散列。无论算法剖析把工夫复杂度摊还到多低，对 1 GB 数据量的再散列就是实打实的耗时操作，也是无法忍受的。此时，为防止一次性扩容过多数据的状况，有一种 “懒扩容” 计划：在翻新一个新散列表的同时，保留旧的散列表。每次插入新的数据都插入到新散列表中，并从旧散列表中取一个数据再散列到新的散列表中。通过屡次操作后，旧散列表中的数据就逐步搬运到新散列表中。

5.2 因素 2 – 采纳的抵触解决办法

凋谢寻址法和拆散链表法的优缺点和实用场景不同：

• 1、拜访效率不同： 凋谢寻址法中数据都存储在数组中，是一个间断的内存区域，基于局部性原理，凋谢寻址法可能更好地命中 CPU 缓存行。而拆散链表法中的数据次要位于链表中，是离散的内存区域，对 CPU 缓存行不优敌对；
• 2、抵触概率不同： 凋谢寻址法的抵触概率人造比拆散链表法高，这是因为凋谢寻址法在发生冲突后，会在邻近的地位寻找闲暇地位填充数据，这使得本来并没有“抵触”的键值对也会因为没有闲暇地位而被迫沉积。而拆散链表法只有的确发生冲突的键值对才会沉积到同一个桶中；
• 3、内存利用率不同： 因为凋谢寻址法的抵触概率更高，所以装载因子下限不能设置很高，存储雷同的数据量，凋谢寻址法也须要事后申请更大的数组空间，内存利用率不会高。当然，拆散链表法在链表指针上也有额定内存耗费，如果存储的元素的内存量远远大于一个指针的内存量，则能够疏忽不迭。

综上所述，它们各自的实用场景是什么呢？

• 凋谢寻址法 – 对装载因子敏感，适宜于小数据量且装载因子较小的场景： 例如 Java 的 ThreadlLocalMap，因为我的项目中不会大量应用 ThreadLocal 线程部分存储，所以它是一个小规模数据场景，这里应用开发地址法是没问题的；
• 拆散链表法 – 对装载因子的容忍度更高，适宜于大数据量且大对象（绝对于一个指针）的场景： 例如，Java 中更通用的 HashMap 散列表就是采纳拆散链表法。而且，拆散链表法还可能应用更多灵便的优化策略，例如将链表树化为红黑树，防止极其状况下工夫复杂度进化为 O(n)。

5.3 因素 3 – 散列函数设计

散列算法随机性和高效性也会影响散列表的性能。如果散列值不够随机，即便散列表整体的装载因子不高，也会使得数据汇集在某一个区域或桶内，仍然会影响散列表的性能。如果散列算法不够高效，也会间接耗费计算性能。

6. 总结

• 1、散列表是基于散列思维实现的 Map 数据结构，就是通过 hash 函数提取键（Key）的特征值（散列值），再将键值对映射到固定的数组下标中，利用数组反对随机拜访的个性，实现 O(1) 工夫的存储和查问操作；
• 2、当数组的长度为 2 的整数幂时，能够将取余运算转换为位运算 hash & (length - 1)，进步索引的计算效率；
• 3、因为散列值算法是压缩映射，所以散列表永远无奈防止散列抵触，罕用的散列抵触解决办法有凋谢寻址法和拆散链表法；
• 4、凋谢寻址（Open Addressing）的核心思想是在呈现散列抵触时，在数组上从新探测出一个闲暇地位。经典的探测办法有线性探测、平方探测和双散列探测；
• 5、拆散链表法（Separate Chaining）的核心思想是在呈现散列抵触时，将抵触的元素增加到同一个桶（Bucket / Slot）中，桶中的元素会组成一个链表，或者跳表、红黑树等动静数据结构；
• 6、凋谢寻址法对装载因子敏感，适宜于小数据量且装载因子较小的场景。拆散链表法对装载因子的容忍度更高，适宜于大数据量且大对象（绝对于一个指针）的场景；
• 7、采纳的散列抵触解决办法、装载因子和散列函数设计都会影响散列表性能。

明天，咱们聊了散列表的整体设计思维。在后续几篇文章里，咱们将探讨散列表的具体实现 —— HashMap。请关注。

参考资料

• 数据结构与算法剖析 · Java 语言形容（第 5 章 · 散列）—— [美] Mark Allen Weiss 著
• 算法导论（第 11 章 · 散列表）—— [美] Thomas H. Cormen 等 著
• 散列算法 —— 维基百科
• 数据结构与算法之美（第 18~22 讲）—— 王争 著，极客工夫 出品