HashMap的数据结构
HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，他的底层结构是一个数组，而数组的元素是一个单向链表。
HashMap默认初始化的是一个长度为16位的数组，每个数组储存的元素代表的是每一个链表的头结点。在jdk1.8中，当HashMap不断地插入元素，导致链表太长时，会将链表转换为红黑树。
Node<K,V>
Node是HashMap的一个内部类，实现了Map.Entry接口，本质就是一个存储键值对的链表。
具体如下：
static class Node<K,V> implements Map.Entry<K,V> { final int hash;//用来定位数组索引位置final K key; V value; Node<K,V> next;//链表的下一个nodeNode(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; }
....
}
Hash算法
通过Hash算法，对key计算出数组下标，把数据放在对应下标元素的链表上。
Hash算法：通过Key进行Hash的计算，就可以获取Key对应的HashCode。如果出现了重复的hashCode，就称作碰撞。
如果发生了碰撞事件，那么意味这数组的一个位置要插入两个或者多个元素，这个时候数组上面挂的链表起作用了，链表会将数组某个节点上多出的元素按照尾插法(jdk1.7及以前为头差法)的方式添加。
Hash算法本质上就是三步：取key的hashCode值、高位运算? 、取模运算。
位运算接近底层，速度较快。
Node<K,V>[] table
即哈希桶数组，明显它是一个Node的数组。
如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。
Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)。
HashMap如何扩容？
扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。 扩容后的HashMap容量是之前容量的两倍。
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //Capcity是指容量 int oldCap = (oldTab == null) ? 0 : oldTab.length; //Threshold是所能存储的最大数量 int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) {//超过最大值就不再扩充了if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //存储的最大数量Threshold翻倍 newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; //创建新的Node数组 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; // oldTab[j]表示原数组上的元素，也就是链表头节点或红黑树 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; }
HashMap插入数据：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //如果node[]数组为空，就先扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //计算index，并对null做处理 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //如果节点key存在，直接覆盖value 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; }
线程安全性
在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。
其他：
1.注意hashCode()和hash()算法的区别。。
定位hash槽是HashMap自己实现的hash()函数。
hashcode()是key对象的类覆写的Object中的方法。
先用hash(key)找到hash槽(也就是数组下标)，如果槽上没值，直接放上去；如果有值，再判断key是否为同一个对象（这里用的equals方法，间接使用了hashcode）,如果是就替代value，如果否则加到链表中。
参考博客：