键值对Map

一.Map 介绍

1.什么是 map?

在编程语言中，Map 集合通常是指一种实现了 Map 数据结构的容器类或数据类型。Map 集合中可以存储键值对，每个键都是唯一的，而值可以重复。Map 集合也被称为关联数组、字典或哈希表等。在 java 中称为 Map,在 python 中称为字典.

Map 集合通常提供了一些方法，例如插入元素、删除元素、查找元素等。在 Java 中，Map 集合是一个接口，它有多个实现类，例如 HashMap、TreeMap、LinkedHashMap 等。在 Python 中，Map 集合的实现包括字典（dictionary）和有序字典（ordered dictionary）等。在 C++中，Map 集合是通过 STL 库中的 map 类实现的。

Map 集合常用于存储和管理大量键值对的数据，例如在 Web 开发中，Map 集合可以用来存储 HTTP 请求的参数和对应的值；在游戏开发中，Map 集合可以用来存储游戏对象的属性和状态等。

2.Map 类图结构

在 Java 中，常见的 Map 有以下几种：

1. HashMap：基于哈希表实现，可以支持 null 键和 null 值，不保证元素的顺序。
   
2. TreeMap：基于红黑树实现，可以自动按键排序，但不能存储 null 键。
   
3. LinkedHashMap：基于哈希表实现，可以按照插入顺序或访问顺序迭代元素。
   
4. Hashtable：基于哈希表实现，与 HashMap 类似，但是它是线程安全的，不支持 null 键或 null 值。
   
5. ConcurrentHashMap：基于分段锁实现的哈希表，可以支持高并发，不支持 null 键或 null 值。
   

3.HashMap 的数据结构？

HashMap 本质是一个定长的数组，数组中存放链表，HashMap 在 jdk1.8 的源码如下图

static class Node<K,V> implements Map.Entry<K,V> {

       final int hash;

       final K key;

       V value;

       Node<K,V> next;

       Node(int hash, K key, V value, Node<K,V> next) {

           this.hash = hash;

           this.key = key;

           this.value = value;

           this.next = next;

       }

}

当向 HashMap 中 put 值时，会首先通过 hash 函数计算出数组的位置，比如索引值为 i，将其放到 entry[i]的位置，如果当前位置有元素了，会插在这个元素的前面（jdk1.7 头插法，jdk1.8 尾插法），最先加入的元素在链表尾部。比如第一个键值对 a 通过 hash 得到数组的索引为 index=0，键值对 b 也计算 index=0，则 b.next=a,entry[0]=b;这样 index=0 的位置存放了 b，a 两个键值对，是用链表关联的。也就是说数组中存储的是最后插入的元素。

构造函数:

//构造一个具有默认初始容量 (16) 和默认负载因子 (0.75) 的空 HashMap

HashMap()

//构造一个带指定初始容量和默认负载因子 (0.75) 的空 HashMap

HashMap(int initialCapacity)

//构造一个带指定初始容量和负载因子的空 HashMap

HashMap(int initialCapacity, float loadFactor)

Node 节点:

static class Node<K,V> implements Map.Entry<K,V> {

   // 哈希码，用来查找位置以及比对元素是否相同

   final int hash;

   // 键

   final K key;

   // 值

   V value;

   // 指向下一个结点

   Node<K,V> next;

   Node(int hash, K key, V value, Node<K,V> next) {

       this.hash = hash;

       this.key = key;

       this.value = value;

       this.next = next;

   }

   public final K getKey()        { return key; }

   public final V getValue()      { return value; }

   public final String toString() { return key + "=" + value; }

   // 重写了 hashCode， ^ 是位异或运算符

   public final int hashCode() {

       return Objects.hashCode(key) ^ Objects.hashCode(value);

   }

   public final V setValue(V newValue) {

       V oldValue = value;

       value = newValue;

       return oldValue;

   }

   // 重写 equals() 方法

   public final boolean equals(Object o) {

       if (o == this)

           return true;

       if (o instanceof Map.Entry) {

           Map.Entry<?,?> e = (Map.Entry<?,?>)o;

           if (Objects.equals(key, e.getKey()) &&

               Objects.equals(value, e.getValue()))

               return true;

       }

       return false;

   }

}

TreeNode节点:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

   // 父节点

   TreeNode<K,V> parent;

   // 左节点

   TreeNode<K,V> left;

   // 右节点

   TreeNode<K,V> right;

   TreeNode<K,V> prev;

   // 判断颜色，默认红色

   boolean red;

   TreeNode(int hash, K key, V val, Node<K,V> next) {

       super(hash, key, val, next);

   }

   // 返回根节点

   final TreeNode<K,V> root() {

       for (TreeNode<K,V> r = this, p;;) {

           if ((p = r.parent) == null)

               return r;

           r = p;

       }

4.HashMap 中的常量?

// 序列化自动生成的一个码，用来在正反序列化中验证版本一致性。

private static final long serialVersionUID = 362498820763181265L;

// 默认的初始容量 1 * 2^4 = 16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 最大容量 1 * 2^30

static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的加载因子 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 桶的树化阈值，当桶(bucket)上的结点数大于这个值时会转成红黑树，

// 也就是上面提到的长度大于阈值（默认为8）时，将链表转化为红黑树

static final int TREEIFY_THRESHOLD = 8;

// 桶的链表还原阈值，当桶(bucket)上的结点数小于这个值时树转链表

// 一个道理

static final int UNTREEIFY_THRESHOLD = 6;

// 最小树形化容量阈值，当哈希表中的容量 > 该值时，才允许树形化链表

// 否则，若桶内元素太多时，则直接扩容，而不是树形化

// 为了避免进行扩容和树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD

static final int MIN_TREEIFY_CAPACITY = 64;

// 存储元素的数组，总是2的幂次倍

transient Node<k,v>[] table;

// 存放具体元素的集

transient Set<map.entry<k,v>> entrySet;

// 存放元素的个数（不是数组的长度）

transient int size;

// 扩容和修改的计数变量

transient int modCount;

// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容

int threshold;

// 加载因子

final float loadFactor;

其中有几个需要强调的内容

threshold 临界值

• 数组扩容的一个临界值，即当数组实际大小（容量 _ 填充因子，即：threshold = capacity _ loadFactor）超过临界值时，会进行扩容。
  

loadFactor 加载因子

• 加载因子就是表示哈希表中元素填满的程度，当表中元素过多，超过加载因子的值时，哈希表会自动扩容，一般是一倍，这种行为可以称作 rehashing（再哈希）。
  
• 加载因子的值设置的越大，添加的元素就会越多，确实空间利用率的到了很大的提升，但是毫无疑问，就面临着哈希冲突的可能性增大，反之，空间利用率造成了浪费，但哈希冲突也减少了，所以我们希望在空间利用率与哈希冲突之间找到一种我们所能接受的平衡，经过一些试验，定在了 0.75f。
  

5.put 方法实现原理？

构造方法的时候并没有初始化，而是在第一次 put 的时候初始化

jdk1.7 采用的是数组+链表的方式

jdk1.8 采用的是数组+链表/红黑树


put 方法源码分析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

              boolean evict) {

 // jdk1.8中HashMap底层数据结构使用的是Node

 Node<K,V>[] tab; Node<K,V> p; int n, i;

 // 如果table还未初始化，则初始化table，注意这里初始化使用的是resize函数[扩容函数]

 if ((tab = table) == null || (n = tab.length) == 0)

   n = (tab = resize()).length;

 /**

        * 这里表示如果tab[i]位置上为null，则直接插入数据

        * i=(n-1)&hash与jdk1.7中找出元素在tab上的index是一样的操作

        * 注意这里在多线程环境下会造成线程不安全问题

        */

 if ((p = tab[i = (n - 1) & hash]) == null)

   tab[i] = newNode(hash, key, value, null);

 else {// 如果i位置上有元素，则进行链式存储

   Node<K,V> e; K k;

   // 如果tab[i]上的元素与插入元素的key完全一样，则进行覆盖操作

   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) {

       // 如果p节点的next为空，则将待插入的元素，直接添加在链表尾

       if ((e = p.next) == null) {

         // 从这里可知道jdk1.8在，如果存在链表，插入数据是直接放在链表尾的

         p.next = newNode(hash, key, value, null);

         // 当同一节点链表中元素个数>=8时，底层数据结构转向红黑树，

         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

           treeifyBin(tab, hash);  // 将底层数据结构转向红黑树

         break;

       }

       // 判断next元素是否和插入元素相同，如果相同，则不做操作，跳出循环

       if (e.hash == hash &&

           ((k = e.key) == key || (key != null && key.equals(k))))

         break;

       p = e; // 将next赋值给p，继续循环

     }

   }

   // 覆盖操作

   if (e != null) { // existing mapping for key

     V oldValue = e.value;

     // onlyIfAbsent表示是否要改变原来的值，true-不改变，false-改变

     if (!onlyIfAbsent || oldValue == null)

       e.value = value;

     afterNodeAccess(e);

     return oldValue;

   }

 }

 // 修改次数加1，fail-fast机制

 ++modCount;

 // 判断是否需要扩容

 if (++size > threshold)

   resize();

 afterNodeInsertion(evict);

 return null;

}

6.put 方法的 hash 函数？

static final int hash(Object key) {

       int h;

       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

• key==null

• key 等于 null 时，值为 0，所以 HashMap 的 key 可以为 null，
  
• 对比 HashTable，如果 key 为 null，会抛出异常；HashTable 的 key 不可为 null
  

• key！=null

• 首先计算 HashCode 的值，再 HashCode 的值右移 16 位再和 HashCode 的值进行异或运算
  
• 此过程就是扰动函数
  
• 扰动函数原理，如果是小于 32 位，则右移 16 位后高位补零，进行异或运算后高位还是 0
  
• 如果是 32 位的，则右移 16 位后，高位补 0，原来的高位变成了低位，进行亦或运算，增加随机，均匀分布
  

7.hash 右移 16 位异或？

//jdk1.8的hash方法

static final int hash(Object key) {

 int h;

 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

//jdk1.7的hash方法

final int hash(Object k) {

 int h = hashSeed;

 // 如果使用了再次hash，并且key的类型为String,则直接使用String的hash算法返回其hash值

 if (0 != h && k instanceof String) {

   return sun.misc.Hashing.stringHash32((String) k);

 }

 // 如果走到这里h可能为0或者为1，再次异或上k的hashCode，如果h为1，表示再hash，则这里的h可能会±1，h为0的时候，h就表示k的hashCode

 h ^= k.hashCode();

 // This function ensures that hashCodes that differ only by

 // constant multiples at each bit position have a bounded

 // number of collisions (approximately 8 at default load factor).

 // 这里进行两次hash主要是为了最大可能的解决hash碰撞，防止低位不变，而高位变化时，产生hash碰撞

 h ^= (h >>> 20) ^ (h >>> 12);

 return h ^ (h >>> 7) ^ (h >>> 4);

}

1010 1010 0001 0100 1111 0101 h=11146485  大槽位

0000 0000 0000 0000 1010 1010 >>>16

1010 1010 0001 0100 0101 1111 ^ //高低位数据权重保留

1111 1111 1111 1111 1111 1111 (capitity -1)=16777215

1010 1010 0001 0100 1111 0101 &结果===11146485//高低位数据的变化影响都有保留，尽可能地离散

0000 0000 0001 0101 h=21  小槽位

0000 0000 0000 0000 >>>16

0000 0000 0001 0101 ^  21//不改变低位数据权重

0000 0000 0001 1111 (capitity -1)=31

0000 0000 0001 0101 &31结果===21

由于最终要和(length-1)进行与运算，数组的长度大多都是小于 2 的 16 次方的，高 16 位是用不到的。所以始终是 hashCode 的低 16 位参与运算，如何让高 16 位也参与运算呢，会让下标更加散列。右移 16 位后，高 16 位和低 16 位进行异或运算，增加随机性。

8.为什么用^不用&或者|?

增加随机性,较少 hash 碰撞。

如果用&操作符，得到 75%的 0，25%的 1

如果用|操作符，得到 75%的 1，25%的 0

如果用^操作符，得到 50%的 1，50%的 0，异或运算对均匀分布非常有用

9.如何计算数组下标？

put 方法是用如下方法计算下标的,实际计算公式是 hash&(length-1),length-1 的二进制是 0111111,使用&运算能快速定位到下标的位置

if ((p = tab[i = (n - 1) & hash]) == null)

       tab[i] = newNode(hash, key, value, null);

10.为什么引入红黑树？

在 jdk1.7 以前，HashMap 用的是数组+链表，如果链表越来越长，查询的时间复杂度最坏时 O(n)

为了提高查询效率，jdk1.8 使用了红黑树，查询的平均时间复杂度为 O(logn)

在 Java 中，HashMap 是一种基于哈希表实现的 Map 集合，它可以在常数时间内执行插入、删除和查找操作，因此在大多数情况下，它是使用最广泛的 Map 实现类。然而，当哈希表中的元素数量增加时，哈希冲突的概率就会增加。若哈希冲突过于频繁，HashMap 的性能将会下降。

为了解决这个问题，Java 引入了一种名为红黑树的数据结构。当哈希表中的某个桶（bucket）中的元素数量超过一定阈值（默认为 8），桶中的元素将会被转换为一棵红黑树。这样，在进行查找、插入和删除操作时，就可以利用红黑树的特性，在 O(log n)的时间复杂度内完成操作，而不是在 O(n)的时间复杂度内进行线性查找。

使用红黑树可以提高 HashMap 在高负载情况下的性能和效率，因为红黑树的高度是 O(log n)，而哈希表的平均查找时间是 O(1)。此外，红黑树还可以保证元素的有序性，这对于需要按照键排序的场景非常有用。

11.为什么变树阈值为 8？

在 jdk1.8 及以后的版本，HashMap采用的数据结构是，数组+链表/红黑树，在链表长度为 8 时,并且数组长度大于等于 64 时，开始由链表转化为红黑树。

红黑树节点的大小大概是普通节点大小的两倍，转为红黑树,牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。

阈值为什么要选 8 呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为 8 的情况，发生概率仅为 0.00000006。

//链表个数的概率

* 0:    0.60653066

* 1:    0.30326533

* 2:    0.07581633

* 3:    0.01263606

* 4:    0.00157952

* 5:    0.00015795

* 6:    0.00001316

* 7:    0.00000094

* 8:    0.00000006

* more: less than 1 in ten million

至于红黑树转回链表的阈值为什么是 6，而不是 8？是因为如果这个阈值也设置成 8，假如发生碰撞，节点增减刚好在 8 附近，会发生链表和红黑树的不断转换，导致资源浪费。

链表的时间复杂度是 O(n)，红黑树的时间复杂度是 O(logn),红黑树的时间复杂度是优于链表的。因为树节点所占空间是普通节点的 2 倍。所以当节点足够多时选择使用红黑树。也就是说，当节点比较少的时候，尽管红黑树的时间复杂度表现比链表好一些，但红黑树所占空间比链表大，综合考虑，在节点较多时，红黑树所占空间劣势相比查询性能的提升不那么明显时，转化为红黑时。

当 k=9 时，也就是发生的碰撞次数为 9 次时，概率为亿分之三，碰撞的概率已经无限接近为 0。

如果设置为 9，意味着，几乎永远都不会再次发生碰撞，换句话说，链表的长度此时为 8，要发生碰撞才会从链表变树。但永远都不会变树，因为概率太小了。因此设置为 9，实在没必要。

P(N(1)=k)=0.6065∗(0.5k)/k!

当k=0时，P= 0.6065

当k=1时，p= 0.3032

当k=2时，p= 0.0758

当k=3时，p= 0.0126

当k=4时，p= 0.0015

当k=5时，p= 0.0001

当k=6时，p= 0.000013

当k=7时，p= 0.0000009

当k=8时，p= 0.00000006

当k=9时，p= 0.000000003

12.什么是泊松分布？

泊松分布是一个离散概率分布，表示在一定时间或空间范围内，事件发生的次数符合某个平均值的概率分布。泊松分布的概率质量函数为：

P(X=k) = (λ^k * e^(-λ)) / k!

其中，X 表示事件发生的次数，k 为非负整数，λ 为事件发生的平均次数。e 为欧拉数，约等于 2.71828。

泊松分布的特点是，当事件发生的概率很小，但发生次数很多时，可以用泊松分布来描述。例如，在一定时间内，电话呼叫中心接到的电话数量、网站访问量、交通事故数量等，都可以用泊松分布来描述。

泊松分布可以用于很多领域，例如工业生产、交通管理、金融分析等。在计算机科学中，泊松分布在网络流量和负载均衡等领域也有广泛的应用。

13.转化为红黑树的条件?

如果链表的长度大于 8，一定会转化为红黑树吗？答案是不一定的

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

                  boolean evict) {

       Node<K,V>[] tab; Node<K,V> p; int n, i;

       if ((tab = table) == null || (n = tab.length) == 0)

           n = (tab = resize()).length;

       if ((p = tab[i = (n - 1) & hash]) == null)

           tab[i] = newNode(hash, key, value, null);

       else {

           Node<K,V> e; K k;

           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);

                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

                           //树化>=8-1=7,binCount从0开始的,所以实际判断链表个数>=8

                           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;

}

final void treeifyBin(Node<K,V>[] tab, int hash) {

       int n, index; Node<K,V> e;

    //第二个条件是判断数组长度是不是大于等于64,小于64,还是进行扩容

       if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

           resize();

       else if ((e = tab[index = (n - 1) & hash]) != null) {

           TreeNode<K,V> hd = null, tl = null;

           do {

               TreeNode<K,V> p = replacementTreeNode(e, null);

               if (tl == null)

                   hd = p;

               else {

                   p.prev = tl;

                   tl.next = p;

               }

               tl = p;

           } while ((e = e.next) != null);

           if ((tab[index] = hd) != null)

               hd.treeify(tab);

       }

   }

转化为红黑树的条件,先判断链表的长度是不是大于等于 8,再判断 table 数组的长度是否大于等于 64，小于 64 则扩容，大于等于 64，才转化为红黑树

14.为什么不用 AVL 树？

HashMap 查找时间复杂度:

• 在没有地址冲突时，效率 O(1)
  
• 有少量地址冲突，在冲突的地址拉链(建链表)，效率在 O(1) ~ O(logn) 之间
  
• 有大量地址冲突，在冲突的地址建红黑树，效率 O(logn)
  

AVL 树和红黑树有以下区别:

• AVL 树更加平衡，提供更快的查询速度，一般读取密集型任务，用 AVL 树。
  
• 红黑树更适合插入和修改密集型任务。
  
• 通常，AVL 树的旋转比红黑树更加复杂。
  
• AVL 以及红黑树是高度平衡的树数据结构。它们非常相似，真正的区别在于 在任何添加/删除操作时完成的旋转操作次数。
  
• 两种实现都缩放为 O(logN)，其中 N 是叶子的数量，但实际上 AVL 树在查找 密集型任务上更快:利用更好的平衡，树遍历平均更短。另一方面，插入和删除方 面，AVL 树速度较慢:需要更高的旋转次数才能在修改时正确地重新平衡数据结构。
  
• 在 AVL 树中，从根到任何叶子的最短路径和最长路径之间的差异最多为 1。在 红黑树中，差异可以是 2 倍。
  
• 两个都是 O(logn)查找，但平衡 AVL 树可能需要 O(logn)旋转，而红黑树将需要最多两次旋转使其达到平衡(尽管可能需要检查 O(logn)节点以确定旋转的位置)。旋转本身是 O(1)操作，因为你只是移动指针。
  

红黑树:适用于大量插入和删除,因为它是非严格的平衡树；只要从根节点到叶子节点的最长路径不超过最短路径的 2 倍，就不用进行平衡调节.查找效率是 O(logn),红黑树舍去了严格的平衡，使其插入，删除，查找的效率稳定在 O(logn)

AVL 树:是一种自平衡二叉搜索树。在 AVL 树中，任何节点的两个子树的高度最大差别为 1，也就是说，AVL 树中所有节点的左子树与右子树高度差的绝对值都不超过 1。AVL 允许的差值小；在进行大量插入和删除操作时，会频繁地进行平衡调整，严重降低效率；AVL 也是 O(logn);查找没问题 O(logn)，但是为了保证高度平衡，动态插入和删除的代价也随之增加，综合效率肯定达不到 O(logn)

15.HashCode 作为下标？

为什么不能用HashCode直接作为下标,原因如下:

HashCode 的值范围在-(2³¹)到 2³¹-1，HashMap 的容量范围是 16 ～ 2³⁰，HashMap 通常取不到最大值，且机器设备也无法提供这么大的数组空间，hashCode 的值可能不在 HashMap 的 index 范围内，导致无法匹配。解决方法是右移 16 位进行异或运算。

在 Java 中，HashCode 是一个用于散列算法的整数值，可以用于快速查找和比较对象。在 Map、Set 等集合类中，HashCode 被用于确定对象在集合中的位置。

然而，将 HashCode 直接作为下标存储对象可能会存在冲突的情况。因为 HashCode 是一个有限的整数值，而对象的数量是无限的，所以不同的对象可能会有相同的 HashCode 值。如果直接使用 HashCode 作为下标存储对象，就可能会导致对象被覆盖或丢失。

为了解决这个问题，Java 中的 HashMap 等集合类采用了一种称为“拉链法”的解决方案。具体来说，HashMap 内部维护了一个桶（bucket）数组，每个桶对应一个链表，相同 HashCode 的对象会被存储在同一个桶对应的链表中。当需要查找、插入或删除对象时，HashMap 会先计算对象的 HashCode 值，然后根据 HashCode 值找到对应的桶和链表，再在链表中进行操作。

通过采用拉链法，HashMap 等集合类可以有效地解决 HashCode 冲突的问题，保证对象的存储和访问的正确性。因此，不能直接使用 HashCode 作为下标存储对象，而应该使用 HashMap 等集合类提供的接口方法来进行对象的存储和访问。

16.数组长度为 2 的幂次方

为什么 HashMap 的数组长度要保持为 2 的幂次方呢？

• 只有是 2 的幂次方，hash&(length-1)才等价于 hash%length，实现 key 的快速定位;
  
• 2 的幂次方可以减少 hash 冲突，这样可以保证对数组长度取模后得到的结果是均匀分布的。提高查询效率;
  
• 扩容时直接数组长度翻倍,提升了扩容的效率;
  

在哈希表（Hashmap）中，通过哈希函数将键（key）映射到对应的存储桶（bucket）中。为了确定键在哈希表中的存储位置，常常使用与运算符来实现。

当哈希表的存储桶数量为 2 的幂次方时，使用与运算符可以有效地计算键的下标。这是因为 2 的幂次方的二进制表示中，只有最高位为 1，其他位都为 0。假设哈希表的存储桶数量为n，其二进制表示为1000...00（共k位，最高位为 1，其余位为 0），那么使用与运算符&进行操作时，结果如下：

• hash & (n - 1)
  

由于n - 1的二进制表示为0111...11，其共有k位，最高位为 0，其余位为 1。这样，与运算符会将hash的二进制表示的低k位保留下来，而高位则会被置为 0。通过这种方式，可以将一个大范围的哈希值映射到0到n-1的范围内。

例如，假设哈希表的存储桶数量为 16（即n = 16），其二进制表示为10000，而n - 1的二进制表示为01111。对于一个哈希值hash，通过hash & (n - 1)的操作，可以将其下标限定在0到15的范围内。

使用与运算符的好处是计算速度快，特别是在大多数哈希表实现中，执行位运算比执行除法运算更高效。因此，与运算符通常用于哈希表中计算键的下标，以提高性能和效率。

需要注意的是，哈希表的性能和均匀性也与哈希函数的选择和实现方式有关。一个好的哈希函数能够尽量避免碰撞（collision）并分布键的映射均匀。

通过这种方式，使用与运算符可以将不同的字符串键映射到不同的存储桶中。这样，我们可以有效地在哈希表中存储和检索数据，提高了访问效率。

//putVal方法中

if ((p = tab[i = (n - 1) & hash]) == null)

           tab[i] = newNode(hash, key, value, null);

二.HashMap 进阶

1.jdk1.7 和 jdk1.8 中 HashMap？

jdk1.7:

• 底层采用数组+链表
  
• 数组长度默认是 16，加载因子是 0.75，阈值是 0.75*16=12，当发生冲突时，会以链表的形式存储新的数据，新的数据插入到链表的头部，将新来的值赋值给当前位置的数组。
  
• 当数组中的 12 个位置被占据时，同时新插入的数据位置不为空，需要进行 2 倍扩容。
  
• 并发环境会产生死锁。头插法会使链表发生反转，多线程环境下会产生环.
  

jdk1.8:

• 底层采用数组+链表/红黑树
  
• 数组长度默认是 16，加载因子是 0.75，阈值是 0.75*16=12，当发生冲突时，会以链表的形式存储新的数据，新的数据插入到链表的尾部，将新来的值赋值给当前位置的数组。插入尾部也是为转换红黑树做准备，如果链表上的元素超过 8 个并且数据个数大于等于 64，则转换为红黑树。提高增删查的效率。
  
• 达到阈值值，直接扩容，2 倍扩容。不需要判断新元素的位置是否为空。
  
• 并发下不会产生思死锁，但是会出现数据覆盖。多线程下，1.8 会有数据覆盖
  

数据覆盖举例:线程 A：往 index 插，index 此时为空，可以插入，但是此时线程 A 被挂起线程 B：此时，对 index 写入数据，A 恢复后，就把 B 数据覆盖了

改动对比:

jdk1.8 的 HashMap 主要有五点优化:

数据结构：数组 + 链表改成了数组 + 链表或红黑树

原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由 O(n)降为 O(logn)

链表插入方式：链表的插入方式从头插法改成了尾插法

简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后。

原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。

扩容 rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。

原因：提高扩容的效率，更快地扩容。

扩容时机：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；

散列函数：1.7 做了四次移位和四次异或，jdk1.8 只做一次。

原因：做 4 次的话，边际效用也不大，改为一次，提升效率。

2.jdk1.7 和 jdk1.8 的扩容原理？


jdk1.7

扩容前和扩容后都是使用的公式 hash&(length-1)

整体扩容过程是取出数组元素，遍历以该数组元素为头节点的链表元素，然后计算在新数组中的下标，然后进行交换，即原来 hash 冲突的单向链表的尾部变成了扩容后单向链表的头部。

void transfer(Entry[] newTable, boolean rehash) {

   int newCapacity = newTable.length;

   for (Entry<K,V> e : table) {

       while(null != e) {

           Entry<K,V> next = e.next;//这里记做第一步

           if (rehash) {

               e.hash = null == e.key ? 0 : hash(e.key);

           }

           int i = indexFor(e.hash, newCapacity);

           e.next = newTable[i];//这里记做第二步

           newTable[i] = e;//这里记做第三步

           e = next;//这里记做第四部

       }

   }

}

transfer 函数作用:在对 table 进行扩容到 newTable 后，需要将原来数据转移到 newTable 中，注意 10-12 行代码，这里可以看出在转移元素的过程中，使用的是头插法，也就是链表的顺序会翻转，这里也是形成死循环的关键点。

• hashmap1.7 中的死循环是有多个线程并发扩容形成了环状链表，随后再进行扩容的线程会循环取这个环状链表的节点，造成死循环；
  
• 其次，环状链表是几个节点相互指向，并不是某个节点自己指向自己。
  

jdk1.8

对公式进行判断(hash&newTable)==0

jdk1.8 的扩容更加的优雅，由于扩容数组长度是 2 倍关系。假设原数组 size 是 4，扩容后为 8，左移一位是 2 倍，二进制表示为 0100 >> 1000 的变化。扩容时只需要判断原来的 hash 值和 newtable 进行与运算的结果，如果为 0，则位置保持不变，如果为 1，则在原来的位置加上原数组的长度。

如果为 true，则放在原位置

如果为 false，则放在原位置+oldCap 处

`HashMap 是线程不安全的，其主要体现:

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

3.HashMap jdk1.8 扩容源码分析

HashMap 的扩容原理也挺值得说的,其中把链表分割成一条高位链表和一条低位链表分别插入到新的 2 倍空间数组中,并且不需要重新对每个 key 重新取模,低位链表还是放在原来相同的下标桶位,高位链表放在原来下标桶位+oldCap 的下标位置

final Node<K,V>[] resize() {

 Node<K,V>[] oldTab = table;

 int oldCap = (oldTab == null) ? 0 : oldTab.length;

 int oldThr = threshold;

 int newCap, newThr = 0;

 // 如果table中有元素

 if (oldCap > 0) {

   // 容量是否已达限制

   if (oldCap >= MAXIMUM_CAPACITY) {

     threshold = Integer.MAX_VALUE;

     return oldTab;

   }

   // 扩容，并更新扩容阈值

   else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

            oldCap >= DEFAULT_INITIAL_CAPACITY)

     newThr = oldThr << 1; // double threshold

 }

 // 如果table中没有元素，但是已初始化扩容阈值，这里将table的新容量赋值为扩容阈值

 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;

 @SuppressWarnings({"rawtypes","unchecked"})

 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

 table = newTab;

 // 如果原来table有值，则循环将原值转移到newTab中

 if (oldTab != null) {

   for (int j = 0; j < oldCap; ++j) {

     Node<K,V> e;

     // 找到有值的节点

     if ((e = oldTab[j]) != null) {

       oldTab[j] = null; //将原来table中当前位置置null

       if (e.next == null) // 如果当前节点next为null，将其放置在newTab中的新位置

         newTab[e.hash & (newCap - 1)] = e;

       // 如果是红黑树则进行红黑树操作，关于红黑树后面会进行分析

       else if (e instanceof TreeNode)

         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

       else { // preserve order  // 当走到这里，说明节点上为链表形式存储数据，需进行循环操作

         // 存储位置在newTable和oldTable位置不变元素

         Node<K,V> loHead = null, loTail = null;

         // 存储oldTable中位置发生了变化的元素，当然这里是和oldTable相比较

         // 参看下面的注释，应该可以很好理解

         Node<K,V> hiHead = null, hiTail = null;

         Node<K,V> next;

         do {

           // 由于是链表循环，因此需存储next节点的值，这种形式在jdk1.7中出现过多次

           next = e.next;

           /**

                            *这里需要注意一下，这里是用元素的hash值，与原来table长度做&操作

                            * 如果为0，则表示e.hash&(newCap-1)和e.hash&(oldCap-1)是一样的

                            * 也就说元素的位置在newTable中是不变的，因为newTable的大小为oldTable大小的2倍

                            * 相当于其二进制向左移动了1位，其newCap-1的二进制全都为1，且比原来oldCap-1的二进制多了一个1

                            * eg:oldCap=16,newCap=32，注意求key的位置是用e.hash&(table.length-1)

                            * e.hash&0x1111=原来key的位置

                            * e.hash&0x10000=0，表明e.hash在二进制的第5位上一定为0，所以：

                            * e.hash&0x11111=也一定是原来key的位置

                            * 如果:

                            * e.hash&0x10000=1，表明e.hash在二进制的第5位上一定为1，所以：

                            * e.hash&0x11111=原来key的位置加上oldCap的长度即可（0x10000）

                            * 这样根据一个二进制位就将原来的一条链表分成两条链表进行存储，这里非常的关键，不是很好理解

                            * 仔细理解上面的解释，相信你会发现这是非常神奇的一个技巧

                            */

           // 有了上面的原理，再来看这就非常明确了

           // 元素在newTable中位置不改变

           if ((e.hash & oldCap) == 0) {

             // 初始时，将e放在loHead头上，然后尾又是e，后续循环的时候，只操作tail就行了，形成链表

             if (loTail == null)

               loHead = e;

             else

               loTail.next = e;

             // 尾部存储为e,形成链表，注意理解就好

             loTail = e;

           }

           // 元素在newTable中位置发生了变化[相对oldTable]

           // 这里就相当于两条链表了，位置不变的一条，位置变了的又是一条

           else {

             if (hiTail == null)

               hiHead = e;

             else

               hiTail.next = e;

             hiTail = e;

           }

         } while ((e = next) != null);

         // 如果位置不变链表不为null

         if (loTail != null) {

           loTail.next = null;

           // 从这里也可看出这里存储的是元素在newTable中位置不改变[相对oldTable]

           // 只需要存储head值即可，因为已形成链表

           newTab[j] = loHead;

         }

         if (hiTail != null) {

           hiTail.next = null;

           // 位置变化的元素，位置只需要加上oldCap的值就可以了,上面已进行分析

           newTab[j + oldCap] = hiHead;

         }

       }

     }

   }

 }

 return newTab;

}

在 jdk1.7 源码中 HashMap 进行扩容时，hash 冲突的数组索引处的旧链表元素扩容到新数组时，如果扩容后的数组元素的位置与原数组的索引位置相同，则链表会发生倒置，在 jdk1.8 中不会出现倒置。

在 jdk1.7 中，扩容时紧紧只是重新计算了数组的下标，整体的数据结构还是数组+链表

在 jdk1.8 中，扩容时，不仅重新计算了下标，在链表长度达到 8 时，会转换为红黑树。且当前结构为红黑树，元素个数小于 6 时，会转换为链表结构。

4.jdk1.8 红黑树扩容 split 方法？

//扩容后，红黑树的hash分布，只可能存在于两个位置：原索引位置、原索引位置+oldCap

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {

   TreeNode<K,V> b = this;//拿到调用此方法的节点

   // Relink into lo and hi lists, preserving order

   TreeNode<K,V> loHead = null, loTail = null;//存储索引位置为：“原索引位置”的节点

   TreeNode<K,V> hiHead = null, hiTail = null;//存储索引位置为：“原索引+oldCap”的节点

   int lc = 0, hc = 0;

   for (TreeNode<K,V> e = b, next; e != null; e = next) {

       next = (TreeNode<K,V>)e.next;

       e.next = null;

       if ((e.hash & bit) == 0) {

           if ((e.prev = loTail) == null)

               loHead = e;

           else

               loTail.next = e;

           loTail = e;

           ++lc;

       }

       else {

           if ((e.prev = hiTail) == null)

               hiHead = e;

           else

               hiTail.next = e;

           hiTail = e;

           ++hc;

       }

   }

   if (loHead != null) {

       if (lc <= UNTREEIFY_THRESHOLD)

           tab[index] = loHead.untreeify(map);

       else {

           tab[index] = loHead;

           if (hiHead != null) // (else is already treeified)

               loHead.treeify(tab);

       }

   }

   if (hiHead != null) {

       if (hc <= UNTREEIFY_THRESHOLD)

           tab[index + bit] = hiHead.untreeify(map);

       else {

           tab[index + bit] = hiHead;

           if (loHead != null)

               hiHead.treeify(tab);

       }

   }

}

5.String 类适合做 key 的原因？

在《Java 编程思想》中有这么一句话:设计 hashCode() 时最重要的因素就是对同一个对象调用 hashCode() 都应该产生相同的值。

String 类型的对象对这个条件有着很好的支持，因为 String 对象的 hashCode() 值是根据 String 对象的 内容计算的，并不是根据对象的地址计算。下面是 String 类源码中的 hashCode() 方法:String 对象底 层是一个 final 修饰的 char 类型的数组，hashCode() 的计算是根据字符数组的每个元素进行计算的，所 以内容相同的 String 对象会产生相同的散列码

HashMap 内部实现是通过 key 的 hashCode 来确定 value 的位置的。

• String 天生复写了 hashCode 方法，根据 String 的内容来计算 hashCode。
  
• 因为字符串是不可变的，当创建字符串时，它的 hashCode 被缓存下来，不需要再次计算，所以相比于其他对象更快。
  

public int hashCode() {

       int h = hash;

       if (h == 0 && value.length > 0) {

           char val[] = value;

           for (int i = 0; i < value.length; i++) {

               h = 31 * h + val[i];

           }

           hash = h;

       }

       return h;

}

6.自定义的对象作为 key？

需要重写 hashCode 方法和 equals 方法。

当 HashMap 存入 k1 的时候，会执行 hashCode 方法，因为没有重写 hashCode 方法，会去 Object 类找 hashCode 方法，而 object 类的 hashCode 方法返回的时对象的地址。这时候用 k2 去获取，用相同的方式去获取 hashCode 方法，因为内存地址不一样，所以 hashCode 不一样。

即使 hashCode 一致，在 hash 冲突的情况下，需要调用 equals 方法进行对比，因为没有重写 equals 方法，会调用 object 的 equals 方法，object 的 equals 方法会比较内存地址是否一样，因为 k1 和 k2 时 new 出来的，内存地址是不一样的，所以 k2 获取不到 k1 的值。因为没有重写 hashCode 方法和 equals 方法。

7.什么是 hash 冲突？

hash，一般翻译为散列，也音译为哈希。

通俗来讲就是将任意长度的字符通过散列算法，输出为固定长度的散列值，也叫 hash 值。这种散列是一种压缩映射，散列值的空间远小于原值的空间，不同的输入可能会有相同的散列值输出。所以不能仅仅通过散列值来做字符相等的判断。简单来说就是将任意长度的消息，压缩到某一固定长度消息的函数。

根据同一散列函数计算出的 hash 值不同，则输入值肯定不同，hash 值相同，输入值也可能不同。也就是 hash 冲突的情况。

在处理哈希冲突的情况下，equals 方法非常有用。当不同的对象被映射到相同的哈希值时，我们需要进一步检查它们的内容是否真的相同。这时就需要通过重写 equals 方法来定义两个对象在逻辑上的相等性。通常，重写 equals 方法会比较对象的字段内容，以确定它们是否表示相同的数据。

8.解决 hash 冲突的方式有哪些？

开放定址法:使用探测的方式在数组中找到另一个可以存储值的位置。

链地址法:也叫拉链法，HashMap 和 HashSet 都是使用的这种方式，在存在 hash 冲突的时候，使用链表或者红黑树的形式存储数据。

再散列法:hash 冲突时，通过再次散列的方式确定插入的位置，缺点是每次冲突都要计算散列，时间复杂度增加。

公共溢出区:将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

9.开发寻址法的探索方式？

线性探测:

按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上往后加一个单位，直至不发生哈希冲突。

再平方探测:

按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上先加 1 的平方个单位，若仍然存在则减 1 的平方个单位。随之是 2 的平方，3 的平方等等。直至不发生哈希冲突。

伪随机探测:

按顺序决定哈希值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来哈希值的基础上加上随机数，直至不发生哈希冲突。

10.开放地址法和拉链法的优缺点？

开放地址法:会产生堆积问题，不适合大规模的数据存储，插入时，可能会出现多次冲突的情况，删除数据时，其他数据也有影响，实现相对较为复杂。且节点规模大时，再平方探测会浪费空间。

拉链法:处理冲突简单，且无堆积现象。平均查找长度短，时间复杂度低。链表中的节点是动态申请的，适合构造表不能确定的情况。相对而言，指针域可以忽略不计，所以更节省空间。尾插法简单，只需要修改指针，不需要对其他冲突做处理。

11.负载因子为什么会影响性能？

负载因子代表了一个散列表的空间使用程度。initailCapacity*loadFactor=HashMap 的实际容量

负载因子越大，元素越多，导致扩容时机越晚,导致 hash 冲突的机会变多,从而链表变长，查询的时间复杂度增大，性能下降。HashMap 的负载因子默认是 0.75

负载因子越小，元素稀疏，空间利用率低。查找效率高。

12.HashMap 中红黑树的插入方法?

插入方法 balanceInsertion

源码及注释如下,需要注意的是参数 root 表示根节点,x 表示需要旋转的结点,返回值就是新的根节点,红黑树的插入平衡中可能会涉及根节点的改变，因此参数传入原来的根节点来修改。

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,

                                           TreeNode<K,V> x) {

 x.red = true;             //所有插入结点初始值都为红色

 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //xp为x父结点，xpp为x的祖父结点，xppl为x的祖父结点的左子结点，xppr为x的祖父结点的右子结点

   if ((xp = x.parent) == null) { //插入结点是根结点，直接变黑色，返回x

     x.red = false;

     return x;

   }

   else if (!xp.red || (xpp = xp.parent) == null) //情况2，插入结点父结点为黑色

     return root; //不用操作，直接返回原来的根结点

   //下面是情况3，父结点是红结点

   if (xp == (xppl = xpp.left)) { //x的父结点是祖父结点的左子结点

     if ((xppr = xpp.right) != null && xppr.red) { //情况3.1，叔叔结点是红结点

       xppr.red = false;//x的叔叔结点变黑色

       xp.red = false; //x的父结点变为黑色

       xpp.red = true; //x的祖父结点变红色

       x = xpp;  //把祖父结点作为新的插入结点

     }

     else {

       if (x == xp.right) {//情况3.2.2叔叔结点不存在或者为黑色，插入结点x是父结点p的右子结点

         root = rotateLeft(root, x = xp); 对x的父结点左旋，把p设为插入结点,之后转到下面情况3.2.1

           xpp = (xp = x.parent) == null ? null : xp.parent;

       }

       if (xp != null) {//情况3.2.1 叔叔结点不存在或者为黑色，插入结点x是父结点p的左子结点

         xp.red = false;//x的父结点xp变黑

         if (xpp != null) {

           xpp.red = true; //x的祖父结点xpp变为红

           root = rotateRight(root, xpp); //对x的祖父结点右旋

         }

       }

     }

   }

   else { //x的父结点是祖父结点的右子结点

     if (xppl != null && xppl.red) {//情况3.1 叔叔结点是红色

       xppl.red = false;//叔叔结点变黑

       xp.red = false;//父结点变黑

       xpp.red = true;//祖父结点变红

       x = xpp;//把祖父结点设置为新的插入结点

     }

     else {

       if (x == xp.left) {//情况3.3.2叔叔结点不存在或者为黑色，插入结点x是父节点p的左子结点

         root = rotateRight(root, x = xp);//duix的父结点右旋，把p设置为新的插入结点，之后转到下面情况3.3.1

         xpp = (xp = x.parent) == null ? null : xp.parent;

       }

       if (xp != null) {//情况3.3.1 叔叔结点不存在或者为黑色，插入结点x是父结点p的右子结点

         xp.red = false;//x的父结点xp变黑

         if (xpp != null) {

           xpp.red = true;//x的祖父结点xpp变为红

           root = rotateLeft(root, xpp);//对x的祖父结点xpp左旋

         }

       }

     }

   }

 }

}

13.红黑树的特点?

• 红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：
  
• 每个节点要么是红色，要么是黑色；
  
• 根节点永远是黑色的；
  
• 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
  
• 每个红色节点的两个子节点一定都是黑色；
  
• 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
  
  

14.如果初始化 HashMap 为 17?

简单来说，就是初始化时，传的不是 2 的倍数时，HashMap 会向上寻找离得最近的 2 的倍数，所以传入 17，但 HashMap 的实际容量是 32。我们来看看详情，在 HashMap 的初始化中，有这样⼀段⽅法；

public HashMap(int initialCapacity, float loadFactor) {

 ...

   this.loadFactor = loadFactor;

 this.threshold = tableSizeFor(initialCapacity);

}

阀值 threshold ，通过⽅法 tableSizeFor 进⾏计算，是根据初始化传的参数来计算的。同时，这个⽅法也要要寻找⽐初始值⼤的，最⼩的那个 2 进制数值。⽐如传了 17，我应该找到的是 32。

static final int tableSizeFor(int cap) {

int n = cap - 1;

n |= n >>> 1;//高位不断补1

n |= n >>> 2;//高位不断补1

n |= n >>> 4;//高位不断补1

n |= n >>> 8;//高位不断补1

n |= n >>> 16;//高位不断补1

//最后加1变为2的 n次幂

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

MAXIMUM_CAPACITY = 1 << 30，这个是临界范围，也就是最⼤的 Map 集合。计算过程是向右移位 1、2、4、8、16，和原来的数做|运算，这主要是为了把⼆进制的各个位置都填上 1，当⼆进制的各个位置都是 1 以后，就是⼀个标准的 2 的倍数减 1 了，最后把结果加 1 再返回即可。

那为什么必须要对cap进行-1之后再进行运算呢？如果指定的数刚好是 2 的整数次幂，如果没有-1 结果会变成比他大两倍的数

以 17 为例，看一下初始化计算 table 容量的过程:

例子 1:

例子 2:

15.为什么 key 和 value 都可以为 null

在 Java 中，HashMap 是一种散列表实现，它使用键值对的方式来存储数据。HashMap 中的每个键对应唯一的值，即 key-value 对。在 HashMap 中，key 和 value 都可以为 null，这是因为 HashMap 内部使用了哈希算法来计算 key 的散列值，并将 key-value 对存储在散列表中。如果key为null，那么在计算散列值时，会将null作为特殊值对待，并将散列值设置为0。如果value为null，那么在存储value时，HashMap会将这个null值作为一个普通的value来处理，并将它与key一起存储在散列表中。

需要注意的是，在使用 HashMap 时，如果 key 为 null，那么在进行 put、get、remove 等操作时，需要特殊处理。例如，当需要判断一个 key 是否存在时，应该使用 containsKey 方法而不是直接判断 key 是否为 null。同样地，当需要获取一个 key 对应的 value 时，也应该使用 get 方法，并在返回结果之前判断 value 是否为 null。

在使用 HashMap 时，通常建议尽量避免使用 null 值作为 key 或 value，以免造成不必要的麻烦。如果确实需要使用 null 值，那么应该注意特殊处理，并避免在程序中出现空指针异常。

16.设计实现一个 HashMap 吗？

• 散列函数：hashCode()+除留余数法
  
• 冲突解决：链地址法
  
• 扩容：节点重新 hash 获取位置
  

/**

* 自定义HashMap

*

* @author : kwan

* @date : 2022/8/8

*/

public class ThirdHashMap<K, V> {

 /**

    * 节点类

    */

 class Node<K, V> {

   //键值对

   private K key;

   private V value;

   //连表。后维

   private Node<K, V> next;

   private Node(K key, V value) {

     this.key = key;

     this.value = value;

   }

   public Node(K key, V value, Node<K, V> next) {

     this.key = key;

     this.value = value;

     this.next = next;

   }

 }

 //默认容量

 final int DEFAULT_CAPACITY = 16;

 final float LOAD_FACTOR = 0.75f;

 //HashMap的大小

 private int size;

 //桶效组

 Node<K, V>[] buckets;

 /**

    * 无参构造器，设置桶数组默认容量

    */

 public ThirdHashMap() {

   buckets = new Node[DEFAULT_CAPACITY];

   size = 0;

 }

 /**

    * 有多构造，指定桶数组容量

    */

 public ThirdHashMap(int capacity) {

   buckets = new Node[capacity];

   size = 0;

 }

 /**

    * 哈希函数，获取地址

    */

 private int getIndex(K key, int length) {

   //获取hash code

   int hashCode = key.hashCode();//和标数组长度取余

   int index = hashCode % length;

   return Math.abs(index);

 }

 /**

    * put方法

    */

 public void put(K key, V value) {

   //刺断是否需要进行打容

   if (size >= buckets.length * LOAD_FACTOR) {

     resize();

   }

   putVal(key, value, buckets);

 }

 /**

    * 将元素存入指定的node数组

    */

 private void putVal(K key, V value, Node<K, V>[] table) {

   //获取位置

   int index = getIndex(key, table.length);

   Node node = table[index];//插入的值置为空

   if (node == null) {

     table[index] = new Node<>(key, value);

     size++;

     size++;

     return;

   }

   //插入位置不为空，说明发生冲夹，使用链地址法，调历销表

   while (node != null) {

     //如果key相同，就覆盖掉

     if ((node.key.hashCode() == key.hashCode())

         && (node.key == key || node.key.equals(key))) {

       node.value = value;

       return;

     }

     node = node.next;

   }

   //当前key不在链表中，捡入链表头都

   Node newNode = new Node(key, value, table[index]);

   table[index] = newNode;

   size++;

 }

 /**

    * 扩容

    */

 private void resize() {

   //创建一个两价容量的桶数组

   Node<K, V>[] newBuckets = new Node[buckets.length * 2];

   //将当落元表主新散列到新的敬组

   rehash(newBuckets);

   buckets = newBuckets;

 }

 /**

    * 重新散列当苗元素

    */

 private void rehash(Node<K, V>[] newBuckets) {

   //map大小里新计算

   size = 0;

   //将旧的桶数组的元素全部剧到新的桶数组里

   for (int i = 0; i < buckets.length; i++) {

     //为空，跳

     if (buckets[i] == null) {

       continue;

     }

     Node<K, V> node = buckets[i];

     while (node != null) {

       //将元未放入新数组

       putVal(node.key, node.value, newBuckets);

       node = node.next;

     }

   }

 }

 /**

    * 获取元素

    */

 public V get(K key) {

   //获取key对应的地址

   int index = getIndex(key, buckets.length);

   if (buckets[index] == null) {

     return null;

   }

   Node<K, V> node = buckets[index];

   //查找链表

   while (node != null) {

     if ((node.key.hashCode() == key.hashCode())

         && (node.key == key | !node.key.equals(key))) {

       return node.value;

     }

     node = node.next;

   }

   return null;

 }

 /**

    * 返回HashMap大小

    *

    * @return

    */

 public int size() {

   return size;

 }

}

三.HashTable

1.Hashtable 定义

Hashtable 是 Java 中的一个散列表实现，继承自 Dictionary 类，实现了 Map 接口。Hashtable 使用键值对的方式来存储数据，其中每个键对应唯一的值，即 key-value 对。

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable,             java.io.Serializable {

        .........

}

2.为啥 key 和 value 都不能为 null

Hashtable 中的 key 和 value 都不能为 null，这是因为 Hashtable 内部使用了哈希算法来计算 key 的散列值，然后将 key-value 对存储在散列表中。如果 key 为 null，那么在计算散列值时就会抛出 NullPointerException 异常；

如果value为null,那么存储value时就无法区分一个null值是表示这个key不存在还是表示这个key对应的值为null

public synchronized V put(K key, V value) {

       // Make sure the value is not null

       if (value == null) {

           throw new NullPointerException();

       }

}

为了解决这个问题，Java 中提供了 HashMap 类，它和 Hashtable 类类似，也是一个散列表实现，但是 HashMap 允许 key 和 value 都为 null，而且 HashMap 的性能也比 Hashtable 更好。

因此，在开发中如果不需要考虑线程安全问题，建议使用 HashMap 来代替 Hashtable。如果需要线程安全，也可以使用 Java 中提供的 ConcurrentHashMap 类来实现线程安全的散列表。

3.HashTable 是有序的吗?

HashTable 是无序的,生成的 hashcode 不一样,找到的 index 不一样,Hashtable 与 HashMap 一样，都是以键值对的形式存储数据。但是 Hashtable 的键值不能为 null，而 HashMap 的键值是可以为 null 的。Hashtable 是线程安全，因为它的元素操作方法上都加了 synchronized 关键字，这就导致锁的粒度太大，因此日常开发中一般建议使用 ConcurrentHashMap。


4.Hashtable 确定 index 位置?

int index = (hash & 0x7FFFFFFF) % tab.length;

public synchronized V put(K key, V value) {

     // Make sure the value is not null

     if (value == null) {

         throw new NullPointerException();

     }

     // Makes sure the key is not already in the hashtable.

     Entry<?,?> tab[] = table;

     int hash = key.hashCode();

     int index = (hash & 0x7FFFFFFF) % tab.length;

     @SuppressWarnings("unchecked")

     Entry<K,V> entry = (Entry<K,V>)tab[index];

     for(; entry != null ; entry = entry.next) {

         if ((entry.hash == hash) && entry.key.equals(key)) {

             V old = entry.value;

             entry.value = value;

             return old;

         }

     }

     addEntry(hash, key, value, index);

     return null;

}

5.构造函数

从默认构造函数可知：Hashtable 的默认容量为 11，扩容因子为 0.75f。

public Hashtable(int initialCapacity) {

       this(initialCapacity, 0.75f);

}

public Hashtable() {

     this(11, 0.75f);

}

public Hashtable(Map<? extends K, ? extends V> t) {

       this(Math.max(2*t.size(), 11), 0.75f);

       putAll(t);

}

6.Hashtable 扩容?

在 put 函数中涉及扩容，但是由于 put 操作为线程安全，所以扩容时也是线程安全的。扩容要求：当前元素个数大于等于容量与扩容因子的乘积。还有一点需注意插入的新节点总是在头部。

整个扩容过程比较简单，注意新的数组大小是原来的 2 倍加 1，还有一点比较重要扩容时插入新元素采用的是头插法，元素会进行倒序。

protected void rehash() {

 // 旧的容量大小

 int oldCapacity = table.length;

 Entry<?,?>[] oldMap = table;

 // overflow-conscious code

 // 扩容后新的容量等于原来容量的2倍+1

 int newCapacity = (oldCapacity << 1) + 1;

 // 容量大小控制，不要超过最大值

 if (newCapacity - MAX_ARRAY_SIZE > 0) {

   if (oldCapacity == MAX_ARRAY_SIZE)

     // Keep running with MAX_ARRAY_SIZE buckets

     return;

   newCapacity = MAX_ARRAY_SIZE;

 }

 // 创建新的数组

 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

 modCount++;

 // 更新扩容因子

 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

 table = newMap;

 // 数组转移 这里是从数组尾往前搬移

 for (int i = oldCapacity ; i-- > 0 ;) {

   for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {

     Entry<K,V> e = old;

     old = old.next;

     // 计算元素在新数组中的位置

     int index = (e.hash & 0x7FFFFFFF) % newCapacity;

     // 进行元素插入，注意这里是头插法，元素会倒序

     e.next = (Entry<K,V>)newMap[index];

     newMap[index] = e;

   }

 }

}

7.HashTable 扩容方式为 2n+1？

为了均匀分布，降低冲突率

首先，Hashtable 的初始容量为 11。扩容方式为

int newCapacity = (oldCapacity << 1) + 1;

Index 的计算方式为：

int  index = (hash & 0x7FFFFFFF) % tab.tength;

常用的 hash 函数是选一个数 m 取模（余数），推荐 m 是素数，但是经常见到选择 m=2ⁿ，因为对 2ⁿ求余数更快，并认为在 key 分布均匀的情况下，key%m 也是在[0,m-1]区间均匀分布的。

但实际上，key%m 的分布同 m 是有关的。

证明如下：key%m = key - xm，即 key 减掉 m 的某个倍数 x，剩下比 m 小的部分就是 key 除以 m 的余数。显然，x 等于 key/m 的整数部分，以 floor(key/m)表示。假设 key 和 m 有公约数 g，即 key=ag, m=bg, 则key - xm = key - floor(key/m)m = key - floor(a/b)m。由于 0 <= a/b <= a，所以 floor(a/b)只有 a+1 种取值可能，从而推导出 key%m 也只有 a+1 种取值可能。a+1 个球放在 m 个盒子里面，显然不可能做到均匀。

由此可知，一组均匀分布的 key，其中同 m 公约数为 1 的那部分，余数后在[0,m-1]上还是均匀分布的， 但同 m 公约数不为 1 的那部分，余数在[0, m-1]上就不是均匀分布的了。把 m 选为素数，正是为了让所有 key 同 m 的公约数都为 1，从而保证余数的均匀分布，降低冲突率。 鉴于此，在 HashTable 中，初始化容量是 11，是个素数，后面扩容时也是按照 2N+1 的方式进行扩容， 确保扩容之后仍尽量是素数。

8.HashMap 和 Hashtable 的区别？

1. 继承的父类不同

• Hashtable 继承自 Diconary 类，HashMap 继承自 AbtractMap 类
  
• 两者都实现了 map 接口
  

2. 线程安全不同

• HashMap 的实现不是同步的，如果多线程同时访问同一 hash 映射，至少有一个线程从结构上修改了该映射，则应该实现外部同步。结构上的修改是指添加或删除一个或多个映射关系的任
  何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。
  
• Hashtable 的方法是 synchronize 修饰的。在多线程环境下可以直接使用 Hashtable，不需要额外增加同步，使用 HashMap 需要额外处理同步问题。一般使用封装好的工具类。或则加上 synchronize 修饰。
  

3. 是否提供 contains 方法

• HashMap 去掉了 contains 方法，保留了 containValue 和 containsKey 方法。因为 contains 方法容易让人产生误解。
  
• Hashtable 保留了 contains 方法，contains 方法和 containsValue 方法功能相同。
  

4. key 和 value 是否允许为 null

• Hashtable 中，key 和 value 都不能为 null。put(null,null)编译可以通过，因为 key 和 value 都是 object 类型，但是执行会报错。会报空指针异常。
  
• 在 HashMap 中 key 可以为 null，并且只能有一个 null 键。值可以有多个 null 值。当 get 方法获取到的值为 null 时，可能是 HashMap 中不存在该 key，也可能是 key 对应的值为 null，所以不能通过 get 方法判断 key 是否存在，应该用 containsKey 方法。
  

5. 迭代方式不同

• 两者都使用了 terator 迭代器。
  
• 由于历史原因，Hashtable 还使用了 enumeration 的方式。
  

6. hash 值不同

• Hashtable 直接使用了 hashCode 与 Integer 的最大值进行与操作,再和数组长度取余;
  
• HashMap 还进行了扰动函数的计算和与函数运算;
  

7. 内部实现(初始化+扩容)

• Hashtable 默认不指定长度为 11，HashMap 默认为 16。Hashtable 不要求数组的容量为 2 的幂次方，HashMap 要求数组的容量为 2 的幂次方。
  
• Hashtable 扩容时为 2n+1，HashMap 为 2n。
  

9.Hashtable 总结?

• Hashtable 线程安全、元素无序（因为以 hashCode 为基准进行散列存储），不允许[key，value]为 null。
  
• Hashtable 默认容量为 11，与 HashMap 不同（默认容量 16），扩容时容量增长为 2n+1（HashMap 直接增长为 2 倍）。
  
• 扩容转移元素时采用的是头插法
  

四.ConcurrentHashMap

1.jdk1.7 中 CHM 数据结构？

ConcurrentHashMap 和 HashMap 结构差不多，不过 ConcurrentHashMap 支持并发操作。所以结构更加复杂一些。

整个 ConcurrentHashMap 由一个个 segment 组成。segment 代表一段的意思。所以 ConcurrentHashMap 也叫分段锁。简单理解，ConcurrentHashMap 是由 segment 数组组成。segment 继承自 reentrantlock 来进行加锁，所以每个 segment 是线程安全的，整个 ConcurrentHashMap 就是线程安全的。

ConcurrentHashMap 与 HashMap 和 Hashtable 最大的不同在于：put 和 get 两次 Hash 到达指定的 HashEntry，第一次 hash 到达 Segment,第二次到达 Segment 里面的 Entry,然后在遍历 entry 链表.

2.CHM 的构造函数有几个？

public ConcurrentHashMap() {

}

public ConcurrentHashMap(int initialCapacity) {

   if (initialCapacity < 0)

       throw new IllegalArgumentException();

   int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?

              MAXIMUM_CAPACITY :

              tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));

   this.sizeCtl = cap;

}

public ConcurrentHashMap(Map<? extends K, ? extends V> m) {

   this.sizeCtl = DEFAULT_CAPACITY;

   putAll(m);

}

public ConcurrentHashMap(int initialCapacity, float loadFactor) {

  this(initialCapacity, loadFactor, 1);

}

//可设置初始容量和阈值和并发级别

public ConcurrentHashMap(int initialCapacity,

                        float loadFactor, int concurrencyLevel) {

   if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)

       throw new IllegalArgumentException();

   if (initialCapacity < concurrencyLevel)   // Use at least as many bins

       initialCapacity = concurrencyLevel;   // as estimated threads

   long size = (long)(1.0 + (long)initialCapacity / loadFactor);

   int cap = (size >= (long)MAXIMUM_CAPACITY) ?

       MAXIMUM_CAPACITY : tableSizeFor((int)size);

   this.sizeCtl = cap;

}

concurrencyLevel:并发级别，并发数，segment 数。默认是 16，也就是说默认是 16 个 segments。

理论上来说，最多支持 16 个线程并发写。操作分布在不同的 segment 上，对单独的 segment 进行加锁处理，可以做到线程安全，可以在初始化的时候设置此值，设置之后不支持扩容。

3.jdk1.7 的 CHM 是如何进行锁操作的？


数据结构：ReentrantLock+Segment+HashEntry 组成，写的时候对单个 segment 加锁

4.jdk1.8 的 CHM 是如何保证并发的？


数据结构为数组+链表/红黑树，内部大量采用 cas 来实现。JDK8 中 ConcurrentHashMap 参考了 JDK8 HashMap 的实现，采用了数组+链表/红黑树的实现方式来设计，内部大量采用 CAS 操作。

CAS 是 compare and swap 的缩写，即我们所说的比较交换。cas 是一种基于锁的操作，而且是乐观锁。在 java 中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加 version 来获取数据，性能较悲观锁有很大的提高。

JDK8 中彻底放弃了 Segment 转而采用的是 Node，其设计思想也不再是 JDK1.7 中的分段锁思想。

Node:保存 key，value 及 key 的 hash 值的数据结构。其中 value 和 next 都用 volatile 修饰，保证并发的

可见性。

static class Node<K,V> implements Map.Entry<K,V> {

   final int hash;

   final K key;

   volatile V val;//并发可见性

   volatile Node<K,V> next;//并发可见性

   Node(int hash, K key, V val, Node<K,V> next) {

       this.hash = hash;

       this.key = key;

       this.val = val;

       this.next = next;

   }

}


5.jdk1.8 的 CHM 和 jdk1.7 的区别？

数据结构上的区别，在 jdk1.7 中使用的是 ReentrantLock+Segment+HashEntry ，在 jdk1.8 中使用的是 Node+CAS+synchronized+红黑树。

• JDK1.8 的实现降低锁的粒度，JDK1.7 版本锁的粒度是基于 Segment 的，包含多个 HashEntry，而 JDK1.8 锁的粒度就是 HashEntry（首节点）
  
• 取消了 segment 分段锁，采用数组+链表+红黑树。
  
• 1.7 中用 ReentrantLock+Segment 加锁，1.8 中使用的是 CAS+synchronized 加锁,对数组元素 Node 加锁。
  
• 在链表节点大于 8 时,且数组长度大于等于 64 时，会转为红黑树。数据量大时，hash 冲突加剧，性能下降。
  
• 查询时间复杂度，1.7 最坏时是单链表 O(n),1.8 是红黑树 O(logn)
  
• JDK1.8 版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用 synchronized 来进行同步，所以不需要分段锁的概念，也就不需要 Segment 这种数据结构了，由于粒度的降低，实现的复杂度也增加了
  
• JDK1.8 使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档
  

6.Hashtable 和 CHM 在多线程下区别？

多线程环境下都是线程安全的，ConcurrentHashMap 的效率更高。

HashTable 使用一把锁处理并发问题，在多线程情况下，多个线程竞争同一个锁，效率较低，导致阻塞。

ConcurrentHashMap 分两个版本

• 1.7 使用分段锁，相当于把 HashMap 分成多段，每一段都拥有各自的锁，这样可以实现多线程访问。
  
• 1.8 采用了 cas 和 synchronized 加锁，锁粒度细化到元素本身，理论上是最高级别的并发。
  

7.CHM 的 get()为什么不需要加锁?

ConcurrentHashMap 的 get 操作可以无锁是由于 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程 A 修改结点的 val 或者新增节点的时候是对线程 B 可见的。

在 Node 上加 volatile 的目的是什么呢？其实就是为了使得 Node 数组在扩容的时候对其他线程具有可见性而加的 volatile。

get 操作全程不需要加锁是因为 Node 的成员 val 是用 volatile 修饰的和 Node 用 volatile 修饰没有关系。Node 用 volatile 修饰主要是保证在数组扩容的时候保证可见性。

8.CHM 是如何进行扩容的?

private transient volatile int sizeCtl;


通过构造函数可以发现 sizeCtl 变量经常出现，该变量通过查看 jdk 源码注释可知该变量主要控制初始化或扩容：

• -1，表示线程正在进行初始化操作。
  
• -(1+nThreads)，表示 n 个线程正在进行扩容。
  
• 0，默认值，后续在真正初始化的时候使用默认容量。
  
• 大于 0，初始化或扩容完成后下一次的扩容门槛。
  

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {

   int n = tab.length, stride;

   // 单核不拆分，下面讨论多核的情况

   // 计算步长，拆分任务n >>> 3 = n / 2^3

   // 先将n分为8份，然后等分给每个cpu，若最后计算的步长小于最小步长16，则设置为16

   if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)

       stride = MIN_TRANSFER_STRIDE; // subdivide range

   if (nextTab == null) {            // initiating

       try {

           // 扩容 2倍

           @SuppressWarnings("unchecked")

           Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];

           nextTab = nt;

       } catch (Throwable ex) {      // try to cope with OOME

           sizeCtl = Integer.MAX_VALUE;

           return;

       }

       nextTable = nextTab;

       // transferIndex 记录迁移进度

       transferIndex = n;

   }

   int nextn = nextTab.length;

   ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);

   // 从后面的迁移逻辑看到 迁移复制元素是逆序迁移

   // advance= true 则代表可继续向前一个位置迁移复制元素

   boolean advance = true;

   // 是否所有线程都全部迁移完毕，true则可以将nextTab赋值给table了

   boolean finishing = false; // to ensure sweep before committing nextTab

   // i 代表当前线程正在迁移的数组位置，bound代表它本次可以迁移的范围下限

   for (int i = 0, bound = 0;;) {

       Node<K,V> f; int fh;

       while (advance) {

           int nextIndex, nextBound;

          // （1）两种情况不需要继续向前一个位置迁移复制元素（逆序）：

           // ①i每次自减1，i>=bound说明本批次迁移未完成，不需要继续向前推进。

           // ②finishing标志为true，说明所有线程分配的迁移任务都已经完成了，则不需要向前推进。

           // 若 --i < bound，说明当前批次的迁移任务完成，可继续分配新范围的任务

           // 也就是一个线程可以多次分到任务，能者多劳。

           if (--i >= bound || finishing)

               // 向前一个位置迁移复制元素

               advance = false;

            //(2) 每次执行，都会把 transferIndex 最新的值同步给 nextIndex

           else if ((nextIndex = transferIndex) <= 0) {

               //若 transferIndex小于等于0，则说明原数组中所有位置的迁移任务都分配完毕（不代表所有位置都迁移完毕）

               //于是，需要跳出while循环，并把 i设为 -1，

               // 以跳到（4）判断正在处理的线程是否完成自己负责范围内迁移工作。

               i = -1;

               advance = false;

           }

           else if (U.compareAndSwapInt

                    (this, TRANSFERINDEX, nextIndex,

                     nextBound = (nextIndex > stride ?

                                  nextIndex - stride : 0))) {

               //（3）cas 设置TRANSFERINDEX，分配任务范围[nextBound,nextIndex)，任务的长度是stride

               // 举例，假设 n=64，即初始的transferIndex=64，stride=16

               // nextIndex=transferIndex=64，nextBound=nextIndex-stride=48

               // bound=48

               // i=63

               // 从后往前复制

               bound = nextBound;

               i = nextIndex - 1;

               advance = false;  // 本次任务分配完成，结束循环

           }

       }

       // （4）i已经越界了，整个数组的迁移任务已经全部分配完毕

       if (i < 0 || i >= n || i + n >= nextn) {

           int sc;

           if (finishing) {

               // 扩容完毕

               // nextTable置为空

               nextTable = null;

               // 新数组赋值给旧数组

               table = nextTab;

               // sizeCtl 设置为新的数组长度的 3/4.即 3/4 *2n

               sizeCtl = (n << 1) - (n >>> 1);

               return;

           }

           // 到这，说明所有的迁移任务都分配完了

           // 当前线程也已经完成了自己的迁移任务（无论参与了几次迁移），

           // 则sc-1，表明参与扩容的线程数减1

           if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {

               // 迁移开始时，会设置 sc=(rs << RESIZE_STAMP_SHIFT) + 2

               // 每当有一个线程参与迁移，sc 就会加 1。

               // 因此，这里就是去校验当前 sc 是否和初始值相等。

               if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)

                   // 不相等，当前线程扩容任务结束。

                   return;

               // 相等，说明还有一个线程还在扩容迁移（不一定是触发扩容的第一个线程）

               // 则当前线程会从后向前检查一遍，哪些位置的节点没有复制完，就帮忙一起复制。

               // 一圈扫描下来，肯定是全部迁移完毕了，则finishing可提前设置为true。

               finishing = advance = true;

               i = n; // recheck before commit

           }

       }

       else if ((f = tabAt(tab, i)) == null)

           // （5）若i的位置元素为空，就把占位节点设置为fwd标志。

           // 设置成功，advance置为true，向前推进复制

           advance = casTabAt(tab, i, null, fwd);

       else if ((fh = f.hash) == MOVED)

           // （6）若当前位置的头结点是 ForwardingNode ，则说明这个位置的所有节点已经迁移完成，

           // 可以继续向前迁移复制其他位置的节点

           advance = true; // already processed

       else {

           // （7）对tab[i]进行迁移，可能是链表 or 红黑树

           synchronized (f) {

               if (tabAt(tab, i) == f) {

                   Node<K,V> ln, hn;

                   if (fh >= 0) {

                       // 链表

                       int runBit = fh & n;

                       Node<K,V> lastRun = f;

                       // lastRun并不是一条链表的最后一个，一条链表的节点可以分为两类，

                       // 在循环中寻找lastRun的满足条件是链表中最后一个与前一个节点runBit不相等的节点作为lastRun，

                       // 而此时lastRun后面可能还有节点，但runBit都是和lastRun相等的节点。

                       // 这里找lastRun和java7是一样的

                       for (Node<K,V> p = f.next; p != null; p = p.next) {

                           // 计算p的位置

                           int b = p.hash & n;

                           if (b != runBit) {

                               // 和runBit不是同一位置

                               runBit = b;

                               lastRun = p;

                           }

                       }

                       // hash & n=0为低位节点，hash & n!=0为高位节点。

                       // 判断找到的lastRun是低位节点还是高位节点

                       if (runBit == 0) {

                           ln = lastRun;

                           hn = null;

                       }

                       else {

                           hn = lastRun;

                           ln = null;

                       }

                       // lastRun之前的结点因为fh&n不确定，所以全部需要再hash分配。

                       for (Node<K,V> p = f; p != lastRun; p = p.next) {

                           int ph = p.hash; K pk = p.key; V pv = p.val;

                           if ((ph & n) == 0)

                               ln = new Node<K,V>(ph, pk, pv, ln);

                           else

                               hn = new Node<K,V>(ph, pk, pv, hn);

                       }

                       setTabAt(nextTab, i, ln);

                       setTabAt(nextTab, i + n, hn);

                       setTabAt(tab, i, fwd);

                       advance = true;

                   }

                   else if (f instanceof TreeBin) {

                       // 是红黑树，

                       // 原理上和链表迁移的过程差不多，也是将节点分成高位节点和低位节点

                       TreeBin<K,V> t = (TreeBin<K,V>)f;

                       // lo低位树头节点，loTail低位树尾节点

                       // hi高位树头节点，hiTail高位树尾节点

                       TreeNode<K,V> lo = null, loTail = null;

                       TreeNode<K,V> hi = null, hiTail = null;

                       int lc = 0, hc = 0;

                       for (Node<K,V> e = t.first; e != null; e = e.next) {

                           int h = e.hash;

                           TreeNode<K,V> p = new TreeNode<K,V>

                               (h, e.key, e.val, null, null);

                           if ((h & n) == 0) {

                               if ((p.prev = loTail) == null)

                                   lo = p;

                               else

                                   loTail.next = p;

                               // 尾插法

                               loTail = p;

                               ++lc;

                           }

                           else {

                               if ((p.prev = hiTail) == null)

                                   hi = p;

                               else

                                   hiTail.next = p;

                               hiTail = p;

                               ++hc;

                           }

                       }

                       // 低位节点的个数 <= UNTREEIFY_THRESHOLD=6, 则树退为链表

                       // 否则判断是否有高位节点，无，则原先那棵树t就是一棵低位树，直接赋值给ln

                       // 有高位节点，则低位节点重新树化。

                       // 高位节点的判断同理

                       ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :

                           (hc != 0) ? new TreeBin<K,V>(lo) : t;

                       hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :

                           (lc != 0) ? new TreeBin<K,V>(hi) : t;

                       setTabAt(nextTab, i, ln);

                       setTabAt(nextTab, i + n, hn);

                       setTabAt(tab, i, fwd);

                       advance = true;

                   }

               }

           }

       }

   }

}

9.CHM 的 put 方法源码?

public V put(K key, V value) {

   return putVal(key, value, false);

}

final V putVal(K key, V value, boolean onlyIfAbsent) {

   if (key == null || value == null) throw new NullPointerException();

   // 1. 哈希值高低位扰动

   int hash = spread(key.hashCode());

   int binCount = 0;

   for (Node<K,V>[] tab = table;;) {

       Node<K,V> f; int n, i, fh;

       if (tab == null || (n = tab.length) == 0)

           // 2. tab 为空 初始化 懒汉模式

           tab = initTable();

       else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {

           // 3. tab不为null，则通过(n - 1) & hash 计算 tab对应索引下标，找到node

           // node为null说明没有发生hash冲突，cas 设置新节点node到tab的对应位置，成功则结束循环

           if (casTabAt(tab, i, null,

                        new Node<K,V>(hash, key, value, null)))

               break;                   // no lock when adding to empty bin

       }

       else if ((fh = f.hash) == MOVED)

           // 4. 发现哈希值为MOVED时，

           // 说明数组正在扩容，帮助扩容，这个节点只可能是ForwardingNode

           tab = helpTransfer(tab, f);

       else {

           // 5.正常情况下发生哈希冲突

           V oldVal = null;

           synchronized (f) {

               // 再次检查i位置的节点是否还是f

               // 如果有变动则重新循环

               if (tabAt(tab, i) == f) {

                   if (fh >= 0) {

                       // 6. fh>=0 是链表

                       binCount = 1;

                       for (Node<K,V> e = f;; ++binCount) {

                           K ek;

                           if (e.hash == hash &&

                               ((ek = e.key) == key ||

                                (ek != null && key.equals(ek)))) {

                               // 链表中已经有hash相等且（key地址相等 or key值相等）

                               // 则判断是否需要替换

                               // put onlyIfAbsent=false，新值替换旧值

                               // putIfAbsent onlyIfAbsent=true,新值不替换旧值

                               oldVal = e.val;

                               if (!onlyIfAbsent)

                                   e.val = value;

                               break;

                           }

                           // 解决hash冲突的方式

                           // 链表法，新节点放在了链表尾部（尾插法），这里和jdk1.7不一样

                           Node<K,V> pred = e;

                           if ((e = e.next) == null) {

                               pred.next = new Node<K,V>(hash, key,

                                                         value, null);

                               break;

                           }

                       }

                   }

                   else if (f instanceof TreeBin) {

                       // 7.红黑树

                       Node<K,V> p;

                       binCount = 2;

                       if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,

                                                      value)) != null) {

                           // putTreeVal的返回值是已经存在的节点

                           // p != null 说明 key已经存在，看是否需要替换value

                           oldVal = p.val;

                           if (!onlyIfAbsent)

                               p.val = value;

                       }

                   }

               }

           }

           if (binCount != 0) {

               // 8. binCount，链表的长度>=8时 可能变为红黑树，也可能是扩容

               // 数组长度小于64时，是扩容数组

               if (binCount >= TREEIFY_THRESHOLD)

                   treeifyBin(tab, i);

               if (oldVal != null)

                   // 若旧值不为null，则说明是替换，不需要后面的addCount

                   return oldVal;

               break;

           }

       }

   }

   // 9. 元素数量+1

   addCount(1L, binCount);

   return null;

}

10.key 和 value 为什么不能为 null?

ConcurrentHashMap 中 key 和 value 为什么不能为 null 呢?下面从 HashMap 和 ConcurrentHashMap 的对比,详细说明.根据 HashMap 的源码可以知道,当 key 为 null 时，计算出的 hash 值为 0，value 放置在第 0 个桶上

//HashMap

static final int hash(Object key) {

   int h;

   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

根据 ConcurrentHashMap 源码可以知道,ConcurrentHashMap 没有像 HashMap 一样先计算 hash,先进行了判断 key 和 value 是否为 null,为 null 会抛出空值针异常,主要是因为存在二义性问题且 ConcurrentHashMap 没法解决

• 可能没有这个 key
  
• 可能有这个 key，只不过 value 为 null
  

因为 ConcurrentHashMap 是线程安全的，一般使用在并发环境下，你一开始 get 方法获取到 null 之后，再去调用 containsKey 方法，没法确保 get 方法和 containsKey 方法之间，没有别的线程来捣乱，刚好把你要查询的对象设置了进去或者删除掉了。

//ConcurrentHashMap

final V putVal(K key, V value, boolean onlyIfAbsent) {

 if (key == null || value == null) throw new NullPointerException();

 int hash = spread(key.hashCode());

 int binCount = 0;

 ......

}

11.jdk1.8 中 CHM 最大并发量

在 JDK1.8 中，ConcurrentHashMap 的并发性能得到了大幅提升，最大支持的并发量也有所增加。根据官方文档的描述，JDK1.8 中的 ConcurrentHashMap 最大可以同时支持并发读写操作的线程数是理论上的最大值，即 CPU 核心数乘以 2。

12.compute 方法

compute 方法具有原子性,保证 ConcurrentHashMap 的 get 和 put 的原子性。

compute方法有三个版本：

1. compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)：

• 这个方法会对给定的键执行指定的函数。
  
• 如果键不存在，函数将不会被执行，且方法会返回null。
  
• 如果函数返回的值为null，则键会被从ConcurrentHashMap中移除（如果存在的话）。
  
• 如果函数返回的值不为null，则新值会与键相关联。
  

2. computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction)：

• 这个方法会在键不存在时执行指定的函数。
  
• 如果键不存在，函数将被执行，返回的值会与键关联，并作为方法的返回值。
  
• 如果键已经存在，方法不会执行函数，直接返回已存在的值。
  

3. computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)：

• 这个方法会在键存在时执行指定的函数。
  
• 如果键存在，函数将被执行，返回的值会与键关联，并作为方法的返回值。
  
• 如果键不存在，方法不会执行函数，返回null。
  

这些compute方法允许你在多线程环境下以安全的方式更新ConcurrentHashMap中的键值对。由于它们的操作是原子性的，可以有效地避免竞态条件和数据不一致性问题。

public class Juc_29_question_ConcurrentHashMap_02 extends Thread {

   private static final ConcurrentHashMap<String, Integer> invokeMap = new ConcurrentHashMap<>();

   static {

       invokeMap.put("key", 0);

   }

   @Test

   public void test1() throws InterruptedException {

       for (int i = 0; i < 5; i++) {

           Juc_29_question_ConcurrentHashMap_02 thread = new Juc_29_question_ConcurrentHashMap_02();

           thread.start();

       }

   }

   @Override

   public void run() {

       System.out.println(invokeMap.compute("key", (key, value) -> value + 1));

   }

}

源码

public V compute(K key,

                    BiFunction<? super K, ? super V, ? extends V> remappingFunction) {

       if (key == null || remappingFunction == null)

           throw new NullPointerException();

       int h = spread(key.hashCode());

       V val = null;

       int delta = 0;

       int binCount = 0;

       for (Node<K,V>[] tab = table;;) {

           Node<K,V> f; int n, i, fh;

           if (tab == null || (n = tab.length) == 0)

               tab = initTable();

           else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {

               Node<K,V> r = new ReservationNode<K,V>();

               synchronized (r) {

                   if (casTabAt(tab, i, null, r)) {

                       binCount = 1;

                       Node<K,V> node = null;

                       try {

                           if ((val = remappingFunction.apply(key, null)) != null) {

                               delta = 1;

                               node = new Node<K,V>(h, key, val, null);

                           }

                       } finally {

                           setTabAt(tab, i, node);

                       }

                   }

               }

               if (binCount != 0)

                   break;

           }

           else if ((fh = f.hash) == MOVED)

               tab = helpTransfer(tab, f);

           else {

               synchronized (f) {

                   if (tabAt(tab, i) == f) {

                       if (fh >= 0) {

                           binCount = 1;

                           for (Node<K,V> e = f, pred = null;; ++binCount) {

                               K ek;

                               if (e.hash == h &&

                                   ((ek = e.key) == key ||

                                    (ek != null && key.equals(ek)))) {

                                   val = remappingFunction.apply(key, e.val);

                                   if (val != null)

                                       e.val = val;

                                   else {

                                       delta = -1;

                                       Node<K,V> en = e.next;

                                       if (pred != null)

                                           pred.next = en;

                                       else

                                           setTabAt(tab, i, en);

                                   }

                                   break;

                               }

                               pred = e;

                               if ((e = e.next) == null) {

                                   val = remappingFunction.apply(key, null);

                                   if (val != null) {

                                       delta = 1;

                                       pred.next =

                                           new Node<K,V>(h, key, val, null);

                                   }

                                   break;

                               }

                           }

                       }

                       else if (f instanceof TreeBin) {

                           binCount = 1;

                           TreeBin<K,V> t = (TreeBin<K,V>)f;

                           TreeNode<K,V> r, p;

                           if ((r = t.root) != null)

                               p = r.findTreeNode(h, key, null);

                           else

                               p = null;

                           V pv = (p == null) ? null : p.val;

                           val = remappingFunction.apply(key, pv);

                           if (val != null) {

                               if (p != null)

                                   p.val = val;

                               else {

                                   delta = 1;

                                   t.putTreeVal(h, key, val);

                               }

                           }

                           else if (p != null) {

                               delta = -1;

                               if (t.removeTreeNode(p))

                                   setTabAt(tab, i, untreeify(t.first));

                           }

                       }

                   }

               }

               if (binCount != 0) {

                   if (binCount >= TREEIFY_THRESHOLD)

                       treeifyBin(tab, i);

                   break;

               }

           }

       }

       if (delta != 0)

           addCount((long)delta, binCount);

       return val;

   }

或者

public class Juc_29_question_ConcurrentHashMap_01 extends Thread {

   private static final ConcurrentHashMap<String, Integer> invokeMap = new ConcurrentHashMap<>();

   private static final Object lock = new Object();  // 添加一个锁对象

   static {

       invokeMap.put("key", 0);

   }

   @Test

   public void test1() throws InterruptedException {

       for (int i = 0; i < 5; i++) {

           Juc_29_question_ConcurrentHashMap_01 thread = new Juc_29_question_ConcurrentHashMap_01();

           thread.start();

       }

   }

   @Override

   public void run() {

       synchronized (lock) {

           invokeMap.put("key", invokeMap.get("key") + 1);

           System.out.println(invokeMap);

       }

   }

}

13.computeIfAbsent

computeIfAbsent 是一个在 Java 编程语言中用于 Map 接口的方法，它允许你根据指定的键执行一个计算操作，如果该键在 Map 中不存在的话。如果键存在，则方法返回与该键关联的值；如果键不存在，则方法会执行给定的计算函数以生成一个值，并将键和生成的值放入 Map 中，然后返回该值。

以下是 computeIfAbsent 方法的签名：

V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)

其中：

• key 是你想要在 Map 中查找或添加的键。
  
• mappingFunction 是一个函数，它接受一个键作为输入并返回一个值。如果键不存在于 Map 中，这个函数会被调用，生成一个值，然后将该键和生成的值放入 Map 中。如果键已经存在于 Map 中，这个函数不会被调用，方法会直接返回与该键关联的值。
  

这个方法的用途在于，当你需要按需计算某个键对应的值时，可以使用它来避免重复计算，同时保持代码的简洁性和可读性。

以下是一个简单的示例，展示了如何使用 computeIfAbsent 方法：

import java.util.*;

public class ComputeIfAbsentExample {

   public static void main(String[] args) {

       Map<String, List<Integer>> map = new HashMap<>();

       // 使用 computeIfAbsent 添加值到 Map 中

      //这里add是在外层,注意看清楚写法

       map.computeIfAbsent("even", key -> new ArrayList<>()).add(2);

       map.computeIfAbsent("even", key -> new ArrayList<>()).add(4);

       map.computeIfAbsent("odd", key -> new ArrayList<>()).add(1);

       map.computeIfAbsent("odd", key -> new ArrayList<>()).add(3);

       System.out.println(map); // 输出: {even=[2, 4], odd=[1, 3]}

   }

}

在这个示例中，我们创建了一个 Map，然后使用 computeIfAbsent 方法将偶数和奇数分别添加到 "even" 和 "odd" 键所对应的列表中。由于 "even" 和 "odd" 键在 Map 中不存在，计算函数会被调用来生成一个新的列表，并将值添加到列表中。最后，我们输出了 Map，可以看到生成的结果。

14.computeIfPresent

computeIfPresent 是一个在 Java 编程语言中用于 java.util.Map 接口的方法。它是 Java 8 引入的一种函数式编程风格的方法，用于在映射中根据给定的键执行一个函数来更新键对应的值。

以下是 computeIfPresent 方法的方法签名：

V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)

这里的参数解释如下：

• key：要操作的键。
  
• remappingFunction：一个函数，接受两个参数，即键和当前与键相关联的值。它返回一个新的值，该值将替代旧值作为键的新值。如果函数返回 null，则表示删除键和其关联的值。
  

computeIfPresent 的作用是，当指定的键在映射中存在时，使用 remappingFunction 对当前值进行处理，然后将处理后的新值与键关联。如果键不存在，该方法不会执行任何操作。

以下是一个简单的示例，展示了 computeIfPresent 的用法：

import java.util.HashMap;

import java.util.Map;

public class ComputeIfPresentExample {

   public static void main(String[] args) {

       Map<String, Integer> map = new HashMap<>();

       map.put("one", 1);

       map.put("two", 2);

       // 使用 computeIfPresent 更新值

       map.computeIfPresent("one", (key, value) -> value + 10);

       // 输出更新后的映射

       System.out.println(map); // 输出: {one=11, two=2}

       // 尝试使用 computeIfPresent 更新不存在的键

       map.computeIfPresent("three", (key, value) -> value + 10);

       // 输出不变，因为键 "three" 不存在

       System.out.println(map); // 输出: {one=11, two=2}

   }

}

在上述示例中，computeIfPresent 方法用于更新键 "one" 对应的值，然后再尝试对不存在的键 "three" 使用该方法，但由于键 "three" 不存在，没有发生任何变化。

五.LinkedHashMap

1.LinkedHashMap 简介

LinkedHashMap 是 HashMap 的一个子类。它继承了 HashMap 的所有特性，同时还具有一些额外的功能，位于 java.util 包下。

与 HashMap 不同的是，LinkedHashMap 会保持元素插入的顺序，因此它是有序的。具体来说，LinkedHashMap 使用一个双向链表来维护插入顺序，而 HashMap 则不保证元素的遍历顺序。这使得 LinkedHashMap 可以按照元素插入的顺序进行迭代，并且这个迭代顺序不会随着时间的推移而改变。

2.LinkedHashMap 特点

LinkedHashMap的主要特性包括:

1. 有序性：维护元素插入的顺序，可以按照插入顺序进行迭代。
   
2. 基于 HashMap 实现：LinkedHashMap 底层使用 HashMap 来存储键值对，因此具有 HashMap 的高效查找和插入操作。
   
3. 可以选择按插入顺序或访问顺序排序：在构造 LinkedHashMap 对象时，可以选择按照插入顺序或者访问顺序（最近访问的元素放在最后）来排序。
   
4. 线程不安全：和 HashMap 一样，LinkedHashMap 也不是线程安全的。如果在多线程环境中使用，需要考虑同步措施。
   

默认情况下，LinkedHashMap 按照插入顺序进行排序。如果希望按照访问顺序进行排序，可以使用带有 accessOrder 参数的构造方法：

LinkedHashMap<K, V> linkedHashMap = new LinkedHashMap<>(initialCapacity, loadFactor, true);

在此构造方法中，accessOrder 为 true 表示按访问顺序排序，为 false 表示按插入顺序排序。

3.LinkedHashMap 双向链表？


数据结构：数组+单向链表+双向链表

每一个节点都是双向链表的节点，维持插入顺序。head 指向第一个插入的节点，tail 指向最后一个节点。

数组+单向链表是 HashMap 的结构，用于记录数据。

双向链表保存的是插入顺序，顺序访问。

next 是用于维护数据位置的，before 和 after 是用于维护插入顺序的。

// Entry继承HashMap的Node

static class Entry<K,V> extends HashMap.Node<K,V> {

 Entry<K,V> before, after;

 Entry(int hash, K key, V value, Node<K,V> next) {

   super(hash, key, value, next);

 }

}

/**

* The head (eldest) of the doubly linked list.

*/

// 旧数据放在head节点

transient LinkedHashMap.Entry<K,V> head;

/**

* The tail (youngest) of the doubly linked list.

*/

// 新数据放在tail节点

transient LinkedHashMap.Entry<K,V> tail;

/**

* The iteration ordering method for this linked hash map: <tt>true</tt>

* for access-order, <tt>false</tt> for insertion-order.

*

* @serial

*/

// false-按插入顺序存储数据 true-按访问顺序存储数据

final boolean accessOrder;

4.按 put 的顺序进行遍历？

可以使用 LinkedHashMap,有 2 种功能,一个是插入顺序,一个是访问顺序

初始化时可以指定。相对于访问顺序，插入顺序使用的场景更多一些，所以默认是插入顺序进行编排。

5.LinkedHashMap2 种遍历顺序？

LinkedHashMap 有两种遍历顺序,插入顺序和访问顺序

插入方式：遍历时和插入时位置固定

访问方式：put 和 get 方法都会将当前元素移到双向链表的最后

是否使用访问顺序遍历，是通过LinkedHashMap 的 accessOrder 参数控制的，true 为访问顺序遍历，false 为插入顺序遍历。默认是 false，插入方式遍历。如果是 true，注意并发修改异常。因为 get 方法会修改 LinkedHashMap 的结构。

• LinkedHashMap 的底层数据结构继承至 HashMap 的 Node，并且其内部存储了前驱和后继节点。
  
• LinkedHashMap 通过 accessOrder 来控制元素的相关顺序，false-按插入顺序存储数据，true-按访问顺序存储数据，默认为 false。
  

//默认插入顺序

public class Data_01_LinkedHashMapTest_02 {

 public static void main(String[] args) {

   LinkedHashMap<String, Integer> map = new LinkedHashMap<>(2, 0.75f, false);

   map.put("1", 1);

   map.put("5", 5);

   map.put("6", 6);

   map.put("2", 2);

   map.put("3", 3);

   map.get("5");

   map.get("6");

   for (Integer s : map.values()) {

     System.out.println(s);

   }

 }

}

//输出结果

1

5

6

2

3

//访问顺序

public class Data_01_LinkedHashMapTest_01 {

 public static void main(String[] args) {

   LinkedHashMap<String, Integer> map = new LinkedHashMap<>(2, 0.75f, true);

   map.put("1", 1);

   map.put("5", 5);

   map.put("6", 6);

   map.put("2", 2);

   map.put("3", 3);

   map.get("5");

   map.get("6");

   for (Integer s : map.values()) {

     System.out.println(s);

   }

 }

}

//输出结果,会把put和get操作的元素放在最后

1

2

3

5

6

6.LinkedHashMap 访问顺序的原理？

public LinkedHashMap(int initialCapacity,

                    float loadFactor,

                    boolean accessOrder) {

 super(initialCapacity, loadFactor);

 this.accessOrder = accessOrder;

}

关键点是 accessOrder 参数，默认为 false，插入方式，true 为访问方式。

当调用 get 方法时，会判断 accessOrder 的值，如果为 true，会执行 afterNodeAccess 方法，就是放到 node 的后面。

public V get(Object key) {

 Node<K,V> e;

 // 通过getNode方法取出节点，如果为null则直接返回null

 if ((e = getNode(hash(key), key)) == null)

   return null;

 // 如果accessOrder为true，则需要把节点移动到链表末尾

 if (accessOrder)

   afterNodeAccess(e);

 return e.value;

}

7.LinkedHashMap 的 put 方法的原理？

LinkedHashMap 没有 put 方法，使用的是 HashMap 的 put 方法，并且复写了 newNode 方法和 afterNodeAccess 方法。

新增的节点放到双向链表末尾

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {

   LinkedHashMap.Entry<K,V> p =

       new LinkedHashMap.Entry<K,V>(hash, key, value, e);

   linkNodeLast(p);

   return p;

}

将新增的节点添加至链表尾部

void afterNodeAccess(Node<K,V> e) { // move node to last

   LinkedHashMap.Entry<K,V> last;

   if (accessOrder && (last = tail) != e) {

       LinkedHashMap.Entry<K,V> p =

           (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;

       p.after = null;

       if (b == null)

           head = a;

       else

           b.after = a;

       if (a != null)

           a.before = b;

       else

           last = b;

       if (last == null)

           head = p;

       else {

           p.before = last;

           last.after = p;

       }

       tail = p;

       ++modCount;

   }

}

8.LinkedHashMap 的 get 方法原理？

会判断是否是访问顺序，如果是，放到双向链表末尾。

JDK1.8 的 HashMap 的 get 方法

• 计算数据在桶中的位置 (tab.length- 1) & hash(key)
  
• 通过 hash 值和 key 值判断待查找的数据是否在对应桶的首节点， 如果在，则返回对应节点 据；否则判断桶首节点的类型。如果节点 为红黑树，从红黑树中获取对应数据；如果节点为链表节点，则遍历 链表，从中获取对应数据
  

public V get(Object key) {

 Node<K,V> e;

 if ((e = getNode(hash(key), key)) == null)

     return null;

 if (accessOrder)

     afterNodeAccess(e);

 return e.value;

}

9.用 LinkedHashMap 实现 LRU 算法？

主要考察 2 个点

• accessOrder 实现 lru 的逻辑
  
• removeEldestEntry 的复写
  

在插入之后，会调用 LinkedHashMap 的 afterNodeInsertion 方法，需要重写 removeEldestEntry 方法

void afterNodeInsertion(boolean evict) { // possibly remove eldest

   LinkedHashMap.Entry<K,V> first;

   if (evict && (first = head) != null && removeEldestEntry(first)) {

       K key = first.key;

       removeNode(hash(key), key, null, false, true);

   }

}

class Scratch<K, V> extends LinkedHashMap<K, V> {

 private int capacity;

 public Scratch(int capacity) {

   super(16, 0.75f, true);

   this.capacity = capacity;

 }

 @Override

 protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {

   return size() > capacity;

 }

}

10.LinkedHashMap 和 HashMap 区别？

• LinkedHashMap 继承自 HashMap，是基于 HashMap 和双向链表实现的。并实现了 HashMap 中预留的钩子函数,因此不必重写 HashMap 的很多方法，设计非常巧妙。
  
• HashMap 是无序的，LinkedHashMap 是有序的，分为插入顺序和访问顺序。如果是访问顺序，使用 put 和 get 时，都会把 entry 移动到双向链表的表尾。
  
• LinkedHashMap 存取数据还是和 HashMap 一样，使用 entry[]数组的形式，双向链表只是为了保证顺序。
  
• LinkedHashMap 也是线程不安全的。
  
• LinkedHashMap 默认容量为 16，扩容因子默认为 0.75，非同步，允许[key,value]为 null。LinkedHashMap 底层数据结构为双向链表，可以看成是 LinkedList+HashMap。如果 accessOrder 为 false，则可以按插入元素的顺序遍历元素，如果 accessOrder 为 true，则可以按访问顺序遍历元素。
  

六.其他 Map

1.什么是 TreeMap?

TreeMap 是 Java 编程语言中的一个类，它实现了 SortedMap 接口，并且是 NavigableMap 接口的一个具体实现。它是一个基于红黑树数据结构的有序映射（键值对）集合，可以用来存储键值对，并根据键的自然顺序或自定义排序规则对键进行排序。

TreeMap 中的元素是按照键的顺序进行排序的，因此它是有序的。具体的排序顺序取决于键的比较方式。如果键的类型实现了 Comparable 接口，TreeMap 会使用键的自然顺序进行排序。如果键的类型没有实现 Comparable 接口，你也可以在构造 TreeMap 对象时提供一个 Comparator 对象来指定自定义的排序规则。

2.TreeMap 特点

TreeMap的主要特性包括:

1. 有序性：元素按照键的顺序进行排序，可以通过键的自然顺序或自定义比较器来实现。
   
2. 基于红黑树：TreeMap 底层使用红黑树这种自平衡二叉搜索树数据结构来存储键值对。这使得查找、插入和删除操作的时间复杂度为 O(log n)，保证了较高的性能。
   
3. 线程不安全：和 HashMap 一样，TreeMap 也不是线程安全的。如果在多线程环境中使用，需要考虑同步措施。
   
4. 支持导航方法：TreeMap 提供了许多导航方法，比如获取最小/最大键、获取小于/大于某个键的最接近键等等。
   

3.TreeMap 构造方法

使用 TreeMap 时，常见的构造方式如下：

TreeMap<K, V> treeMap = new TreeMap<>();

这将创建一个按键的自然顺序进行排序的 TreeMap。

如果要创建一个按照自定义排序规则排序的 TreeMap，可以使用带有 Comparator 参数的构造方法：

TreeMap<K, V> treeMap = new TreeMap<>(customComparator);

TreeMap 适用于需要在键的顺序上进行操作的场景，并提供了快速的查找和有序遍历能力。由于它基于红黑树实现，适用于大量数据的高效存储和操作。

4.说说 WeakHashMap?

• WeakHashMap 非同步，默认容量为 16，扩容因子默认为 0.75，底层数据结构为 Entry 数组（数组+链表）。
  
• WeakHashMap 中的弱引用 key 会在下一次 GC 被清除，注意只会清除 key，value 会在每次 map 操作中清除。
  
• 在 WeakHashMap 中强引用的 key 是不会被 GC 清除的。
  

5.ConcurrentSkipListMap

ConcurrentSkipListMap 是在 JDK 1.6 中新增的，为了对高并发场景下的有序 Map 提供更好的支持

它有几个特点:

• 高并发场景
  
• key 是有序的
  
• 添加、删除、查找操作都是基于跳表结构（SkipList）实现的
  
• key 和 value 都不能为 null
  

而跳表结合了树和链表的特点，其特性如下：

• 跳表由很多层组成；
  
• 每一层都是一个有序的链表；
  
• 最底层的链表包含所有元素；
  
• 对于每一层的任意一个节点，不仅有指向其下一个节点的指针，也有指向其下一层的指针；
  
• 如果一个元素出现在 Level n 层的链表中，则它在 Level n 层以下的链表也都会出现。
  

6.ConcurrentSkipListMap 结构

ConcurrentSkipListMap 用到了两种结构的节点。

Node 节点代表了真正存储数据的节点，包含了 key、value、指向下一个节点的指针 next：

static final class Node<K,V> {

 final K key;     // 键

 V val;           // 值

 Node<K,V> next;  // 指向下一个节点的指针

 Node(K key, V value, Node<K,V> next) {

   this.key = key;

   this.val = value;

   this.next = next;

 }

}

Index 节点代表了跳表的层级,层级节点，包含了当前节点 node、下一层 down、当前层的下一个节点 right：

static final class Index<K,V> {

 final Node<K,V> node;   // 当前节点

 final Index<K,V> down;  // 下一层

 Index<K,V> right;       // 当前层的下一个节点

 Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {

   this.node = node;

   this.down = down;

   this.right = right;

 }

}

如图所示，Node 节点将真实的数据按顺序链接起来，Index 节点组成了跳表中多层次的索引结构。


七.ConcurrentNavigableMap

ConcurrentNavigableMap 是一个接口,ConcurrentSkipListMap 是 ConcurrentNavigableMap 的一个实现类

1.headMap

headMap（T toKey）方法返回小于给定键的键的映射视图。

//ConcurrentSkipListMap

public ConcurrentNavigableMap<K,V> headMap(K toKey,  boolean inclusive) {

   if (toKey == null) throw new NullPointerException();

   return new SubMap<K,V> (this, null, false, toKey, inclusive, false);

}

SubMap(ConcurrentSkipListMap<K,V> map,

            K fromKey, boolean fromInclusive,

            K toKey, boolean toInclusive,

            boolean isDescending) {

         Comparator<? super K> cmp = map.comparator;

         if (fromKey != null && toKey != null &&

             cpr(cmp, fromKey, toKey) > 0)

             throw new IllegalArgumentException("inconsistent range");

         this.m = map;

         this.lo = fromKey;

         this.hi = toKey;

         this.loInclusive = fromInclusive;

         this.hiInclusive = toInclusive;

         this.isDescending = isDescending;

}

public static void main(String[] args) {

     ConcurrentNavigableMap map = new ConcurrentSkipListMap();

     map.put("1", "one");

     map.put("2", "two");

     map.put("3", "three");

     map.put("4", "three");

     map.put("5", "three");

     map.put("6", "three");

     map.put("7", "three");

     ConcurrentNavigableMap headMap = map.headMap("5");

     Set<String> keySet = headMap.keySet();

     for (String key : keySet) {

         System.out.println("key:" + key + " , value:" + headMap.get(key));

     }

}

//输出 1,2,3,4

2.tailMap

tailMap(T fromKey)方法将返回包含或者大于fromKey的map视图 .

如果改变原来的map，这些变化也会影响tail map。

public ConcurrentNavigableMap<K,V> tailMap(K fromKey,

                                              boolean inclusive) {

       if (fromKey == null)

           throw new NullPointerException();

       return new SubMap<K,V>

           (this, fromKey, inclusive, null, false, false);

   }

public static void main(String[] args) {

     ConcurrentNavigableMap map = new ConcurrentSkipListMap();

     map.put("1", "one");

     map.put("2", "two");

     map.put("3", "three");

     map.put("4", "three");

     map.put("5", "three");

     map.put("6", "three");

     map.put("7", "three");

     ConcurrentNavigableMap headMap = map.tailMap("5");

     Set<String> keySet = headMap.keySet();

     for (String key : keySet) {

         System.out.println("key:" + key + " , value:" + headMap.get(key));

     }

 }

//返回5,6,7

3.subMap

subMap()方法返回了一个从 from (including)到 to (excluding)的 map 试图，并且 key 大于等于 from 小于 to

public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {

       return subMap(fromKey, true, toKey, false);

   }

public static void main(String[] args) {

     ConcurrentNavigableMap map = new ConcurrentSkipListMap();

     map.put("1", "one");

     map.put("5", "three");

     map.put("2", "two");

     map.put("3", "three");

     map.put("4", "three");

     map.put("6", "three");

     map.put("7", "three");

     ConcurrentNavigableMap headMap = map.subMap("3", "5");

     Set<String> keySet = headMap.keySet();

     for (String key : keySet) {

         System.out.println("key:" + key + " , value:" + headMap.get(key));

     }

 }

//输出 3,4

4.descendingKeySet

倒序排列 key

public static void main(String[] args) {

     ConcurrentNavigableMap map = new ConcurrentSkipListMap();

     map.put("1", "one");

     map.put("5", "three");

     map.put("2", "two");

     map.put("3", "three");

     map.put("4", "three");

     map.put("6", "three");

     map.put("7", "three");

     final NavigableSet navigableSet = map.descendingKeySet();

     System.out.println(JSON.toJSONString(navigableSet));

 }

5.navigableKeySet

正序排列 key

public static void main(String[] args) {

     ConcurrentNavigableMap map = new ConcurrentSkipListMap();

     map.put("1", "one");

     map.put("5", "three");

     map.put("2", "two");

     map.put("3", "three");

     map.put("4", "three");

     map.put("6", "three");

     map.put("7", "three");

     final NavigableSet navigableSet = map.navigableKeySet();

     System.out.println(JSON.toJSONString(navigableSet));

 }

6.descendingMap

倒序排列 map

public static void main(String[] args) {

     ConcurrentNavigableMap map = new ConcurrentSkipListMap();

     map.put("1", "one");

     map.put("5", "three");

     map.put("2", "two");

     map.put("3", "three");

     map.put("4", "three");

     map.put("6", "three");

     map.put("7", "three");

     ConcurrentNavigableMap<Integer, String> descendingMap = map.descendingMap();

     System.out.println(JSON.toJSONString(descendingMap));

}

7.ceilingEntry

获取指定 key 的 map

public static void main(String[] args) {

     ConcurrentNavigableMap map = new ConcurrentSkipListMap();

     map.put("1", "one");

     map.put("5", "three");

     map.put("2", "two");

     map.put("3", "three");

     map.put("4", "three");

     map.put("6", "three");

     map.put("7", "three");

     Map.Entry<String, String> ceilingEntry = map.ceilingEntry("4");

     System.out.println(JSON.toJSONString(ceilingEntry));

 }

8.ceilingKey

获取指定 key 的 key

public static void main(String[] args) {

     ConcurrentNavigableMap map = new ConcurrentSkipListMap();

     map.put("1", "one");

     map.put("5", "three");

     map.put("2", "two");

     map.put("3", "three");

     map.put("4", "three");

     map.put("6", "three");

     map.put("7", "three");

     String ceilingKey = (String) map.ceilingKey("4");

     System.out.println(JSON.toJSONString(ceilingKey));

 }

9.lastEntry

//取比当前key大一个的map值

 Map.Entry<Integer, String> higherEntry = concurrentNavigableMap.higherEntry(2);

 System.out.println(JSON.toJSONString(higherEntry));

 //取比当前key小一个的map值

 Map.Entry<Integer, String> lowerEntry = concurrentNavigableMap.lowerEntry(2);

 System.out.println(JSON.toJSONString(lowerEntry));

 //取最后一个map值

 Map.Entry<Integer, String> lastEntry = concurrentNavigableMap.lastEntry();

 System.out.println(JSON.toJSONString(lastEntry));

八.Map 汇总问题

1.存储 null 值的情况

2.常用的 Map？


3.讨论下 map 的性能？


前提：IdentityHashMap 不在讨论范围内。数据 100W，机器指标 I3 处理区，4G 内存。单线程环境。

• Hashtable 和 HashMap 性能差不多， 因为是单线程环境，其实 table 和 map 最显著的区别就是同步问题，没有同步问题，两者的性能区别不是很大， 就像我们经常所说的， Hashtable 会慢一点，因为是同步的.
  
• LinkedHashSet,不多说，维护双向顺序链表，肯定会累一点，慢一点。其中插入操作慢的更加显著。
  
• TreeMap，红黑树结构的有序 map。 如果对存入的数据顺序没有要求的话，TreeMap 的性能慢的比较显著，因为红黑树需要进行平衡的旋转变色 。况且，多数情况下，HashMap 的存取时间复杂度都是 O（1），红黑树是 O(logn)，所以 treemap 慢一点，正常。