hashMap的内部实现原理（JDK1.8 hashmap改动）

1.hashmap结构

学过java的或者其他语言的我们都应该对数组和链表不会感到陌生。当然很清楚他们的优点和缺点。 队列：查询方便，插入，删除效率低，因为插入删除一个元素后，后面的元素都要重新下序号。 链表：插入，删除方便，但是查询效率低，链表查询要一个一次一次找下去

所以hashmap结合了两者的优点。

可以从上面的图（网上找的），可以看出hashMap是由数组和链表组成（我看的源码为jdk1.7，JDK1.8当链表的长度很大时，会使用红黑树的方式）

首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。

2.hashmap源码解析

（有些细节被我忽略了，方便学习，以下源码摘选自JDK1.7）

2.1构造

HashMap map=new HashMap<>(); public HashMap() { //当我们不传参数时，默认运行这个构造函数 //DEFAULT_INITIAL_CAPACITY=16，为我们需要的数组长度 //DEFAULT_LOAD_FACTOR=0.75，是hashmap到达现在数组的多少时，进行扩大 //比如现在的数组为16，当hashmap的数组存放到达16*DEFAULT_LOAD_FACTOR时，进行扩大 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } //接下来调用的函数，也是传入参数的方法 //传参数时 public HashMap(int initialCapacity, float loadFactor) { //当长度太长时， if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; this.loadFactor = loadFactor; threshold = initialCapacity; //在hashmap里这个方法做事情，但是他的子类里可以实现自己的方法 //这是模板设计模式的钩子函数~~ init(); }

我们可以看出其实在hashmap实例化的时候并没有创建数组等等，只是定义了loadFactor ，threshold 两个变量。其实hashmap的数组要在put第一个值时出现。

2.2 存放变量

put一个东西 map.put(1,”111”);

public V put(K key, V value) { //当hashmap的table，也就是hashMap的数组为空时，初始化数组 if (table == EMPTY_TABLE) { //看2.2.1函数 inflateTable(threshold); } if (key == null) return putForNullKey(value); //求出hash值 int hash = hash(key); //其实并不是直接把hash值当作key，要把hash与table的长度进行&位运算 int i = indexFor(hash, table.length); //如果在一模一样的key上有值了，就替换原来的值，并返货原值 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; //在相应的数组上面放入一个Entry，具体看2.2.2 addEntry(hash, key, value, i); return null; }

2.2.1初始化数组

//tosize为目前的数组大小 private void inflateTable(int toSize) { // Find a power of 2 >= toSize //这个是通过源码来找出小与等于tosize的最大的2的次方数 //比如3通过运算为2的一次方，17是16（2的4次方），16是16，15就是2的三次方8 int capacity = roundUpToPowerOf2(toSize); //计算出我们定义的边界值，就是到达threshold 时进行扩大，loadFactor是在2.1中初始化的，默认为0.75 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //构造数组 table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }

2.2.2 添加Entry

void addEntry(int hash, K key, V value, int bucketIndex) { //判断size长度是否超过我们的边界值，如果超过，长度就扩大两倍 if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } //添加新的Entry createEntry(hash, key, value, bucketIndex); } //这个方法其实很简单，就是实例化Entry链表，Entry的链表的next就是我们原来的链表 //其实就会在我们的链表头插入了一个新的链表 void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }

2.3get取数据

//这个其实很简单 public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } //先得到hash值 int hash = (key == null) ? 0 : hash(key); //把hash与table.length&运算，在遍历链表 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }

如果大家看的还是不明白的话，可以自己结合jdk的源码，边调试边看。 看完之后可以尝试写一个简单的hashMap（当然jdk的hashMap不单单这么简单。。）

---

2017-6-27 添加

3 JDK1.8源码解析

JDK1.8版本对hashmap的部分设计做出了修改 ，其中最大的不同是当链表的长度超过64时，数据结构会从链表转换成树的结构以及hash计算的方法。

在阅读下面的内容时，最好对JDK1.8 关于hashmap的内容大致进行阅读，基本思路和内容大致和1.7雷同。（分析都在对源码有初步了解的情况下）

3.1 hash坐标的计算

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

通过计算出hash值后，获取下标的操作和以前一样 ，通过(n-1)&hash获取坐标。 hash的散列值是int类型，有32位组成。当我们计算下标的时候，很有可能只用到了后面的几位，所以可能出现分布不均匀的现象。因此通过>>>16的方法，使前16位与后16位相互影响，使分布更加均匀。 也方便后面resize（）中调整链表更加方便。

3.2 添加数据

Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //前面的判断和以前大致相同 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断是否是树型结构 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //创建节点 p.next = newNode(hash, key, value, null); //当现在链表长度大于8时会调整结构 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //如果已经存在 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; p.next = newNode(hash, key, value, null);

整体上区别不大，主要是有两个地方修改： 1. 创建节点的时候，是插入到链表的最后面，1.7版本是插入到头。 2. 当链表的长度大于8时，会对链表的结构做出变化（调用resize方法，见3.3）。 3. 当节点类型是树形节点的时候，使用不同的方式处理。

当链表的长度大于8时，会运行下列的函数。 有注释看出，这个方法会替代所有的联型的排列方式，除非数组太小，由代码看出是小于64的时候。

/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //长度小于64的的时候，是调用resize()方法。 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); //把队列转换成树形的方式。 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }

3.3 resize方法

当链表的长度大于8时，会对链表的结构做出变化。

调整的基本思路为下图。n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，把0和1的分成两条链表，为0链表的在原来 下标下面，为1的链表转移到j + oldCap的地方。 这种处理方式好处是不需要重新计算下标的值，并且链表的次序也是和原来的保持一致。

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //省略一些基本代码，是调整数组的大小，数组大小扩大两倍 table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果是树形结构 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

3.3 树形

当链表的长度大于等于32的的时候，链表的形式会转变成树的结构，树形的结构更加加快的get的速度。

关于树形结构，hashMap使用的是红黑树（B树的一种），有兴趣的朋友可以去研究研究。 红黑树参考资料：http://www.cnblogs.com/v-July-v/archive/2010/12/29/1983707.html http://www.cnblogs.com/nullzx/p/6111175.html

参考文献： java中HashMap详解： http://alex09.iteye.com/blog/539545/ hash冲突：https://www.zhihu.com/question/20733617/answer/111577937