HashMap的底层存储结构
JDK8中，HashMap是以数组+链表+红黑树的存储结构。
整体上看是一个数组，通过计算元素key的hash值来获取存放位置的数组下标，如果出现hash碰撞，以链表形式存储，称之为桶,如果链表长度达到8，会转换为红黑树存储，红黑树的引进主要是为了提升查询的性能。
HashMap的底层存储结构
HashMap常量
//缺省的初始容量16 tatic final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30; //默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //当桶上的节点数大于阈值时转换为红黑数 static final int TREEIFY_THRESHOLD = 8; //当桶上节点数小于阈值时转换为链表 static final int UNTREEIFY_THRESHOLD = 6; //被树化的最小Hash表容量 static final int MIN_TREEIFY_CAPACITY = 64;
HashMap变量
//元素存放表，长度总是2的幂次倍 transient Node<K,V>[] table; //具体元素存放集合 transient Set<Map.Entry<K,V>> entrySet; //实际存放键值对数量 transient int size; //扩容（重hash）或者map结构修改的次数 transient int modCount; //扩容阈值（容量*负载因子） int threshold; //负载因子 final float loadFactor;
Node是对Map中键值对的描述
static class Node<K,V> implements Map.Entry<K,V> { //hashCode，不可改变 final int hash; //key不可改变 final K key; V value; //指向当前元素的下一个元素，一个桶中形成链表组织 Node<K,V> next; ... }
HashMap插入元素过程
put过程.png
解释：
主要流程参考上图基本是清晰的，主要说一下图中标①的地方：
在进行链表添加时，首先判断下一个节点是否为空，为空就说明是链表最后一个节点，直接插入到链表尾部，如果不是最后一个节点，判断key是否存在，如果存在则覆盖value值，如果不存在，则继续链表遍历，直到找到相同key或者遍历完最后一个元素后插入到链表的尾部
对应插入元素源码解释如下
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //桶数组是否为空 if ((tab = table) == null || (n = tab.length) == 0) //为空先进行扩容 n = (tab = resize()).length; //根据hash值计算数组下标，并判断该下标处元素是否为空 if ((p = tab[i = (n - 1) & hash]) == null) //如果为空，将元素插入该位置 tab[i] = newNode(hash, key, value, null); else {//如果不为空，说明出现了hash碰撞，插入到桶中 Node<K,V> e; K k; //key是否相同，相同则覆盖元素的value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果是TreeNode，则按红黑树插入 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else {//如果不是TreeNode，插入到链表中 //遍历链表 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; } //判断key是否存在，key存在则跳出循环，接下来的流程中会覆盖value值，如果key不存在，则继续遍历链表 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //key存在，覆盖value值 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(); //为了继承自HashMap的LinkedHashMap而设计 afterNodeInsertion(evict); return null; }
