HashMap

【java】HashMap 一遍就懂！！！！_疯-CSDN博客_hashmap)

增

  1. V    put(K key, V value)
  2. void    putAll(Map<? extends K,? extends V> m)

删

  1. V    remove(Object key) //从该地图中删除指定键的映射（如果存在）。
  2. boolean    remove(Object key, Object value) //仅当指定的key当前映射到指定的value时删除该条目。

改

  1. oldV    replace(K key, V value) //只有当目标映射到某个value时，才能替换指定key的条目。
  2. boolean    replace(K key, V oldValue, V newValue)//仅当当前映射到指定的值时，才能替换指定键的条目。

查

  1. V    get(Object key) //返回到指定键所映射的值，或 null如果此映射包含该键的映射。
  2. V    getOrDefault(Object key, V defaultValue)//返回到指定键所映射的值，或 defaultValue如果此映射包含该键的映射。
  3. boolean    containsKey(Object key) //如果此映射包含指定键的映射，则返回 true 。
  4. boolean    containsValue(Object value) //如果此地图将一个或多个键映射到指定值，则返回 true 。
  5. Set<K>    keySet() //返回此地图中包含的键的Set视图。
  6. Collection<V>    values()//返回此地图中包含的值的Collection视图。

知识讲解

1.JDK1.7和jdk1.8对于HashMap的变化

JDK1.8之前由链表+数组组成 数组是hashMap主体，链表（拉链法）用于解决哈希冲突

JDK1.8之后加入了红黑树 当链表长度大于阈值（默认为8） 或者数组长度大于64，链表转换红黑树，加快搜索速度

2.hashMap的实现原理

首先有一个每个元素都是链表的数组，当添加一个元素（key-value）时，就首先计算元素 key 的 hash 值，以此确定插入数组中的位置，但是可能存在同一 hash 值的元素已经被放在数组同一位置了，这时就添加到同一 hash 值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的 Hash 值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树**，这样大大提高了查找的效率。

HashMap 可以存 null 键和 null 值，不保证元素的顺序恒久不变，通过 hashCode () 方法和 equals 方法保证键的唯一性。

Java实现（hashCode和equals）

  1. Hash值，对于每一个对象，通过其 hashCode () 方法可为其生成一个整形值（散列码）。、
    （所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。）

    1. /**这是一个神奇的函数，用了很多的异或，移位等运算
    2. 对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/
    3. final int hash(Object k) {
    4.      int h = hashSeed;
    5.      if (0 != h && k instanceof String) {
    6.          return sun.misc.Hashing.stringHash32((String) k);
    7.      }
    9.      h ^= k.hashCode();
    11.      h ^= (h >>> 20) ^ (h >>> 12);
    12.      return h ^ (h >>> 7) ^ (h >>> 4);
    13.  }

  1. 该hash整型值通过hash函数扰动处理后，然后通过 (n - 1) & hash将会作为数组下标。

  2. 当 HashMap 中插入值或查询值对应的散列码与数组中的散列码相等时，则会通过 equals 方法比较 key 值是否相等。

  3. 如果相同的话，直接覆盖，不相同就通过拉链法解决冲突

使用 HashMap，如果 key 是自定义的类，就必须重写 hashcode () 和 equals ()。自定义的类的 hashcode () 方法继承于 Object 类，其 hashcode 码为默认的内存地址，这样即便有相同含义的两个对象，比较也是不相等的，例如，生成了两个 Student A对象，正常理解这两个对象应该是相等的，但如果你不重写 hashcode（）方法的话，比较是不相等的！

如果只重写 hashcode () 不重写 equals () 方法，当比较 equals () 时只是看他们是否为同一对象（即进行内存地址的比较，因为equal方法默认实现还是==，而==是比较内存地址的），两个对象还是不同的，因为地址不同。

  1.     static final int hash(Object key) {
  2.       int h;
  3.       // key.hashCode()：返回散列值也就是hashcode
  4.       // ^ ：按位异或
  5.       // >>>:无符号右移，忽略符号位，空位都以0补齐
  6.       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  7.   }
  9. 由于取数组下标的时候，n-1 & hash, 只有hash的低n位（一般是16）被使用 将hash高16位和低16位异或，这样能让hash所有位都参与进来。

基本结构的源码分析

Map - 图1

1.容量，默认16

HashMap的容量需要保证是 2的n次幂，声明大小如果不为2的n次幂，HashMap会调用函数把容量设定为刚刚大于指定大小的2的n次幂。（比如设定容量为1000，HashMap会设定为1024）

为什么呢？

获取数组下标的时候，是通过 hash值跟长度取模来获得数组的下标，因为取模操作非常耗时，所以java采用的 hashcode &(length-1) 的方式：

Map - 图2

二进制全部是1，与运算得到的全是本身的值。与hash值与运算，得到的hash值的后n的二进制。这样就可以把元素的hash值的后n位作为数组下标。同时这样也有利于扩容时数据移动，后面会展开。

HashMap为什么长度是2的幂次方？

HashMap 中的tableSizeFor()方法保证长度是2的幂次方。

hash值的范围是[-2^31 ~ 2^31 - 1],数组不能放下，取hash后n位（n - 1） & hash 作为数组下标。 n肯定是2的幂次方，这样才能元素的hash值的后n位作为数组下标。

2.loadFactor负载因子（填充比），默认0.75

loadFactor 加载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。

loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

threshold = capacity * loadFactor，当 Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。

3.树形化

Map - 图3

链表长度大于8 的时候就会调用 treeifyBin方法转化为红黑树，但是在treeifyBin方法内部却有一个判断，当只有数组长度大于64 的时候，才会进行树形化，否则就只是resize扩容。

因为链表过长而数组过短，会经常发生 hash碰撞，这个时候树形化其实是治标不治本，因为引起链表过长的根本原因是数组过短。所以执行树形化之前，会先检查数组长度，如果长度小于 64，则对数组进行扩容，而不是进行树形化。

因此，真正发生树形化的时候，是数组长度大于64并且链表长度大于8 的时候才会发生的。

3.Put函数

HashMap 只提供了 put 用于添加元素，putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用。

对 putVal 方法添加元素的分析如下：

    1. if ((tab = table) == null || (n = tab.length) == 0)
    2.          n = (tab = resize()).length;

  2. 如果定位到的数组位置有元素就和要插入的 key 比较，如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

    1.  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    2.                 boolean evict) {
    3.      Node<K,V>[] tab; Node<K,V> p; int n, i;
    5.      //延迟初始化，第一次调用putVal会初始化hashMap对象中最耗费内存的散列表。
    6.          if ((tab = table) == null || (n = tab.length) == 0)
    7.              n = (tab = resize()).length;
    9.      //定位到的数组位置没有元素，插入一个新建的节点
    10.      if ((p = tab[i = (n - 1) & hash]) == null)
    11.                  tab[i] = newNode(hash, key, value, null);
    12.       else {
    13.                  //e不为null，就代表当前找到了一个与当前插入元素key相同的元素
    14.                  Node<K,V> e; K k; 
    16.                  //如果找到了相同key的元素
    17.                  if (p.hash == hash &&
    18.                      ((k = p.key) == key || (key != null && key.equals(k))))
    19.                      e = p;
    21.                  //没有找到相同key，但是当前的节点已经树化了
    22.                  else if (p instanceof TreeNode)
    23.                      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    25.                  //桶中的元素和插入的元素key不一致
    26.                  else {
    27.                      for (int binCount = 0; ; ++binCount) {
    29.                         // 如果当前桶中的链表都没有插入的元素，新建一个节点插入到链表末尾
    30.                          if ((e = p.next) == null) {
    31.                              p.next = newNode(hash, key, value, null);
    33.                           //如果链表的长度达到了Treeify——threshold，进行树化
    34.                              if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    35.                                  treeifyBin(tab, hash);
    36.                              break;
    37.                          }
    39.                          //如果当前桶的链表中找打了相同key的元素，进行后续操作
    40.                          if (e.hash == hash &&
    41.                              ((k = e.key) == key || (key != null && key.equals(k))))
    42.                              break;
    43.                          p = e;
    44.                      }
    45.                  }
    47.                  //如果找到了相同key的元素
    48.                  if (e != null) { // existing mapping for key
    49.                      //进行覆盖
    50.                      V oldValue = e.value;
    51.                      if (!onlyIfAbsent || oldValue == null)
    52.                          e.value = value;
    53.                      afterNodeAccess(e);
    54.                      //返回之前的值
    55.                      return oldValue;
    56.                  }
    57.              }
    58.      //散列表结构被修改的次数 符合fast-fail机制（线程不安全）
    59.      ++modCount;
    61.     // 如果触发了扩容机制，threshold就是默认数组大小或者自定义的（2的幂次方）数组大小，进行数组扩容
    63.      if (++size > threshold)
    64.          resize();
    65.      afterNodeInsertion(evict);
    66.      return null;
    67.  }

Map - 图4

4.扩容机制Resize

  1. final Node<K,V>[] resize() {
  2.    // oldCap触发扩容之前的table数组长度
  3.     //oldThr触发之前的阈值
  4.     //oldTab触发扩容之前的哈希表
  5.     Node<K,V>[] oldTab = table;
  6.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  7.     int oldThr = threshold;
  8.         int newCap, newThr = 0;
  10.    // 设置扩容之后的数组大小newCap 和 新的扩容阈值newThr
  11.     odlCap>0 代表哈希表已经初始化一次了
  12.     if (oldCap > 0) {’
  14.        ///// 扩容之前的数组大小已经达到了最大容量，就不扩容，设置扩容条件是最大阈值
  15.         if (oldCap >= MAXIMUM_CAPACITY) {
  16.             threshold = Integer.MAX_VALUE;
  17.             return oldTab;
  18.         }
  20.        // 如果扩容后的大小<最大容量，设置扩容阈值和数组大小委员来两倍。赋值给newCap 
  21.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  22.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  23.             newThr = oldThr << 1; // double threshold
  24.     }
  26.    //    初次进行散列表的初始化（new hashmap（capacity））
  27.     else if (oldThr > 0) // initial capacity was placed in threshold
  28.         newCap = oldThr;
  30.    ///// 初始化散列表，但是没有传入表容量hashmap（）
  31.     else {               // zero initial threshold signifies using defaults
  32.         newCap = DEFAULT_INITIAL_CAPACITY;//16
  33.         设置扩容阈值是 16 * 0.75 = 12
  34.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  35.     }
  37.   // 初次进行散列表的初始化（new hashmap（capacity））时，设置扩容阈值= 传入值 * loadFactor
  38.     if (newThr == 0) {
  39.         float ft = (float)newCap * loadFactor;
  40.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  41.                   (int)ft : Integer.MAX_VALUE);
  42.     }
  44.     threshold = newThr;
  46.     //扩容成一个更大的数组，要重新计算所有元素的下标  e.hash & (newCap - 1)
  47.     @SuppressWarnings({"rawtypes","unchecked"})
  48.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  49.     table = newTab;
  50.     if (oldTab != null) {
  51.         for (int j = 0; j < oldCap; ++j) {
  52.             Node<K,V> e;
  53.             if ((e = oldTab[j]) != null) {
  54.                 //去除oldTab的头节点，添加到newTab中
  55.                 oldTab[j] = null;
  56.                 if (e.next == null)
  57.                     newTab[e.hash & (newCap - 1)] = e;
  58.                 else if (e instanceof TreeNode)
  59.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  60.                 //桶位形成了链表
  61.                 //需要把桶位拆成高链 和低链
  62.                 //低链 hashCode 为 0xxxx 的元素
  63.                 //高链 hashCode 为 1xxxx 的元素
  64.                 else { // preserve order
  65.                     Node<K,V> loHead = null, loTail = null;
  66.                     Node<K,V> hiHead = null, hiTail = null;
  67.                     Node<K,V> next;
  68.                     do {
  69.                         next = e.next;
  71.                         if ((e.hash & oldCap) == 0) {
  72.                             if (loTail == null)
  73.                                 loHead = e;
  74.                             else
  75.                                 loTail.next = e;
  76.                             loTail = e;
  77.                         }
  78.                         else {
  79.                             if (hiTail == null)
  80.                                 hiHead = e;
  81.                             else
  82.                                 hiTail.next = e;
  83.                             hiTail = e;
  84.                         }
  85.                     } while ((e = next) != null);
  87.                     //把低位链表放到新的hashMap里面
  88.                     if (loTail != null) {
  89.                         loTail.next = null;
  90.                         newTab[j] = loHead;
  91.                     }
  93.                     //把高位链表放到新的hashMap里面
  94.                     if (hiTail != null) {
  95.                         hiTail.next = null;
  96.                         newTab[j + oldCap] = hiHead;
  97.                     }
  98.                 }
  99.             }
  100.         }
  101.     }
  102.     return newTab;
  103. }

5.get方法

  1. public V get(Object key) {
  2.         Node<K,V> e;
  3.         return (e = getNode(hash(key), key)) == null ? null : e.value;
  4.     }
  6. 跳到getNode里面
  9.     parameter： first ： 桶位的头元素
  10.                 e： 临时node元素
  11.                 n： table 长度
  12.                 tab： 引用当前的hashMap散列表
  13.     final Node<K,V> getNode(int hash, Object key) {
  14.         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  15.         if ((tab = table) != null && (n = tab.length) > 0 &&
  16.             (first = tab[(n - 1) & hash]) != null) {
  17.             //返回链表的头节点
  18.             if (first.hash == hash && // always check first node
  19.                 ((k = first.key) == key || (key != null && key.equals(k))))
  20.                 return first;
  21.             //如果当前桶位有树或者链表
  22.             if ((e = first.next) != null) {
  23.                 if (first instanceof TreeNode)
  24.                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  25.                 do {
  26.                     //得到链表中的节点
  27.                     if (e.hash == hash &&
  28.                         ((k = e.key) == key || (key != null && key.equals(k))))
  29.                         return e;
  30.                 } while ((e = e.next) != null);
  31.             }
  32.         }
  33.         return null;
  34.     }

6.hashMap的尾部遍历

尾部遍历，正常链表插入到尾部，需要遍历到尾部。这样每次插入就遍历了一次链表，事件复杂度大大升高

因此使用头部插入的方式

  1. 1 2 3 4
  2. 插入循序
  3.     1
  4.     2 1
  5.     3 2 1
  6.     4 3 2 1

然而，在jdk1.7之前，采用队头插入的方式会导致多线程环境下的死循环问题

jdk1.8之后，加入了tail指针，即避免了尾部遍历，又避免了死循环问题

7.红黑树引入

二叉搜索树:

  • 结合了二分查找和链表的特性。
  • 特殊情况下会退化为链表

AVL树：

  • 自平衡的二叉搜索树
  • 每个节点的左子树和右子树高度差至少为1
  • 由于上述条件，每次插入删除节点时，都要进行左旋、右旋操作，让平衡树的性能降低

红黑树

Map - 图5

由于性质5，每一个节点的左子树和右子树的黑节点的层数是相同的，所以我们叫红黑树为黑色完美平衡树

红黑树自平衡

主要操作有：

  1. 变色：红变黑或者黑变红

  2. 左旋：找到一个基准节点，把右子节点作为新基准节点，原基准节点作为原来右子节点的左子节点； 原右子节点的左子节点作为原基准点的右子节点
    Map - 图6

  3. 右旋： 找一个基准节点，把左子节点作为新的基准节点。原基准节点作为原左子节点的右子节点；原左子节点的右子节点作为原基准节点的左子节点，
    Map - 图7

红黑树查找和二叉搜索树相同

红黑树插入：

  1. 查找插入的位置（和搜索树相同）

    • 黑色插入会破坏红黑树的平衡性（性质4）， 红色插入可能会破坏性质3，可能不会
  2. 自平衡

插入情景1：插入节点的key已经存在

直接覆盖原值

插入情景2：插入节点的父节点是黑色

直接插入，不影响完美黑平衡

插入情景3：插入节点的父节点是红色

父节点肯定不是根节点，祖父节点肯定是黑节点，这时候要讨论三种情况：

插入情景3.1：叔父节点存在、红节点
  1. 把父亲节点和叔父节点更改为黑色，爷爷节点更改为红色

Map - 图8

插入情景3.2：叔父节点不存在或者是黑色 并且 父节点为祖父节点的左子节点

插入情景3.2.1：当前节点插入为左子节点
  1. **将黑红红改变为红黑红**
  1. 由于此时黑色不平衡，需要进行右旋。

Map - 图9

插入情景3.2.2：当前节点插入为右子节点

  1. 进行左旋，出现LL双红的情况

  2. 和3.2.1相同，变为红黑红

  3. 右旋
    Map - 图10

插入情景3.3： 叔父节点不存在或者是黑色 ，并且父节点为祖父节点的右子节点

插入情景3.3.1: 当前节点为父节点的左子节点

  1. ll右旋

  2. 黑红红-》红黑红

  3. 左旋pp节点
    Map - 图11

插入情景3.3.2： 当前节点为父节点的右子节点
  1. 黑红红-》红黑红
  2. 左旋pp节点

Map - 图12

插入实例

插入发现，父节点是红色，LL双红并且叔父节点存在并且双黑，先变颜色。

发现5和15节点LR双红，叔父节点存在为单黑，当前节点15是父节点5的右子节点，符合情景3.2.2

左旋5，得到15 和5 LL双红，变颜色。

右旋19，最终得到完美黑平衡树

Map - 图13

8.hashMap的线程安全问题

ConcurrentHashMap

资料来源

并发编程板块

ConcurrentHashMap1.7

Map - 图14

Java 7 中 ConcurrentHashMap 的存储结构如上图，ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

TreeMap

  1. public class TreeMap<K,V>
  2.     extends AbstractMap<K,V>
  3.     implements NavigableMap<K,V>, Cloneable, java.io.Serializable

表示TreeMap

NavigableMap（更多）则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法

底层数据结构

TreeMap底层就是红黑树

TreeMap定义了Entry 的内部类 和 红黑两种颜色定义

put

主要就两步

  • 构建排序二叉树

  1. 如果节点为空，创建节点

  2. 不为空

    1. 指定comparator存在，将当前值和父节点比较，记录父节点parent

      1. 小于则进入左子节点
      2. 大于进入有右子节点
      3. 等于更新值
    2. 不存在，按照默认排序

  3. 创建节点，并把节点放在之前指定的位置上

  4. 进行红黑树的自平衡fixAfterInsertion（E e）

    • 平衡二叉树

  1.   1. 将新增节点染成红色
  2.   2. 如果当前节点的父节点P是红色
  4.      1. 如果P位于祖父节点G的左子节点
  6.         1. 如果新增节点R是P的左子节点
  8.            1. 黑红红变为红黑红
  9.            2. G右旋
  10.         2. 如果新增节点R是P的右子节点
  12.            1. P左旋（变成第一种情况）
  13.            2. 黑红红变为红黑红
  14.            3. G右旋
  15.      2. 相反情况也相反

红黑树delete