HashMap
这篇文章介绍了HashMap（哈希映射）的概念、在JDK中的实现原理及其在不同编程语言中的实现。
HashMap的核心概念包括： * 键(key)：用于生成哈希索引的输入。 * 哈希函数(hash function)：将键转换为哈希索引。 * 哈希表(hash table)：存储键值对的列表数组。 * 负载系数(load factor)：衡量哈希表填充程度的指标，默认为0.75。
HashMap的优点是： * 增删和搜索的时间复杂度为O(1)。
JDK中的HashMap实现原理：
* 存储方式：使用哈希表存储，每个槽(Solt)是一个集装箱(Bin)。通过键的哈希值与哈希表容量取余来确定存储索引。为了提高效率，取余运算通常转化为位运算（i = (n - 1) & hash）。哈希表容量总是2的整数次方，扩容时容量变为原来的2倍，通过位运算(newThr = oldThr << 1)计算新阈值。
* 哈希冲突解决方法：当集装箱内元素数量较少时（小于树化阈值，默认为8），使用链表存储。当元素数量超过阈值时，集装箱会“树化”，转为使用红黑树存储，以提高查找效率。
* 红黑树插入键：优先使用键的哈希值比较，若哈希值不可比较则比较键的Comparable接口实现，最后使用决胜局算法（tieBreakOrder）进行比较。决胜局算法先比较类型名称，若仍无法比较则回退使用identityHashCode()。
* 红黑树搜索键：通过键的引用相等或equals方法比较判断键相等。搜索过程也优先使用哈希值，然后是Comparable接口，若冲突则递归查找左右节点。
* 自动扩容：当元素数量超过负载系数规定的阈值时，HashMap会自动扩容。扩容时，所有元素需要根据新的哈希表容量重新计算位置并移动。对于树化的集装箱，会根据元素的哈希值高低位将其分离，并可能在树规模较小时拆分成链表。
* 遍历顺序：HashMap本身不保证遍历顺序。如果需要保证遍历顺序，可以使用JDK提供的LinkedHashMap类，它通过在节点中添加before和after属性来维护一个全局的双向链表，从而实现遍历顺序的保持。
文章最后提供了使用Python、C++和Java实现HashMap，以及Python和C++实现LinkedHashMap的代码示例。
HashMap
哈希映射旨在解决快速查找和访问一个集合中的元素的问题。常用于数据库索引、基于磁盘的数据结构以及数据压缩算法，在密码学上常用于密码的存储。
对于哈希我们关注以下概念：
- 键(key)：键可以是整形、字符串甚至是更复杂的复合类型，用于输入哈希函数生成哈希索引。
- 哈希函数(hash function)：输入键并生成键对应的哈希索引，该索引用于哈希表寻址。
- 哈希表(hash table)：哈希表通常为一个列表数组，存储与键对应的值。
- 负载系数(load factor)：哈希表的负载系数为哈希表元素个数与哈希表大小的比值。默认值为0.75。
哈希具有如下优点：
- 增删和搜索的时间复杂度为$O(1)$
JDK中的HashMap实现
我们通过几个问题回答一下实现原理：
哈希映射是怎么存储的?
哈希映射采用哈希表存储，哈希表每个槽(Solt)为一个集装箱(Bin),取哈希表容量与键的哈希值比值的余数获取哈希表索引进行存储。
哈希映射以2整数次方大小创建哈希表，根据公式$h \mod 2^n = h \& (2^n-1)$取余运算可以转化为按位与运算，$(2^n-1)$代表n位二进制数的最大值，按位与该值等同于取原值的后$n$位二进制数，和取余是等价的。位运算的速度相对更快，哈希映射源码中使用位运算i = (n - 1) & hash来计算哈希表集装箱位置，提高运算效率。
当哈希表的元素个数超过负载系数规定的阈值时进行哈希表扩容，每次扩容为原来的2倍。
源码中使用位运算newThr = oldThr << 1生成新的阈值。
哈希映射是如何解决哈希冲突的?
当集装箱元素个数小于阈值时采用链表存储数据，当元素个数大于阈值时采用红黑树存储数据。树化阈值TREEIFY_THRESHOLD默认为8。
哈希映射是如何在红黑树中插入一个键的?
哈希映射优先使用键的哈希值进行比较，若哈希值不可比较（哈希冲突）则检查键类型是否实现Comparable接口并进行比较，若仍不可比较则使用决胜局算法tieBreakOrder比较。在采用决胜局算法比较前会先调用红黑树搜索算法查找，以确认待插入键不在数据集内。
决胜局算法比较简单，先比较键的类型名称的大小，若仍无法比较则回退使用JDK原生方法identityHashCode()方法比较。
重要提示
决胜局算法仅作为一个维持红黑树插入连续性的规则。identityHashCode方法针对对象生成哈希值，对于成员以及hashCode()函数返回值完全相等的两个不同对象，他们的identityHashCode是完全不一样的，所以在查找阶段遇到哈希冲突且无法比较的情况时，是不会使用决胜局算法确定方向的，左右子节点都需要进行查找从而会增加查询消耗。
Tie-breaking utility for ordering insertions when equal hashCodes and non-comparable. We don’t require a total order, just a consistent insertion rule to maintain equivalence across rebalancings. Tie-breaking further than necessary simplifies testing a bit.
哈希映射是如何在红黑树中搜索一个键的？
哈希映射通过两个键的引用相等或两个键的equals比较结果为true来判断两个键相等。哈希映射优先使用键的哈希值进行比较，若哈希值不可比较（哈希冲突）则检查键类型是否实现Comparable接口并进行比较，若仍不可比较则递归当前节点的左右节点进行查找。
哈希映射是如何进行自动扩容的？
扩容时，由于哈希表容量发生改变，导致集装箱位置计算的结果也会发生改变，需要根据集装箱的状态移动元素到新表。
- 若集装箱位置为空则忽略元素移动。
- 若集装箱为一个元素的链表，直接计算该元素在新表中的位置并移动。
- 若集装箱为多个元素的链表，需要遍历链表确定高位元素和低位元素，高位元素移动到新哈希表高位，低位元素移动到新哈希表的原始位置。
- 若集装箱已经树化，需要遍历树中元素确定高位元素和低位元素并移动到新表，若树的规模较小会在该阶段拆分成链表。
hash & oldCapcity为0判断低位，否则为高位。二进制数$2^n$的$n+1$位为1，其余为0，按位与运算该值等同于保留后第$n+1$位二进制数的值，其余只置0。为什么判断该二进制位的值就能判定高位元素和低位元素呢？这我们得从取余计算说起，没扩容前计算余数是取的后$n$位，当扩容为原来的2倍时取的是后$n+1$位（e.g $2^3-1 = 7 = 111$, $2^4-1 = 15 = 1111$）。换新容量计算时，第$n+1$位计算为0时不影响其计算结果(新表低位位置)，第$n+1$位计算为1时计算结果比原来偏移了$2^n$个单位(新表高位位置)。
哈希映射是如何保证遍历顺序的？
JDK中使用LinkedHashMap类保证遍历顺序，该类继承自HashMap类，主要区别在于节点对象添加了before和after两个属性用于全局导航。
HashMap实现
基于JDK对HashMap的实现原理，下面分别使用三种语言实现了一下。