HashMap底层原理
1、HashMap底层原理
在 JDK 1.7 中 HashMap 是以「数组加链表」的形式组成的，JDK 1.8 之后新增了「红黑树」的组成结构，「当链表长度大于 8 并且 hash 桶的容量大于 64 时，链表结构会转换成红黑树结构」。所以，它的组成结构如下图所示：
HashMap 中数组的每一个元素又称为哈希桶，也就是 key-value 这样的实例。在 Java7 中叫 Entry，Java8 中叫 Node。
因为它本身所有的位置都为 null，在 put 插入的时候会根据 key 的 hash 去计算一个 index 值。比如，我 put ("徐庶", 666)，在 HashMap 中插入 "徐庶" 这个元素，通过 hash 算法算出 index 位置是 3。这时的结构如下所示，还是个数组。
以上没 hash 冲突时，若发生 hash 冲突就得引入链表啦。假设我再次 put ("元直", 666)，在 HashMap 中插入 "元直" 这个元素，通过 hash 算法算出 index 位置也是 3。这时的结构如下所示：形成了链表。
2、HashMap的重要方法
查询-get方法
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }key的hashCode右移16再与key的hashCode值进行异或运算，可以使得key的高16位与低16位都参与了运算，减少了hahs冲突的可能。
first = tab[(n - 1) & hash]用高效的位运算代替取模，计算数组下标。