本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 发问。
前言
大家好,我是小彭。
在前几篇文章里,咱们聊到了 Java 中的几种线性表构造,包含 ArrayList、LinkedList、ArrayDeque 等。明天,咱们来探讨另一种罕用的根底数据结构,同时也是“面试八股文”的规范题库之一 —— 散列表(Hash Table)。
同时,在后续的文章里,咱们将以 Java 语言为例,剖析规范库中实现的散列表实现,包含 HashMap、ThreadLocalMap、LinkedHashMap 和 ConcurrentHashMap。请关注。
小彭的 Android 交换群 02 群曾经建设啦,扫描文末二维码进入~
思维导图:
1. 什么是散列表?
散列表是基于散列思维实现的 Map 数据结构,散列思维是散列表的外围个性,也就做哈希算法或 Hash 算法。散列算法是一种将“任意长度的输出数据”映射为“固定长度的特征值”的算法,输入的特征值就是散列值。
用一个表格总结散列算法的次要性质:
性质 | 形容 |
---|---|
1、单向性(根本性质) | 反对从输出生成散列值,不反对从散列值反推输出 |
2、高效性(根本性质) | 单次散列运算计算量低 |
3、一致性(根本性质) | 雷同输出反复计算,总是失去雷同散列值 |
4、随机性(高效性质) | 散列值在输入值域的散布尽量随机 |
5、输出敏感性(高效性质) | 类似的数据,计算后的散列值差异很大 |
将散列思维利用到散列表数据结构上时,就是通过 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 讲)—— 王争 著,极客工夫 出品