java 集合之HashMap

实现原理：

HashMap由数组+链表组成，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。

如果通过hash定位到数组位置没有链表，则查找、添加速度很快。否则，就要解决hash冲突，操作链表。遍历链表时，通过key对象的equals方法逐一比对。

构造hashmap的时候有两个参数，initialCapacity初始容量（默认16）、loadFactor装载因子（默认0.75）。

向容器中添加元素的时候，如果元素个数达到阈值（元素个数=数组长度*loadFactor），就要自动扩容。

使用一个新的数组代替已有的数组，每次扩容为先前的两倍。

经过 rehash 之后，元素的位置要么在原位置，要么在原位置再移动2次幂的位置。

hash函数

调用对象key自带的hashCode()，hashCode()返回intl类型值。

右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

散列值不能直接使用，还要对数组长度取模（异或实现散列值映射到数组，^代替%，效果一样），得到余数才能访问数组下标。如下：

 https://www.hollischuang.com/archives/2091

java 集合之HashMap

原文：https://www.cnblogs.com/natian-ws/p/10762213.html