共计 717 个字符，预计需要花费 2 分钟才能阅读完成。
什么是哈希表
哈希表（Hash table）又叫散列表，指的是依据关键码值来间接进行拜访的数据结构（即 Key Value 构造）。也就是说，通过映射函数（f(key)）将每一个关键码值都映射到哈希表中一个地位，通过关键码值来拜访数据，以放慢查找的速度（即 O(n)）。这个映射函数叫做散列函数，寄存记录的数组叫做散列表。
给定表 M，存在函数 f(key)，对任意给定的关键字值 key，代入函数后若能失去蕴含该关键字的记录在表中的地址，则称表 M 为哈希 (Hash）表，函数 f(key) 为哈希(Hash) 函数。
什么是哈希抵触
对于不同的关键字，可能失去同一个哈希地址，即 f(key1) = f(key2) 且 key1 ≠ key2，对于这种情称为哈希抵触，也叫哈希碰撞
如何缩小哈希抵触
Java 的 HashMap 中，采纳的是取模算法，亦能够思考应用 offset 来缩小 hash 抵触
如何解决哈希抵触
hash 抵触不可避免，在 Java 的 HashMap 中，应用的是链表的模式解决 hash 抵触，亦可屡次 hash 直到不抵触，或建设公共区域寄存抵触的 key，或应用凋谢地址，往相邻的方向寻找未应用的存储地址
如何对待链表解决哈希抵触
通过 KV 构造的特点可知，该数据结构次要是解决无序数据的查问效率问题，然而因为引入了链表来解决 hash 抵触，在极其状况下查问会十分慢，因为链表的查问工夫复杂度为 O(n)，因而在 Java 的 HashMap 中又引入了红黑树，来均衡查问效率，当然由链表与红黑树的转换之间也存在着性能开销，故在转换条件上也有肯定的限度，在默认状况下，hashMap 的长度达到 64，链表长度大于 8 时才会进行红黑树转换
参考文献：
哈希表
面试官：哈希表都不晓得，你是怎么看懂 HashMap 的？
