HashMap数据结构

哈希表结构（链表散列：数组+链表+红黑树）实现，结合数组和链表的优点。当数组总容量超过64，链表长度超过8时，链表会转为红黑树。

  1. transient Node<K,V>[] table;
  2.  // 初始容量为16
  3. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  4.  // 扩容因子
  5. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  6.  // 转为红黑树阈值
  7. static final int TREEIFY_THRESHOLD = 8;
  8.  // 由红黑树转为链表阈值
  9. static final int UNTREEIFY_THRESHOLD = 6;
  10.  // 最小转为红黑树时数组容量
  11. static final int MIN_TREEIFY_CAPACITY = 64;

HashMap工作原理

HashMap底层通过hash数组和单向链表实现，数组中每个元素都是链表，由Node内部类（实现Map.Entry接口）实现，HashMap通过put、get方法存储和获取。

存储

  1. 存储对象时，将K/V(key-value)键值对传给put()方法；
  2. 计算hash(K)方法计算k的hash值，然后结合数组长度，计算得到数组下标；
  3. 调整数组大小（当容量中元素个数大于capacity*loadfactor时，容量会进行扩容resize为2n）；

  4. 如果K的hash值在HashMap中不存在，则插入，若存在，则发生碰撞；如果K的hash值在HashMap中存在，且两者equals()返回true，则更新键值对；如果K的hash值在HashMap中存在，且两者equals()返回false，则插入链表（jdk7头插法，jdk8尾插法）或者红黑树中（树的添加方式）。

    put()方法

    image.png

  5. 判断键值对数组table[i]是否为空或者null，否则执行resize()进行扩容；

  6. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3；
  7. 判断table[i]的首个元素是否和key一样，如果相同（这里的相同指hashcode相同，equals()相同）直接覆盖value，否则转向4；
  8. 判断table[i]是否为treeNode，即table[i]是否是红黑树，如果是，则直接在书中叶子节点插入键值对，否则转向5；
  9. 遍历table[i]，判断链表长度是否大于8，大于8且HashMap元素总量大于64时把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
  10. 插入成功后，判断实际存在的键值对size是否超过了最大容量threshold，如果超过，进行扩容。 ```java public V put(K key, V value) { // 对key的hashcode()做hash操作 return putVal(hash(key), key, value, false, true); }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 步骤1：tab为空则创建 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 步骤2：计算index，并对null做处理 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; // 步骤3：节点key存在，直接覆盖value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 步骤4：判断该链为红黑树 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // 步骤5：该链为链表 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; } // key已经存在直接覆盖value 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; // 步骤6：超过threshold，进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

  1. <a name="xjYuY"></a>
  2. #### 扩容机制
  3. ```java
  4. final Node<K,V>[] resize() {
  5.     Node<K,V>[] oldTab = table;
  6.     // oldCap表示为当前table的元素个数，默认长度16，扩容：2n
  7.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  8.     int oldThr = threshold;
  9.     int newCap, newThr = 0;
  10.     if (oldCap > 0) {
  11.       // 超过扩容最大值，就不在扩容，只好让它去碰撞static final int MAXIMUM_CAPACITY = 1 << 30;
  12.       // @Native public static final int   MAX_VALUE = 0x7fffffff; 2^31-1
  13.         if (oldCap >= MAXIMUM_CAPACITY) {
  14.             threshold = Integer.MAX_VALUE;
  15.             return oldTab;
  16.         }
  17.         //没超过最大值，扩充为原来两倍
  18.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  19.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  20.             newThr = oldThr << 1; // double threshold
  21.     }
  22.     else if (oldThr > 0) // initial capacity was placed in threshold
  23.         newCap = oldThr;
  24.     else {               // zero initial threshold signifies using defaults
  25.         newCap = DEFAULT_INITIAL_CAPACITY;
  26.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  27.     }
  28.     //计算行的resize上限
  29.     if (newThr == 0) {
  30.         float ft = (float)newCap * loadFactor;
  31.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  32.                   (int)ft : Integer.MAX_VALUE);
  33.     }
  34.     threshold = newThr;
  35.     @SuppressWarnings({"rawtypes","unchecked"})
  36.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  37.     table = newTab;
  38.     if (oldTab != null) {
  39.         // 把每个bucket桶元素都移动到新的bucket桶元素上。
  40.         for (int j = 0; j < oldCap; ++j) {
  41.             Node<K,V> e;
  42.             if ((e = oldTab[j]) != null) {
  43.                 oldTab[j] = null;
  44.                 if (e.next == null)
  45.                     newTab[e.hash & (newCap - 1)] = e;
  46.                 else if (e instanceof TreeNode)
  47.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  48.                 else { // preserve order 链表优化重hash的代码块
  49.                     Node<K,V> loHead = null, loTail = null;
  50.                     Node<K,V> hiHead = null, hiTail = null;
  51.                     Node<K,V> next;
  52.                     do {
  53.                         next = e.next;
  54.                         //原索引
  55.                         if ((e.hash & oldCap) == 0) {
  56.                             if (loTail == null)
  57.                                 loHead = e;
  58.                             else
  59.                                 loTail.next = e;
  60.                             loTail = e;
  61.                         }
  62.                         //原索引+oldCap
  63.                         else {
  64.                             if (hiTail == null)
  65.                                 hiHead = e;
  66.                             else
  67.                                 hiTail.next = e;
  68.                             hiTail = e;
  69.                         }
  70.                     } while ((e = next) != null);
  71.                     // 原索引放到bucket里
  72.                     if (loTail != null) {
  73.                         loTail.next = null;
  74.                         newTab[j] = loHead;
  75.                     }
  76.                     //新索引= 原索引+oldCap放到bucket里
  77.                     if (hiTail != null) {
  78.                         hiTail.next = null;
  79.                         newTab[j + oldCap] = hiHead;
  80.                     }
  81.                 }
  82.             }
  83.         }
  84.     }
  85.     return newTab;
  86. }

获取

  1. 获取对象时，将K传给get()方法；
  2. 调用hash(K)方法（计算K的hash值）从而获取该键值K所在的链表的数组下标；
  3. 顺序遍历链表，equals()方法查询相同Node链表中K对象的V值；

hashcode是定位的，存储位置，equals是定性的，比较两者是否相等。

两个对象的hashcode相同会发生什么

如果hashcode值相同，值不一定就是相同的，还需要使用equals()方法比较，所以两个对象所在数组的下标相同，就会发生“碰撞”，又因为HashMap采用链表存储对象，这个Node会存储到链表中。

红黑树

  • 根节点是黑色
  • 每个节点非红即黑
  • 如果节点是红色，则子节点一定是黑色（反之不一定）
  • 每个叶子节点都是黑色的空节点（NIL节点）

  • 从根节点到叶子结点或空节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

    HashMap、LinkedHashMap、TreeMap区别

    HashMap使用数组+链表+红黑树保存数据；使用场景：在Map中插入、删除和定位元素的情况下；
    LinkedHashMap保存记录的插入顺序，使用Iterator遍历时，先取到的记录肯定是先插入的，遍历比HashMap慢；使用场景：在需要输出的顺序和输入的顺序相同的情况下；
    TreeMap实现SortMap接口，能够把它保存的记录根据键顺序（默认按键顺序升序排序，也可以指定排序的比较器）；使用场景：需要按自然顺序或自定义顺序遍历键的情况下；

    HashMap和HashTable区别

  • HashMap线程不安全，HashTable线程安全；

  • 由于线程不安全，HashMap效率比HashTable效率高；
  • HashMap只允许一条记录的键为null，允许多条记录的值为null，而HashTable不允许；
  • HashMap默认初始容量为16，扩容为原来两倍，HashTable默认初始容量为11，扩容为原来两倍+1；
  • HashMap需要重新计算K的hash值，而HashTable直接使用K的hashcode值。

    解决hash冲突的方法

  1. 开放地址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
  2. 再哈希法
  3. 链地址法（HashMap解决方法）

简单来说，就是数组+链表的结合，在每个数组元素上都加一个链表结构，当数据被hash后，得到数组下标，把数据放在对应下标元素的链表上。

  1. 建立一个公共溢出区