首先，HashMap 是 Map 的一个实现类，它代表的是一种键值对的数据存储形式。key和value允许为null,key不允许重复，可以接受null键和值。
jdk 8 之前，其内部是由数组+链表来实现的，继承了数组的线性查找和链表的寻址修改，而 jdk 8 对于链表长度超过 （底层代码>=）8 的链表将调用treeifyBin函数转储为红黑树。因为，如果按照链表的方式存储，随着节点的增加数据会越来越多，这会导致查询节点的时间复杂度会逐渐增加，平均时间复杂度Ｏ(n)。 为了提高查询效率，故在JDK１.8中引入了改进方法红黑树，以加快检索速度。此数据结构的平均查询效率为Ｏ(log n) 。
要了解红黑树，先要知道avl树，要知道avl树，首先要知道二叉树。
二叉树
二叉树就是每个父节点下面有零个一个或两个子节点。我们在向二叉树中存放数据的时候将比父节点大的数放在右节点，将比父节点小的数放在左节点，这样之后我们在查找某个数的时候只需要将其与父节点比较，大则进入右边并递归调用，小则进入左边递归。但其存在不足，如果运气很不好我的数据本身就是有序的，比如【1，2，3，4，5，6，7】，这样就会导致树的不平衡，二叉树就会退化成为链表。所以我们推出了avl树。
avl树
avl树即平衡树，他对二叉树做了改进，在我们每插入一个节点的时候，必须保证每个节点对应的左子树和右子树的树高度差不超过1。如果超过了就对其进行调平衡，具体的调平衡操作就不在这里讲了，无非就是四个操作——左旋，左旋再右旋，右旋再左旋。最终可以是二叉树左右两边的树高相近，这样我们在查找的时候就可以按照二分查找来检索，也不会出现退化成链表的情况。
红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
红黑树的特点：
1.节点是红色或黑色。
2.根节点是黑色。
3 每个叶子节点（NIL）是黑色。[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。
而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。详细了解红黑树原理可以直接百度。
HashMap的 get(Object key)方法分析：
1 public V get(Object key) { 2 Node<K,V> e; 3 return (e = getNode(hash(key), key)) == null ? null : e.value; 4 }
看下hash(key)算法：
1 static final int hash(Object key) { 2 int h; 3 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 4 }
hash方法计算的值为key的hashCode值与其右移16位后的异或的结果。
getNode源码：
1 final Node<K,V> getNode(int hash, Object key) { 2 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 3 if ((tab = table) != null && (n = tab.length) > 0 && 4 (first = tab[(n - 1) & hash]) != null) { 5 if (first.hash == hash && // always check first node 6 ((k = first.key) == key || (key != null && key.equals(k)))) 7 return first; 8 if ((e = first.next) != null) { 9 if (first instanceof TreeNode) 10 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 11 do { 12 if (e.hash == hash && 13 ((k = e.key) == key || (key != null && key.equals(k)))) 14 return e; 15 } while ((e = e.next) != null); 16 } 17 } 18 return null; 19 }
Node<K,V>就是数组中存储的元素，其源码：
1 static class Node<K,V> implements Map.Entry<K,V> { 2 final int hash; 3 final K key; 4 V value; 5 Node<K,V> next; 6 7 Node(int hash, K key, V value, Node<K,V> next) { 8 this.hash = hash; 9 this.key = key; 10 this.value = value; 11 this.next = next; 12 } 13 14 public final K getKey() { return key; } 15 public final V getValue() { return value; } 16 public final String toString() { return key + "=" + value; } 17 18 public final int hashCode() { 19 return Objects.hashCode(key) ^ Objects.hashCode(value); 20 } 21 22 public final V setValue(V newValue) { 23 V oldValue = value; 24 value = newValue; 25 return oldValue; 26 } 27 28 public final boolean equals(Object o) { 29 if (o == this) 30 return true; 31 if (o instanceof Map.Entry) { 32 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 33 if (Objects.equals(key, e.getKey()) && 34 Objects.equals(value, e.getValue())) 35 return true; 36 } 37 return false; 38 } 39 }
由以上代码我们可以看到，在HashMap中要找到某个元素，先根据hash(key)值来找到key对应的Node元素在数组中的位置，返回唯一的node.value。查找方式：
1.根据key的hash算法找到该key对应的Node在数组中的元素位置，找不到直接返回null;
2.可以找到元素位置，则根据key的equals方法匹配元素位置的key:
a.若相等则直接返回数组中的该元素的value值;
b.不相等则判断：该节点若属于红黑树则调用红黑树的方法查找并返回结果，否则用do{}while方式遍历链表查找；
HashMap的put(K key, V value)方法分析：
1 public V put(K key, V value) { 2 return putVal(hash(key), key, value, false, true); 3 } 4 5 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { 6 Node<K,V>[] tab; Node<K,V> p; int n, i; 7 //如果 table 还未被初始化，那么初始化它 8 if ((tab = table) == null || (n = tab.length) == 0) 9 n = (tab = resize()).length; 10 //根据键的 hash 值找到该键对应到数组中存储的索引 11 //如果为 null，那么说明此索引位置并没有被占用 12 if ((p = tab[i = (n - 1) & hash]) == null) 13 tab[i] = newNode(hash, key, value, null); 14 //不为 null，说明此处已经被占用，只需要将构建一个节点插入到这个链表的尾部即可 15 else { 16 Node<K,V> e; K k; 17 //当前结点和将要插入的结点的 hash 和 key 相同，说明这是一次修改操作 18 if (p.hash == hash && 19 ((k = p.key) == key || (key != null && key.equals(k)))) 20 e = p; 21 //如果 p 这个头结点是红黑树结点的话，以红黑树的插入形式进行插入 22 else if (p instanceof TreeNode) 23 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 24 //遍历此条链表，将构建一个节点插入到该链表的尾部 25 else { 26 for (int binCount = 0; ; ++binCount) { 27 if ((e = p.next) == null) { 28 p.next = newNode(hash, key, value, null); 29 //如果插入后链表长度大于等于 8 ，将链表裂变成红黑树 30 if (binCount >= TREEIFY_THRESHOLD - 1) 31 treeifyBin(tab, hash); 32 break; 33 } 34 //遍历的过程中，如果发现与某个结点的 hash和key，这依然是一次修改操作 35 if (e.hash == hash && 36 ((k = e.key) == key || (key != null && key.equals(k)))) 37 break; 38 p = e; 39 } 40 } 41 //e 不是 null，说明当前的 put 操作是一次修改操作并且e指向的就是需要被修改的结点 42 if (e != null) { 43 V oldValue = e.value; 44 if (!onlyIfAbsent || oldValue == null) 45 e.value = value; 46 afterNodeAccess(e); 47 return oldValue; 48 } 49 } 50 ++modCount; 51 //如果添加后，数组容量达到阈值，进行扩容 52 if (++size > threshold) 53 resize(); 54 afterNodeInsertion(evict); 55 return null; 56 }
当程序试图将一个key-value对放入HashMap中时，程序首先根据hash(key)返回值决定该 Entry(HashMap内部类Node实现了Entry) 的存储位置：
1.如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。
2.如果这两个 Entry 的 key 通过 equals 比较返回 true，则新添加 Entry 的 value 将覆盖集合中原有 Entry的 value，但key不会覆盖。
3.如果这两个 Entry 的 key 通过 equals 比较返回 false，则新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的尾部，当链表长度大于等于8，则将链表裂变成红黑树。
当HashMap中的数据越来越多时，发生碰撞的概率也越来越高，这个时候会对数据进行扩容，默认长度为16，负载因子为0.75，也就是数据数目达到两者乘积也就是16*0.75=12时，数组会扩容为原来的两倍，2*16=32。这个扩容操作叫做rehash，因为要对原先所有数据重新计算位置，再放入扩容后的数组中，所以如果可以确定数组长度的话，提前设置好长度，可以减少性能消耗。
原文：https://www.cnblogs.com/itfeng813/p/11593348.html
