HashMap原理 — 扩容机制及存取原理

回顾一下基本概念：

一. put方法

HashMap使用哈希算法得到数组中保存的位置，然后调用put方法将key-value对保存到table变量中。我们通过图来演示一下存储的过程。

简单解释一下：

我们关注一下这里面最重要的三个方法，hash()，putVal()，resize().

1. hash方法

我们通过hash方法计算索引，得到数组中保存的位置，看一下源码

我们可以看到HashMap中的hash算法是通过key的hashcode值与其hashcode右移16位后得到的值进行异或运算得到的，那么为什么不直接使用key.hashCode()，而要进行异或操作？我们知道hash的目的是为了得到进行索引，而hash是有可能冲突的，也就是不同的key得到了同样的hash值，这样就很容易产业碰撞，如何减少这种情况的发生呢，就通过上述的hash(Object key)算法将hashcode 与 hashcode的低16位做异或运算，混合了高位和低位得出的最终hash值，冲突的概率就小多了。举个例子：

我们的hash(Object key)算法一个道理，最终的hash值混合了高位和低位的信息，掺杂的元素多了，那么最终hash值的随机性越大，而HashMap的table下标依赖于最终hash值与table.length()-1的&运算，这里的&运算类似于挑包子的过程，自然冲突就小得多了。计算过程如下：

2. putVal方法

通过putVal方法将传递的key-value对添加到数组table中。

3. resize方法

HashMap通过resize()方法进行扩容，容量规则为2的幂次

二. get方法

我们先简单说一下get(Object key)流程，通过传入的key通过hash()算法得到hash值，在通过(n - 1) & hash找到数组下标，如果数组下标所对应的node值正好key一样就返回，否则找到node.next找到下一个节点，看是否是treenNode，如果是，遍历红黑树找到对应node，如果不是遍历链表找到node。我们看一下源码

这几个方法是核心，虽然HashMap还有很多常用方法，不过大体和这几个方法有关，或者实现逻辑相似，这里就不再多说了。

三. 总结

本文在上一章基本概念和底层结构的基础上，从源码的角度讲解了扩容机制以及存取原理，主要分析了put方法和get方法，put方法的核心为hash()，putVal()，resize()，get方法的核心为getNode()。