Java 基础 - 集合 - HashMap - 图2

put 方法

hashmapput.png

步骤

  1. 对key的hashCode做hash操作，然后再计算在桶中的index（1.5 HashMap的哈希函数）；
  2. 如果没碰撞直接放到桶里；
  3. 如果碰撞了，以链表的形式存在桶后；
  4. 如果节点已经存在，就替换old value(保证key的唯一性)

  5. 如果桶满了(超过阈值，阈值=loadfactor*current capacity，load factor默认0.75)，就要resize。

    源码

    1. public V put(K key, V value) {
    2.      return putVal(hash(key), key, value, false, true);
    3.  }
    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.      // 如果hashmap为空,调用resize方法，对hashmap进行扩容
    8.      if ((tab = table) == null || (n = tab.length) == 0)
    9.          n = (tab = resize()).length;
    10.      // 根据index找到目标桶后，若当前桶上没有结点，那么直接新增一个结点，赋值给该bucket
    11.      if ((p = tab[i = (n - 1) & hash]) == null)
    12.          tab[i] = newNode(hash, key, value, null);
    13.      else {
    14.          Node<K,V> e; K k;
    15.          // 若当前桶上有链表，且头结点就匹配，那么直接做替换即可；
    16.          // key的hash值一样，key一样，key不为null
    17.          if (p.hash == hash &&
    18.              ((k = p.key) == key || (key != null && key.equals(k))))
    19.              e = p;
    20.          // 若当前桶上的是树结构，则转为红黑树的插入操作
    21.          else if (p instanceof TreeNode)
    22.              e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    23.          else {
    24.              // 若上面的判断都不成立，则对链表做遍历操作
    25.              for (int binCount = 0; ; ++binCount) {
    26.                  // 尾插法，jdk 1.7 是头插法
    27.                  // 若没有结点匹配，则在链表末尾追加
    28.                  if ((e = p.next) == null) {
    29.                      p.next = newNode(hash, key, value, null);
    30.                      // 当链表的长度大于8 时，会将链表转化树
    31.                      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    32.                          // 转红黑树
    33.                          treeifyBin(tab, hash);
    34.                      break;
    35.                  }
    37.                  if (e.hash == hash &&
    38.                      ((k = e.key) == key || (key != null && key.equals(k))))
    39.                      break;
    40.                  p = e;
    41.              }
    42.          }
    43.          //  若链表中有结点匹配，则做value替换
    44.          if (e != null) { // existing mapping for key
    45.              V oldValue = e.value;
    46.              if (!onlyIfAbsent || oldValue == null)
    47.                  e.value = value;
    48.              afterNodeAccess(e);
    49.              return oldValue;
    50.          }
    51.      }
    52.      ++modCount;
    53.      // 判断是否需要扩容
    54.      if (++size > threshold)
    55.          resize();
    56.      afterNodeInsertion(evict);
    57.      return null;
    58.  }

红黑树转换

  1. final void treeifyBin(Node<K,V>[] tab, int hash) {
  2.     int n, index; Node<K,V> e;
  3.     // 若表为空，或表长度小于MIN_TREEIFY_CAPACITY，也不做转换，直接做扩容处理。
  4.     // MIN_TREEIFY_CAPACITY这个其实是转化成红黑树的另外一个条件，就是数组长度要大于64
  5.     // 如果小于64 就可以通过扩容的方法，来减小冲突，没有必要转换成红黑树，因为红黑树的转换也是需要很大是 时间和空间的代价
  6.     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  7.         resize();
  8.     // 获得需要树形化的 链表的第一个节点 也就是数组对应的数组节点table[i]
  9.     else if ((e = tab[index = (n - 1) & hash]) != null) {
  10.         TreeNode<K,V> hd = null, tl = null;
  11.         do {
  12.             //将普通的node节点 构造成TreeNode
  13.             TreeNode<K,V> p = replacementTreeNode(e, null);
  14.             if (tl == null)
  15.                 hd = p;
  16.             else {
  17.                 p.prev = tl;
  18.                 tl.next = p;
  19.             }
  20.             tl = p;
  21.         } while ((e = e.next) != null);
  22.         // 替换成 构造成双链表的节点
  23.         if ((tab[index] = hd) != null)
  24.             // 进行红黑树转换
  25.             hd.treeify(tab);
  26.     }
  27. }
  1. final void treeify(Node<K,V>[] tab) {
  2.             TreeNode<K,V> root = null;
  3.             // 循环遍历链表
  4.             for (TreeNode<K,V> x = this, next; x != null; x = next) {
  5.                 next = (TreeNode<K,V>)x.next;
  6.                 x.left = x.right = null;
  7.                 // 第一次循环        
  8.                 // 将x 赋值给root节点 初始化root节点的颜色 黑色（红黑树的根节点 一定是黑色）
  9.                 if (root == null) {
  10.                     x.parent = null;
  11.                     x.red = false;
  12.                     root = x;
  13.                 }
  14.                 // 此处开始构造红黑树
  15.                 else {
  16.                     //获得当前节点的 key  和 hash
  17.                     K k = x.key;
  18.                     int h = x.hash;
  19.                     Class<?> kc = null;
  20.                     // 从根节点开始每次遍历 寻找插入的位置
  21.                     for (TreeNode<K,V> p = root;;) {
  22.                         int dir, ph;
  23.                         K pk = p.key;
  25.           // 获得根节点的 key 
  26.           // 判断key 与root的key的大小 确定dir的值，也就确定了插入的方向 ，是root节点的左边还是右边
  27.                         if ((ph = p.hash) > h)
  28.                             dir = -1;
  29.                         else if (ph < h)
  30.                             dir = 1;
  31.     // 如果key的hash相等  或者实现comparable接口  又或者是实现了该接口 但是两个比较结果也相同
  32.     // 所以为了打破这种平衡必须再次调用tieBreakOrder方法 比较一次 返回值 只有-1 或1 
  33.                         else if ((kc == null &&
  34.                                   (kc = comparableClassFor(k)) == null) ||
  35.                                  (dir = compareComparables(kc, k, pk)) == 0)
  36.                             dir = tieBreakOrder(k, pk);
  38.                         TreeNode<K,V> xp = p;
  39.                         if ((p = (dir <= 0) ? p.left : p.right) == null) {
  40.                             // 当前链表节点 作为 当前树节点的父节点
  41.                             x.parent = xp;
  42.                             if (dir <= 0)
  43.                                 xp.left = x;
  44.                             else
  45.                                 xp.right = x;
  46.                             // 每次插入完一个节点之后，就要进行红黑树的调整
  47.                             root = balanceInsertion(root, x);
  48.                             break;
  49.                         }
  50.                     }
  51.                 }
  52.             }
  53.             // 根节点目前到底是链表的哪一个节点是不确定的 
  54.             // 要将红黑树的根节点 移动至链表节点的第一个位置 也就是 table[i]的位置。
  55.             moveRootToFront(tab, root);
  56.         }
  1. static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
  2.             int n;
  3.             if (root != null && tab != null && (n = tab.length) > 0) {
  4.                 // 获得当红黑树所处在 table数组的哪一个位置   (n - 1) & root.hash效果与取模相同
  5.                 int index = (n - 1) & root.hash;
  6.                 // 获得改位置的节点对象 也就是链表的第一个节点
  7.                 TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
  8.                 // 如果这个位置不是 root节点 那么就要进行调整了
  9.                 if (root != first) {
  10.                     // 定义一个临时Node 变量
  11.                     Node<K,V> rn;
  12.                     // 直接将链表的第一个位置 指向了root节点 
  13.                     tab[index] = root;
  14.                     // 将前驱和后继相连接 root节点从原链表中脱离出来了
  15.                     TreeNode<K,V> rp = root.prev;
  16.                     if ((rn = root.next) != null)
  17.                         ((TreeNode<K,V>)rn).prev = rp;
  18.                     if (rp != null)
  19.                         rp.next = rn;
  20.                     // 将root与原来双链表的第一个节点相连
  21.                     // 这样root又回到双链表当中 并且在双链表的第一个位置上
  22.                     if (first != null)
  23.                         first.prev = root;
  24.                     root.next = first;
  25.                     // root节点的前驱节点设置为null  因为他双链表的第一个节点 没有前驱
  26.                     root.prev = null;
  27.                 }
  28.                 assert checkInvariants(root);
  29.             }
  30.         }

扩容

在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：
java8resize2.png
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

触发扩容的场景

  1. 哈希table为null或长度为0；
  2. Map中存储的k-v对数量超过了阈值threshold；
  3. 链表中的长度超过了TREEIFY_THRESHOLD，但表长度却小于MIN_TREEIFY_CAPACITY。

扩容步骤

  1. 扩容：哈希表长度*2
  2. 移动：对每个节点重新计算哈希值，重新计算每个元素在数组中的位置，将原来的元素移动到新的哈希表中。

源码

  1. // 初始化或加倍表大小。如果为 null，则根据字段阈值中保留的初始容量目标进行分配。否则，由于我们使用的是两个扩展的电源，因此每个 bin 中的元素必须保持在同一索引中，或者以新表中两个偏移的功率移动。
  2. final Node<K,V>[] resize() {
  3.         Node<K,V>[] oldTab = table;
  4.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  5.         int oldThr = threshold;
  6.         int newCap, newThr = 0;
  7.         if (oldCap > 0) {
  8.             if (oldCap >= MAXIMUM_CAPACITY) {
  9.                 threshold = Integer.MAX_VALUE;
  10.                 return oldTab;
  11.             }
  12.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  13.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  14.                 // oldThr*2
  15.                 newThr = oldThr << 1; 
  16.         }
  17.         else if (oldThr > 0) // initial capacity was placed in threshold
  18.             newCap = oldThr;
  19.         else {               // zero initial threshold signifies using defaults
  20.             newCap = DEFAULT_INITIAL_CAPACITY;
  21.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  22.         }
  23.         if (newThr == 0) {
  24.             float ft = (float)newCap * loadFactor;
  25.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  26.                       (int)ft : Integer.MAX_VALUE);
  27.         }
  28.         threshold = newThr;
  29.         @SuppressWarnings({"rawtypes","unchecked"})
  30.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  31.         table = newTab;
  32.         //上面是做hash表的长度拓展
  33.         //下面是如何迁移数据
  34.         if (oldTab != null) {
  35.             // 循环遍历哈希表的每个不为null的桶
  36.             // 注意，这里是"++j"，略过了oldTab[0]的处理
  37.             for (int j = 0; j < oldCap; ++j) {
  38.                 Node<K,V> e;
  39.                 if ((e = oldTab[j]) != null) {
  40.                     oldTab[j] = null;
  41.                     // 若只有一个结点，则原地存储
  42.                     if (e.next == null)
  43.                         newTab[e.hash & (newCap - 1)] = e;
  44.                     else if (e instanceof TreeNode)
  45.                         // 如果是红黑树，则执行split拆分
  46.                         // 拆分过程中，如果新的红黑树长度小于等于 6 , 则红黑树就会退化成链表
  47.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  48.                     else { // preserve order
  49.                         // "lo"前缀的代表要在原桶上存储，"hi"前缀的代表要在新桶上存储
  50.                         // loHead代表是链表的头结点，loTail代表链表的尾结点
  51.                         Node<K,V> loHead = null, loTail = null;
  52.                         Node<K,V> hiHead = null, hiTail = null;
  53.                         Node<K,V> next;
  54.                         do {
  55.                             next = e.next;
  56.                             if ((e.hash & oldCap) == 0) {
  57.                                 // 有序插入，即依次将原链表的结点追加到当前链表的末尾
  58.                                 if (loTail == null)
  59.                                     loHead = e;
  60.                                 else
  61.                                     loTail.next = e;
  62.                                 loTail = e;
  63.                             }
  64.                             else {
  65.                                 if (hiTail == null)
  66.                                     hiHead = e;
  67.                                 else
  68.                                     hiTail.next = e;
  69.                                 hiTail = e;
  70.                             }
  71.                         } while ((e = next) != null);
  72.                         if (loTail != null) {
  73.                             loTail.next = null;
  74.                             newTab[j] = loHead;
  75.                         }
  76.                         if (hiTail != null) {
  77.                             hiTail.next = null;
  78.                             // 需要搬迁的结点，新下标为从当前下标往前挪oldCap个距离。
  79.                             newTab[j + oldCap] = hiHead;
  80.                         }
  81.                     }
  82.                 }
  83.             }
  84.         }
  85.         return newTab;
  86.     }

remove方法

源码

  1. /**
  2. * 从HashMap中删除掉指定key对应的键值对，并返回被删除的键值对的值
  3. * 如果返回空，说明key可能不存在，也可能key对应的值就是null
  4. * 如果想确定到底key是否存在可以使用containsKey方法
  5. */ 
  6.    public V remove(Object key) {
  7.         Node<K,V> e;
  8.         return (e = removeNode(hash(key), key, null, false, true)) == null ?
  9.             null : e.value;
  10.     }
  12.     /**
  13.      * 方法为final，不可被覆写，子类可以通过实现afterNodeRemoval方法来增加自己的处理逻辑（解析中有描述）
  14.      *
  15.      * @param hash key的hash值，该值是通过hash(key)获取到的
  16.      * @param key 要删除的键值对的key
  17.      * @param value 要删除的键值对的value，该值是否作为删除的条件取决于matchValue是否为true
  18.      * @param matchValue 如果为true，则当key对应的键值对的值equals(value)为true时才删除；否则不关心value的值
  19.      * @param movable 删除后是否移动节点，如果为false，则不移动
  20.      * @return 返回被删除的节点对象，如果没有删除任何节点则返回nul
  21.      */
  22.     final Node<K,V> removeNode(int hash, Object key, Object value,
  23.                                boolean matchValue, boolean movable) {
  24.         Node<K,V>[] tab; Node<K,V> p; int n, index;
  26.     /*
  27.      * 如果 节点数组tab不为空、数组长度n大于0、根据hash定位到的节点对象p（该节点为 树的根节点 或 链表的首节点）不为空
  28.      * 需要从该节点p向下遍历，找到那个和key匹配的节点对象
  29.      */
  30.         if ((tab = table) != null && (n = tab.length) > 0 &&
  31.             (p = tab[index = (n - 1) & hash]) != null) {
  32.             Node<K,V> node = null, e; K k; V v;
  33.             // 如果当前节点的键和key相等，那么当前节点就是要删除的节点，赋值给node
  34.             if (p.hash == hash &&
  35.                 ((k = p.key) == key || (key != null && key.equals(k))))
  36.                 node = p;
  37.             /*
  38.          * 到这一步说明首节点没有匹配上，那么检查下是否有next节点
  39.          * 如果没有next节点，就说明该节点所在位置上没有发生hash碰撞, 就一个节点并且还没匹配上，也就没得删了，最终也就返回null了
  40.          * 如果存在next节点，就说明该数组位置上发生了hash碰撞，此时可能存在一个链表，也可能是一颗红黑树
  41.          */
  42.             else if ((e = p.next) != null) {
  43.                 // 如果是红黑树
  44.                 if (p instanceof TreeNode)
  45.                     node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  46.                 // 如果是链表，循环遍历查找
  47.                 else {
  48.                     do {
  49.                         if (e.hash == hash &&
  50.                             ((k = e.key) == key ||
  51.                              (key != null && key.equals(k)))) {
  52.                             node = e;
  53.                             break;
  54.                         }
  55.                         p = e;
  56.                     } while ((e = e.next) != null);
  57.                 }
  58.             }
  59.             /*
  60.          * 如果node不为空，说明根据key匹配到了要删除的节点
  61.          * 如果不需要对比value值  或者  需要对比value值但是value值也相等
  62.          * 那么就可以删除该node节点了
  63.          */
  64.             if (node != null && (!matchValue || (v = node.value) == value ||
  65.                                  (value != null && value.equals(v)))) {
  66.                 // 如果该节点是个TreeNode对象，说明此节点存在于红黑树结构中，调用removeTreeNode方法（该方法单独解析）移除该节点
  67.                 if (node instanceof TreeNode)
  68.                     ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  69.                 // 如果该节点不是TreeNode对象，node == p 的意思是该node节点就是首节点
  70.                 else if (node == p)
  71.                     // 由于删除的是首节点，那么直接将节点数组对应位置指向到第二个节点即可
  72.                     tab[index] = node.next;
  73.                 else
  74.                     // 如果node节点不是首节点，此时p是node的父节点，由于要删除node，所有只需要把p的下一个节点指向到node的下一个节点即可把node从链表中删除了
  75.                     p.next = node.next;
  76.                 // HashMap的修改次数递增
  77.                 ++modCount;
  78.                 // HashMap的元素个数递减
  79.                 --size;
  80.                 // 调用afterNodeRemoval方法，该方法HashMap没有任何实现逻辑，目的是为了让子类根据需要自行覆写
  81.                 afterNodeRemoval(node);
  82.                 return node;
  83.             }
  84.         }
  85.         return null;
  86.     }

get 方法

步骤

先根据key计算hash值，进一步计算得到哈希table的目标index，若此bucket上为红黑树，则再红黑树上查找，若不是红黑树，遍历链表。

源码

  1.     public V get(Object key) {
  2.         Node<K,V> e;
  3.         return (e = getNode(hash(key), key)) == null ? null : e.value;
  4.     }
  6.     final Node<K,V> getNode(int hash, Object key) {
  7.         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  8.         // 根据哈希表的下标【(n - 1) & hash】来找到对应的桶
  9.         if ((tab = table) != null && (n = tab.length) > 0 &&
  10.             (first = tab[(n - 1) & hash]) != null) {
  11.             // always check first node
  12.             // 判断桶的hash以及key都一样，则返回该桶
  13.             if (first.hash == hash && 
  14.                 ((k = first.key) == key || (key != null && key.equals(k))))
  15.                 return first;
  16.             // 如果发生hash碰撞则通过链表查找
  17.             if ((e = first.next) != null) {
  18.                 if (first instanceof TreeNode)
  19.                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  20.                 do {
  21.                     if (e.hash == hash &&
  22.                         ((k = e.key) == key || (key != null && key.equals(k))))
  23.                         return e;
  24.                 } while ((e = e.next) != null);
  25.             }
  26.         }
  27.         return null;
  28.     }

线程安全

HashMap是线程不安全的，因为HashMap不是线程同步的操作。

问题

  1. 在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
  2. 在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

解决方法

Way1. 将Map转为包装类

  1. Map<String, Integer> oMap = new HashMap<>();
  2. // ...
  3. // 转为线程安全的map
  4. Map<String, Integer> sMap = Collections.synchronizedMap(oMap);

Way2. ConcurrentHashMap

ConcurrentHashMap 是Java并发包中提供的一个线程安全且高效的 HashMap 实现。

  1. Map<String, Integer> cMap = new ConcurrentHashMap<>();
  2. cMap.put("test001", 1);
  3. cMap.put("test002", 2);
  4. System.out.println(cMap.get("test001"));

总结

基于JDK 1.8 分析总结

  1. 结构：数组（hash表）+ 链表+ 红黑树（链表长度大于等于8，且hashmap长度大于等于64）
  2. put采用的是尾插法，避免了之前的闭环风险
  3. 扩容是当前长度2倍
  4. 重写equls时，必须重写hashCode
  5. 不是线程安全的，并发时可能会导致数据覆盖（数据丢失）

  6. 参考