一、HashMap基本数据结构

1.jdk 1.7 版本

在jdk1.7源代码中，HashMap的数据结构由Entry对象和Entry对象数组构成。 及数组加链表（由于链表只有next指针，所以为单向链表）的形式！

//由entry组成的数组 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Entry对象数据结构如下：

static class Entry<K,V> implements Map.Entry<K,V> { //key 为 hashMap中put参数中的key final K key; //存储的value值 V value; //next为链表的下一个结点 Entry<K,V> next; //为当前key计算出来的hash int hash; }

链表在结点新增时，一般分为头插法和尾插法。 头插法:将新new出来的结点的next指针指向原来的头结点，并让原来的头结点等于新new出来的结点。

尾插法:不断遍历头结点，直到结点的next指针为null，则将当前结点的next指针指向新new出来的结点。 而Entry的构造方法中，h为hash值，k为key，v为value，而结点n则代表链表的头结点。

Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }

为什么说结点n为链表的的头结点呢？通过查看调用Entry类构造方法的createEntry方法源代码可知：

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++; }

对象e为table数组中索引为bucketIndex存储的链表的头结点。Entry构造方法中next = n就是头插法中将 new的Entry对象的next指向原来头结点的操作，table[bucketIndex]等于新new的Entry及替换原头结点的位置。

所以jdk 1.7 HashMap单向链表在结点新增时，使用了头插法，这也是HashMap在多线程进行put操作发生扩容造成死锁的原因之一！

2.jdk 1.8 版本

在jdk 1.8 的源代码中，HashMap类增加了红黑树，及数组Node[]、链表Node、红黑树TreeNode的数据结构。

//定义的table数组 transient Node<K,V>[] table; ... //只列出关键的信息 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; //node的构造方法， Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } //Node的hashCode计算方式 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } }

对比Node和Entry类的构造方法会感觉都是将当前结点next指针指向了传入的entry对象或node对象，那是否是说，jdk 1.8 的HashMap 也是头插法呢？

//源码中调用Node构造方法地方有两个，第一个地方是在add元素的是否，hash值与容量计算 //出的table数组索引位置为null或者类型为Node则，调用newNode进行元素添加。 //第二个地方是当存储的node类型为TreeNode，且红黑树个数小于6，将红黑树结点TreeNode //转换为Node的结点时。 // Create a regular (non-tree) node Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } // For conversion from TreeNodes to plain nodes Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { return new Node<>(p.hash, p.key, p.value, next); }

这里我们先只看newNode方法，关于jdk 1.8 HashMap数据结构转换我们在后面的博文中再说。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //定义临时变量tab，和当前结点p，n为table数组的大小，i为当前key对应索引 Node<K,V>[] tab; Node<K,V> p; int n, i; //HashMap 属于懒加载，即在new的时候并不会去创建table数组， //而是在元素添加时，判断table数组是否被初始化，未初始化就 //调用扩容进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //通过hash值与容量计算出对应的table位置， //如果当前位置为null，则直接新建一个node结点，此时传入newNode方法 //中的next为null if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //如果table索引位置存在对象 Node<K,V> e; K k; //判断当前对象的hash值、key、K对象相等，是则将e = p， //e的作用是判断hashMap中是否已存在key，e不为空则存在 //则将oldValue返回，将newValue进行覆盖 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断node结点是否为TreeNode ，如果为TreeNode则表示当前位置 //结点已转换为红黑树，所以node 和 TreeNode共同构成了hashMap else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //本次重点在这个位置！！！ //如果node为链表类型，则通过for循环遍历到最后位置 //此时newNode的next结点也是null，而p则为最后一个结点 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) //如果超过了8则判断是否需要转换 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 省略本次不需要的代码.... } }

所以jdk 1.8中 HashMap的链表在添加元素时，采用了尾插法！而根据上面部分源码，我们可以知道在添加元素put方法调用的putVal方法，对node的类型进行了判断，判断node是否为TreeNode，所以，另外的一个数据结构也就引申出来！

// LinkedHashMap 的静态内部类 Entry<K,V> extends HashMap.Node<K,V> // 所以TreeNode 是Node 类的子类，继承了Node类的next，并增加了prev指针， static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { //父结点 TreeNode<K,V> parent; // red-black tree links //左子结点 TreeNode<K,V> left; //右子结点 TreeNode<K,V> right; //上一个结点，包括继承的next下一个结点 //组成了红黑树和双向链表的一个数据结构 TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } }

那么TreeNode是如何实现双向链表和红黑树双重特性的呢？ 这不得不说到，当链表个数超过8且hashMap的table数组大小超过64才会进行红黑树转换，如果链表个数超过8但是table数组的大小未超过64，只会进行扩容！源码如下：

//putVal()方法中链表添加结点后，如果长度超过8会调用treeifyBin()方法 final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //MIN_TREEIFY_CAPACITY默认值为64 //所以当tab为null或者tab的大小及容量小于64时， if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); //当hash值运算出的index位置存在node结点时 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //循环遍历node结点，并将node结点转换为TreeNode结点 //这里先将node单向链表转为了TreeNode双向链表，不考虑红黑树特性 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); //此时TreeNode类中已构建双向链表完成，再通过TreeNode中的treeify方法 //来构建红黑树特性 if ((tab[index] = hd) != null) //大致为将第一个结点作为根结点，然后不断的next插入结点， //再根据红黑树特性进行自平衡（变色或旋转） hd.treeify(tab); } } ...

所以在链表结点node转为treeNode时，是现将node遍历转成treeNode，此时设置前后指针，维护双向链表。双向链表构建完成后再进行红黑树转换。

以上，就是基于jdk 1.7 与 jdk 1.8 HashMap基本数据结构的区别与组成！