Map

Map

java.util.Map<k,v>接口

Map集合的特点:

• Map集合是一个双列集合,一个元素包含两个值(一个key,一个value)
• Map集合中的元素,key和value的数据类型可以相同,也可以不同
• Map集合中的元素,key是不允许重复的,value是可以重复的
• Map集合中的元素,key和value是一一对应

Map接口中的常用方法

public V put(K key, V value)：把指定的键与指定的值添加到Map集合中。如果该key存在，返回旧的value，否则返回null

public V remove(Object key)：把指定的键所对应的键值对元素 在Map集合中删除，返回被删除元素的值。

public V get(Object key)：根据指定的键，在Map集合中获取对应的值。找不到返回null

boolean containsKey(Object key)：判断集合中是否包含指定的键。

public Set< K > keySet()：获取Map集合中所有的键，存储到Set集合中。

public Set<Map.Entry<K,V>> entrySet()：获取到Map集合中所有的键值对对象的集合(Set集合)。

default V getOrDefault(Object key, V defaultValue)方法：当Map集合中有这个key时，就获取这个key值的值；如果没有就返回默认值defaultValue

public static void main(String[] args) {
    Map<String, String> map = new HashMap<>();
    map.put("name", "lxj");
    map.put("age", "24");
    map.put("sex", "女");
    String name = map.getOrDefault("name", "test");
    System.out.println(name);// lxj，map中存在name,获得name对应的value
    String address = map.getOrDefault("address", "北京");
    System.out.println(address);// 北京，map中不存在address,使用默认值“北京”
}

HashMap集合

java.util.HashMap<k,v> implements Map<k,v>接口

• HashMap集合底层是哈希表：查询的速度特别的快
• hashMap集合是一个无序的集合，存储元素和取出元素的顺序有可能不一致

底层实现：

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

public class MapDemo {
  public static void main(String[] args) {
    //创建 map对象
    HashMap<String, String> map = new HashMap<String, String>();

    //添加元素到集合
    map.put("黄晓明", "杨颖");
    map.put("文章", "马伊琍");
    map.put("邓超", "孙俪");
    System.out.println(map); //{邓超=孙俪, 文章=马伊琍, 黄晓明=杨颖}

    //String remove(String key)
    System.out.println(map.remove("邓超"));
    System.out.println(map);

    // 想要查看黄晓明的媳妇是谁
    System.out.println(map.get("黄晓明"));
    System.out.println(map.get("邓超"));  
  }
}

tips:

• 使用put方法时，若指定的键(key)在集合中没有，则没有这个键对应的值，返回null，并把指定的键值添加到集合中
• 若指定的键(key)在集合中存在，则返回值为集合中键对应的值（该值为替换前的值），并把指定键所对应的值，替换成指定的新值。

Map集合遍历方法

Map集合遍历第一种方式：键找值方式

获取May中所有的Key的集合Set，然后通过元素中的键，获取键所对应的值

分析步骤：

• 获取Map中所有的键，由于键是唯一的，所以返回一个Set集合存储所有的键。方法：keyset()
• 遍历键的Set集合，得到每一个键key。
• 根据键，获取键所对应的值。方法：Map.get(K key)

public class MapDemo01 {
  public static void main(String[] args) {
    //创建Map集合对象
    HashMap<String, String> map = new HashMap<String,String>();
    //添加元素到集合
    map.put("胡歌", "霍建华");
    map.put("郭德纲", "于谦");
    map.put("薛之谦", "大张伟");
    //获取所有的键 获取键集
    Set<String> keys = map.keySet();
    // 遍历键集 得到 每一个键
    for (String key : keys) {
      //key 就是键
      //获取对应值
      String value = map.get(key); //使用get方法可获得键对应的值
      System.out.println(key+"的CP是："+value);
    } 
  }
}

Map集合遍历的第二种方式: 使用Entry对象遍历

使用Map集合中的方法Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射关系的 Set 视图，即键值对对象的集合。

实现步骤:

• 使用Map集合中的方法entrySet(),把Map集合中多个Entry对象取出来,存储到一个Set集合中
• 遍历Set集合,获取每一个Entry对象
• 使用Entry对象中的方法**getKey()和getValue()**获取键与值

public class MapDemo02 {
  public static void main(String[] args) {
    // 创建Map集合对象
    HashMap<String, String> map = new HashMap<String,String>();
    // 添加元素到集合
    map.put("胡歌", "霍建华");
    map.put("郭德纲", "于谦");
    map.put("薛之谦", "大张伟");
    // 获取所有的 entry对象 entrySet
    Set<Map.Entry<String,String>> entrySet = map.entrySet();
    // 遍历得到每一个entry对象
    for (Entry<String, String> entry : entrySet) {
      // 解析
      String key = entry.getKey();
      String value = entry.getValue(); 
      System.out.println(key+"的CP是:"+value);
    }
  }
}

tips：Map集合不能直接使用迭代器或者foreach进行遍历。但是转成Set之后就可以使用了。

HashMap存储自定义类型必须复写对象的hashCode和equals方法

为什么？

如果两个对象的hashCode 值相等，那这两个对象不一定相等（哈希碰撞）。

如果两个对象的hashCode 值相等并且equals()方法也返回 true，我们才认为这两个对象相等。

如果两个对象的hashCode 值不相等，我们就可以直接认为这两个对象不相等。

比如两个Person对象p1和p2，他们的属性值完全相同，我们在重写equals时可以判断他们时相同的对象，但因为p1和p2的HashCode不相同，所有在添加元素时会发现添加了相同的对象，所以必须使用Objects的hash根据对象的需要比较的值生成新的hashCode

public int hashCode() {
   return Objects.hash(name, age);
   }
}

hashCode()调用Objects类中的hash方法，把需要比较的值放入一个数组再进行hashCode比较

public static int hash(Object... values) {
  return Arrays.hashCode(values);

}

练习：每位学生（姓名，年龄）都有自己的家庭住址。那么，既然有对应关系，则将学生对象和家庭住址存储到map集合中。学生作为键, 家庭住址作为值。

注意，学生姓名相同并且年龄相同视为同一人。所以要重写equals和hashcode方法

public class Person {
   private String name;
   private int age;

@Override
public String toString() {
   return "Person{" +
   "name='" + name + '\'' +
   ", age=" + age +
   '}';
}

@Override
public boolean equals(Object o) {
   if (this == o) return true;
   if (o == null || getClass() != o.getClass()) return false;
   Person person = (Person) o;
   return age == person.age &&
   Objects.equals(name, person.name);
}

@Override
public int hashCode() {
   return Objects.hash(name, age);
   }
}

编写测试类：

private static void show02() {
//创建HashMap集合
HashMap<Person,String> map = new HashMap<>();

//往集合中添加元素
map.put(new Person("女王",18),"英国");
map.put(new Person("秦始皇",18),"秦国");
map.put(new Person("普京",30),"俄罗斯");
map.put(new Person("女王",18),"毛里求斯"); //key唯一，会覆盖第一个


//使用entrySet和增强for遍历Map集合
Set<Map.Entry<Person, String>> set = map.entrySet();
for (Map.Entry<Person, String> entry : set) {
   Person key = entry.getKey();
   String value = entry.getValue();
  System.out.println(key+"-->"+value);

}

HashMap中put的过程？

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

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

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

HashMap 为什么线程不安全？

JDK1.7 及之前版本，在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。

数据丢失这个在 JDK1.7 和 JDK 1.8 中都存在，这里以 JDK 1.8 为例进行介绍。

JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。

举个例子：

• 两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。
• 不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。
• 随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    // ...
    // 判断是否出现 hash 碰撞
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素（处理hash冲突）
    else {
    // ...
}

还有一种情况是这两个线程同时 put 操作导致 size 的值不正确，进而导致数据覆盖的问题：

1. 线程 1 执行 if(++size > threshold) 判断时，假设获得 size 的值为 10，由于时间片耗尽挂起。
2. 线程 2 也执行 if(++size > threshold) 判断，获得 size 的值也为 10，并将元素插入到该桶位中，并将 size 的值更新为 11。
3. 随后，线程 1 获得时间片，它也将元素放入桶位中，并将 size 的值更新为 11。
4. 线程 1、2 都执行了一次 put 操作，但是 size 的值只增加了 1，也就导致实际上只有一个元素被添加到了 HashMap 中。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    // ...
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

HashMap 多线程操作导致死循环问题

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap 。

一般面试中这样介绍就差不多，不需要记各种细节，个人觉得也没必要记。如果想要详细了解 HashMap 扩容导致死循环问题，可以看看耗子叔的这篇文章：Java HashMap 的死循环

解释一下HashMap的扩容机制

HashMap 的扩容机制是为了保持哈希表的装载因子（Load Factor）在一个合理的范围内，以维持查询、插入和删除操作的性能。装载因子是哈希表中已存储元素个数与数组容量的比值。

扩容的目的是在哈希表中元素逐渐增加时，防止哈希冲突的发生，保持桶中链表或红黑树的长度在一个可接受的范围，从而维护 HashMap 的性能。

HashMap 的扩容机制分为以下几个步骤：

1. 装载因子检查： 在进行插入操作时，会先检查当前装载因子是否超过了预设的阈值（通常为 0.75）。如果超过了这个阈值，就触发扩容操作。
2. 创建新的数组： 创建一个新的数组，其长度通常是原数组的两倍。新数组的长度总是取2的幂次方，这样有助于保持哈希函数的均匀分布。
3. 重新哈希： 将原数组中的每个元素重新计算哈希值，并放入新的数组中。由于数组长度变化，元素在新数组中的位置可能会不同。
4. 迁移数据： 将原数组中的每个桶中的链表或红黑树的元素逐个迁移到新数组中的对应桶。这一过程是比较耗时的，但只会在扩容时进行一次。
5. 更新引用： 将 HashMap 内部的数组引用指向新的数组。

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

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

因为$2^n-1$的二进制必定是1111…，对于任何整数 x，x & 1 的结果是 x 的最低位（最右边的位）。

(length - 1) & hash 的结果就是 hash 的最低位

位运算是可以直接操作底层数据的，不用进行进制转换，效率更高

HashCode的哈希值是怎么确定的

Object 的 hashCode() 方法是本地方法，也就是用 C 语言或 C++ 实现的。

⚠️ 注意：该方法在 Oracle OpenJDK8 中默认是 “使用线程局部状态来实现 Marsaglia’s xor-shift 随机数生成”, 并不是 “地址” 或者 “地址转换而来”, 不同 JDK/VM 可能不同在 Oracle OpenJDK8 中有六种生成方式 (其中第五种是返回地址), 通过添加 VM 参数: -XX:hashCode=4 启用第五种。

LinkedHashMap

• LinkedHashMap集合底层是哈希表+链表(保证迭代的顺序)

• LinkedHashMap集合是一个有序的集合，存储元素和取出元素的顺序是一致的

LinkedHashMap<String,String> linked = new LinkedHashMap<>();
linked.put("a","a");
linked.put("c","c");
linked.put("b","b");
linked.put("a","d");
System.out.println(linked);// key不允许重复,存和取得顺序一样 {a=d, c=c, b=b}

TreeMap

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

• LinkedHashMap是HashMap的子类
• 在HashMap存储结构的基础上，使用了一对双向链表来记录添加元素的顺序
• 与LinkedHashSet类似，LinkedHashMap可以维护Map 的迭代顺序：迭代顺序与Key-Value 对的插入顺序一致

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

注意：不允许key值为空

public class Person {
    private Integer age;
    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }

    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

Map按照value自定义排序

Map<String, Integer> map = new HashMap<>();
map.put("张三",12);
map.put("李四",23);
map.put("王五",15);
map.put("赵六",19);

//第一种方式
ArrayList<Map.Entry<String, Integer>> entryList = new ArrayList<>(map.entrySet());
entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
    @Override
    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
        return o2.getValue() - o1.getValue();
    }
});
for (Map.Entry<String, Integer> entry : entryList) {
    System.out.println(entry.getValue());
}



//第二种方式
map.entrySet().stream().sorted(new Comparator<Map.Entry<String, Integer>>() {
    @Override
    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
        return o2.getValue() - o1.getValue();
    }
}).forEach(System.out::println);

输出

23
19
15
12

HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap	HashSet
实现了 Map 接口	实现 Set 接口
存储键值对	仅存储对象
调用 put()向 map 中添加元素	调用 add()方法向 Set 中添加元素
HashMap 使用键（Key）计算 hashcode	HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以equals()方法用来判断对象的相等性

HashMap 和 Hashtable 的区别

• 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的，因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；

• 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；

• 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。

• 初始容量大小和每次扩充容量大小的不同： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

• 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间。Hashtable 没有这样的机制。

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

• 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
• 实现线程安全的方式（重要）：
  • 在 JDK1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
  • 到了 JDK1.8 的时候，ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本
  • Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

下面，我们再来看看两者底层数据结构的对比图

Hashtable :

Hashtable 的内部结构

JDK1.7 的 ConcurrentHashMap：

Java7 JDK1.7ConcurrentHashMap 存储结构

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的

JDK1.8 的 ConcurrentHashMap：

JDK1.8 的 ConcurrentHashMap 不再是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 **TreeNode**。当冲突链表达到一定长度时，链表会转换成红黑树。

TreeNode是存储红黑树节点，被TreeBin包装。TreeBin通过root属性维护红黑树的根结点，因为红黑树在旋转的时候，根结点可能会被它原来的子节点替换掉，在这个时间点，如果有其他线程要写这棵红黑树就会发生线程不安全问题，所以在 ConcurrentHashMap 中TreeBin通过waiter属性维护当前使用这棵红黑树的线程，来防止其他线程的进入。

ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。

Java 8 中，锁粒度更细，**synchronized 只锁定当前链表或红黑二叉树的首节点**，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

总结：

线程安全实现方式：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。

Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。

并发度：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。

多线程环境的map为什么 key 和 value 不能为 null？

ConcurrentHashMap 的 key 和 value 不能为 null 主要是为了避免二义性。null 是一个特殊的值，表示没有对象或没有引用。如果你用 null 作为键，那么你就无法区分这个键是否存在于 ConcurrentHashMap 中，还是根本没有这个键。同样，如果你用 null 作为值，那么你就无法区分这个值是否是真正存储在 ConcurrentHashMap 中的，还是因为找不到对应的键而返回的。

拿 get 方法取值来说，返回的结果为 null 存在两种情况：

• 值没有在集合中 ；
• 值本身就是 null。

在单线程情况下，可以通过containsKey直接判断key是否存在集合中，避免了二义性问腿

多线程环境下，存在一个线程操作该 ConcurrentHashMap 时，其他的线程将该 ConcurrentHashMap 修改的情况，所以无法通过 containsKey(key) 来判断否存在这个键值对，也就没办法解决二义性问题了。

比如：线程A调用map.containsKey 方法之前，另一个线程 B 执行了 map.put(key,null) 的操作。那么线程 A 调用的 map.containsKey 方法返回的就是 true 了，与预期为false不符

与此形成对比的是，HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。如果传入 null 作为参数，就会返回 hash 值为 0 的位置的值。单线程环境下，不存在一个线程操作该 HashMap 时，其他的线程将该 HashMap 修改的情况，所以可以通过 contains(key)来做判断是否存在这个键值对，从而做相应的处理，也就不存在二义性问题。

也就是说，多线程下无法正确判定键值对是否存在（存在其他线程修改的情况），单线程是可以的（不存在其他线程修改的情况）。

ConcurrentHashMap 能保证复合操作的原子性吗？

ConcurrentHashMap 是线程安全的，意味着它可以保证多个线程同时对它进行读写操作时，不会出现数据不一致的情况，也不会导致 JDK1.7 及之前版本的 HashMap 多线程操作导致死循环问题。但是，这并不意味着它可以保证所有的复合操作都是原子性的，一定不要搞混了！

复合操作是指由多个基本操作(如put、get、remove、containsKey等)组成的操作，例如先判断某个键是否存在containsKey(key)，然后根据结果进行插入或更新put(key, value)。这种操作在执行过程中可能会被其他线程打断，导致结果不符合预期。

例如，有两个线程 A 和 B 同时对 ConcurrentHashMap 进行复合操作，如下：

// 线程 A
if (!map.containsKey(key)) {
map.put(key, value);
}
// 线程 B
if (!map.containsKey(key)) {
map.put(key, anotherValue);
}

如果线程 A 和 B 的执行顺序是这样：

1. 线程 A 判断 map 中不存在 key
2. 线程 B 判断 map 中不存在 key
3. 线程 B 将 (key, anotherValue) 插入 map
4. 线程 A 将 (key, value) 插入 map

那么最终的结果是 (key, value)，而不是预期的 (key, anotherValue)。这就是复合操作的非原子性导致的问题。

如何保证 ConcurrentHashMap 复合操作的原子性？

ConcurrentHashMap 提供了一些原子性的复合操作，如 putIfAbsent、compute、computeIfAbsent 、computeIfPresent、merge等。这些方法都可以接受一个函数作为参数，根据给定的 key 和 value 来计算一个新的 value，并且将其更新到 map 中。

上面的代码可以改写为：

// 线程 A
map.putIfAbsent(key, value);
// 线程 B
map.putIfAbsent(key, anotherValue);

或者：

// 线程 A
map.computeIfAbsent(key, k -> value);
// 线程 B
map.computeIfAbsent(key, k -> anotherValue);

很多同学可能会说了，这种情况也能加锁同步呀，确实可以，但不建议使用加锁的同步机制，违背了使用 ConcurrentHashMap 的初衷。在使用 ConcurrentHashMap 的时候，尽量使用这些原子性的复合操作方法来保证原子性。

红黑树基本原理

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在插入和删除操作后能够保持树的平衡，确保树的高度大致为对数级别，从而使得查找、插入和删除操作的时间复杂度都是O(log n)。红黑树的基本性质包括：

1. 节点颜色：每个节点要么是红色，要么是黑色。
2. 根节点：根节点是黑色的。
3. 叶子节点：所有叶子节点（NIL节点，空节点）都是黑色的。
4. 红色性质：每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
5. 黑色性质：从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（黑高相同）
6. 平衡性质：从根到叶子的最长路径不会超过最短路径的两倍。

这些性质确保了红黑树在最坏情况下仍然是平衡的，即*树的高度不会超过2log(N+1)**，其中N是树中节点的数量。这使得红黑树在插入和删除操作时能够快速重新平衡，保持操作的效率。