[数据结构与算法]HashMap

HashMap

散列表也叫哈希表，是存储Key-Value映射的集合。对于某一个Key，散列表可以在接近O(1)的时间内进行读写操作

寻址方式

对key按一定的计算规则，算出hash值，并对数组长度进行取模

// 取模代价远远高于位操作代价，因此 Array.length等于二的幂
index = HashCode (Key) % Array.length   

哈希冲突

当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的。例如002936这个Key对应的数组下标是2；002947这个Key对应的数组下标也是2。

解决哈希冲突

1. 开放寻址法(ThreadLocal)
2. —链表法(HashMap)

扩容

衡量HashMap需要进行扩容的条件如下【HashMap.Size >= Capacity×LoadFactor】当前长度：Capacity，负载因子：LoadFactor(0.75f)

数据结构

ArrayList数据结构：【数组】

LinkedList数据结构：【链表】，单向和双向 Node(element,next,prev)

HashMap数据结构：【数组+链表】；链表长度超过8（hash冲突次数），则将其转换为红黑树

HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可