有做公司网站的吗/百度热门排行榜

HashMap是面试的常客了，为了准备面试，重新整理了一下关于HashMap的知识，人给整麻了。

先来几个简单的面试问题：

• HashMap如何解决哈希冲突？

• HashMap如何扩容？

• HashMap在多线程环境下会出现什么问题？

  ……

是不是很简单，可惜我一个都不会！！！

下面我将从头开始介绍

1. 什么 是HashMap

HashMap是一种基于哈希表实现的数据结构，它实现了 Map 接口，可以存储键值对(key-value)映射，根据键的HashCode值快速访问和操作数据。

在 JDK 1.7及以前底层实现是一个 数组 + 链表 的形式，而在 JDK 1.8后 底层是 数组 + 链表 + 红黑树 。本次讲解主要基于JDK1.8

哈希表由一个数组和链表组成, 它将键值对存储在一个数组中，数组中每个元素都是一个链表的头节点。当我们插入一个键值对时，HashMap 首先根据键的哈希值计算出其应该存储在数组的哪个位置，然后将其插入到该位置对应链表的末尾。当我们查找一个键值对时，HashMap 首先根据键的哈希值找到其应该存储的链表，然后在该链表中查找对应的键值对。

HashMap 提供了 O(1) 的时间复杂度用于插入和查找操作。在最坏情况下，HashMap 的时间复杂度为 O(n)，其中 n 是键值对的数量。这是由于哈希碰撞（即两个不同的键的哈希值相同）可能导致链表长度变得非常长。(合理的散列函数可减少哈希碰撞)

注：图片引用自：java - HashMap的实现原理(看这篇就够了） - BAT架构技术与大厂面试 - SegmentFault 思否

2. 为什么要使用HashMap

对比Array、 LinkedList 、HashMap

数据结构	存储方式	长度	随机访问	插入删除	顺序	重复
Array	连续空间	固定不变	O(1)	O(n)需要移动数据	有序	可以重复
LinkedList	线性表（链表）	可变动态增减	O(n)需要遍历查找	O(1)不需要移动数据	有序	可以重复
HashMap	散列表（数组+链表+红黑树）	可变动态增减扩容缩容	O(1)根据哈希值查找	O(1)不需要移动数据但可能产生哈希冲突和重新分配桶位	无序, 可以使用LinkedHashMap或TreeMap实现有序性	不可以重复键值

当你不关心元素的顺序时，hashmap可以无需排序或比较就实现数据的存储和检索。

在需要存储大量的数据时，hashmap可以节省内存空间，并且避免数组或list扩容或缩容带来的性能损耗。

3. HashMap的使用

常用方法：

• put(K key, V value)：将指定的值与该映射中的指定键关联。

• get(Object key)：返回到指定键所映射的值，或者如果此映射不包含该键的映射，则返回 null。

• remove(Object key)：如果存在一个键的映射关系，则将其从此映射中移除。

• containsKey(Object key)：如果此映射包含指定键的映射关系，则返回 true。

• containsValue(Object value)：如果此映射将一个或多个键映射到指定值，则返回 true。

• size()：返回此映射中的键-值映射关系数。

• clear()：从此映射中移除所有映射关系。

• 遍历方式

  • for-each 循环

    for (Map.Entry<K, V> entry : map.entrySet()) {K key = entry.getKey();V value = entry.getValue();
    }
    

  • 迭代器

    Iterator<Map.Entry<K, V>> iterator = map.entrySet().iterator();
    while (iterator.hasNext()) {Map.Entry<K, V> entry = iterator.next();K key = entry.getKey();V value = entry.getValue();
    }
    

  • 使用 Lambda 表达式遍历（JDK 1.8+）

  • 使用 Streams API 遍历（JDK 1.8+）

  • 使用 Enumeration 的方式进行遍历，这种方法是旧版的方法，不推荐使用，因为它比迭代器更慢，而且不支持泛型

    ……

基本使用

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);

4. 源码解析

java.util.Map接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示:

实现流程

HashMap 的内部实现主要由一个数组和若干个链表/红黑树组成。数组中的每个元素都是一个链表/红黑树的头节点，链表/红黑树中存储着相应的键值对。HashMap 将键值对存储在数组中的位置是由键的哈希值决定的。

具体来说，HashMap 会使用键的哈希值对数组的长度进行取模，以确定该键值对应该存储在数组的哪个位置。当插入一个键值对时，

1. 计算该键的哈希值

2. 根据该哈希值找到相应的数组位置

3. 将该键值对插入到对应链表/红黑树的末尾。

   当查找一个键值对时，HashMap 会首先计算该键的哈希值，然后根据该哈希值找到相应的数组位置，并在对应链表/红黑树中查找相应的键值对(遍历)。

4.1 关键问题

建立哈希表之前，需要解决两个主要问题：

1. 设计哈希函数, 要求均匀的分布在哈希表中

2. 冲突的处理
   ​ 冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。在Java中，HashMap采用了链地址法解决哈希冲突，也就是数组+链表的形式

4.1 存储结构

HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的

注：图片引用自Java 8系列之重新认识HashMap - 美团技术团队 (meituan.com)

Node<K,V>用于封装Map集合中的一组键值对对象。它有四个属性：hash、key、value和next，分别表示哈希值、键、值和下一个节点的引用。上图中的每个黑色圆点就是一个Node对象

//定义一个静态内部类Node，实现Map.Entry接口
static class Node<K,V> implements Map.Entry<K,V> {//存储键的哈希码，final类型不可修改final int hash;//存储键对象，final类型不可修改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;}//实现Map.Entry接口中定义的getKey方法，返回当前节点存储的键对象public final K getKey()        { return key; }//实现Map.Entry接口中定义的getValue方法，返回当前节点存储的值对象public final V getValue()      { return value; }//重写toString方法public final String toString() { return key + "=" + value; }//重写hashCode方法，返回键和值的异或运算结果作为哈希码//这样可以保证相同的键值对映射有相同的哈希码，不同的键值对映射有不同的哈希码（大概率）//这也符合Map.Entry接口中规定的hashCode契约：如果两个Entry对象相等，则它们必须有相同的哈希码；如果两个Entry对象有相同的哈希码，则它们不一定相等。public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}//实现Map.Entry接口中定义的setValue方法，用新值替换当前节点存储的值对象，并返回旧值对象public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}//重写equals方法，判断当前节点是否与另一个对象相等public final boolean equals(Object o) {if (o == this) //如果是同一个对象，直接返回truereturn true;if (o instanceof Map.Entry) { //如果是Map.Entry类型的对象，进行进一步判断Map.Entry<?,?> e = (Map.Entry<?,?>)o; //将其强制转换为Map.Entry类型if (Objects.equals(key, e.getKey()) && //如果键对象相等（使用Objects.equals方法可以避免空指针异常）Objects.equals(value, e.getValue())) //并且值对象相等（同理）return true; //则返回true}return false; //否则返回false}}

4.2 HashMap 的容量和负载因子

容量: 内部数组的大小

负载因子: 哈希表可以达到的最大填充因子

填充因子是指哈希表中键值对的数量与数组大小的比值。当哈希表中的键值对数量达到容量与负载因子的乘积时，就会自动进行扩容操作，将数组大小增加为原来的两倍。例如，如果我们将负载因子设置为 0.75，那么当 HashMap 中的键值对数量达到其数组大小的 75% 时，就会触发自动扩容操作。

常量定义解析

//默认的初始容量，必须是2的幂，也就是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//最大容量，如果构造函数中指定了一个更高的值，则使用这个值。必须是2的幂且不超过1<<30
static final int MAXIMUM_CAPACITY = 1 << 30;//默认的负载因子，如果构造函数中没有指定，则使用这个值(经过计算得出的0.75)。
//负载因子是一个浮点数，表示哈希表允许填充的程度。一般来说，负载因子越小，冲突越少，性能越好，但空间利用率越低。
static final float DEFAULT_LOAD_FACTOR = 0.75f;//将链表转化为红黑树的阈值
//当一个桶（bin）中的节点数达到或超过这个值时，就会将链表转化为红黑树，以提高查找效率
//这个值必须大于2，并且至少为8，以便与删除操作中关于转化回链表的假设相匹配
static final int TREEIFY_THRESHOLD = 8;//在调整大小（resize）操作中将红黑树转化回链表的阈值。应该小于TREEIFY_THRESHOLD，并且最多为6，以便与删除操作中关于缩小检测相匹配。
static final int UNTREEIFY_THRESHOLD = 6;//可以进行树化（treeify）的最小表容量。如果桶中节点数太多而表容量太小，则会调整表大小而不是进行树化。应该至少为4 * TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;

4.3 初始化过程

先熟悉几个变量

 /**Node数组，用来存储键值对,Node是一个内部类，表示一个链表节点或者一个红黑树节点。table在第一次使用时初始化，并且在需要时进行扩容。table的长度总是2的幂次方，这样可以提高哈希值和数组索引之间的映射效率*/transient Node<K,V>[] table;/**Set集合，用来缓存hashmap中所有的键值对。entrySet在第一次调用时创建，并且在hashmap结构发生变化时更新。entrySet可以用来遍历hashmap中的所有元素。*/transient Set<Map.Entry<K,V>> entrySet;/*** 包含的键值对的数量*/transient int size;/**hashmap结构修改的次数。结构修改指的是改变了键值对数量或者内部结构（例如rehash）的操作。modCount用来实现快速失败机制，即当迭代器遍历hashmap时，如果发现modCount发生了变化，就抛出ConcurrentModificationException异常。*/transient int modCount;/**扩容的阈值，等于容量乘以负载因子。当size超过threshold时，就会触发resize()方法进行扩容。如果table还没有分配空间，那么threshold就表示初始容量，默认为16。*/int threshold;/**负载因子。负载因子越小，哈希冲突越少，但空间利用率越低；负载因子越大，哈希冲突越多，但空间利用率越高。loadFactor默认为0.75，在创建hashmap时可以指定。*/final float loadFactor;

补充一下rehash和快速失败机制

rehash是指当hashmap进行扩容时，重新计算所有元素的哈希值，并将它们分配到新的数组中。rehash的目的是为了保持元素在数组中的均匀分布，避免哈希冲突过多。rehash是一个耗时的操作，因为它需要遍历所有元素，并且可能会改变元素在链表或者红黑树中的顺序。

快速失败机制是指当迭代器遍历hashmap时，如果发现hashmap结构发生了变化（例如添加或删除元素），就抛出ConcurrentModificationException异常，而不是继续遍历。快速失败机制的目的是为了保证数据的一致性和安全性，避免出现不可预知的结果。快速失败机制并不是完全可靠的，因为它只能检测到结构修改，而不能检测到内容修改（例如修改元素的值）。

示例1：

//创建一个初始容量为4，负载因子为0.75的hashmap
HashMap<String, Integer> map = new HashMap<>(4, 0.75f);
//添加三个元素，此时size为3，threshold为3，不需要扩容
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
//创建一个迭代器遍历entrySet
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {Map.Entry<String, Integer> entry = iterator.next();System.out.println(entry.getKey() + ":" + entry.getValue());//情况一：//在遍历过程中，添加第四个元素，此时size为4，threshold为3，触发扩容和rehash//同时modCount增加1，与迭代器期望的modCount不一致，抛出ConcurrentModificationException异常map.put("d", 4);//情况二://在遍历过程中，修改第一个元素的值，此时size不变，modCount不变，不触发快速失败机制//但是这样做可能会破坏数据的一致性和安全性，因为迭代器已经访问过的元素被修改了if (entry.getKey().equals("a")) {map.put("a", 10);}
}

HashMap构造器

//创建一个空的HashMap，指定初始容量和负载因子。
public HashMap(int initialCapacity, float loadFactor) {//合法性检查if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);//初始容量大于最大容量（2^30），就将其设置为最大容量。                                  if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;//调用tableSizeFor方法，根据初始容量计算出一个大于等于它且最接近它的2的幂次方数，//并赋值给当前对象的threshold属性。threshold表示哈希表达到多少个元素时需要扩容。this.threshold = tableSizeFor(initialCapacity);}

//创建一个空的HashMap，指定初始容量和默认负载因子。
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//创建一个空的HashMap，初始容量为16，负载因子为0.75
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//创建一个新的HashMap，包含指定Map中的所有映射，并使用默认容量和负载因子。
public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}

4.3 put() 方法实现原理

HashMap 的 put() 方法用于插入键值对，那当插入新的键值对时，我们需要先找到应该存放的位置，那么如何去找呢？

我们知道HashMap是根据key值定位的，所以先获取key的hashCode，然后然后对数组的容量进行取模，即可得到它存放的位置。

这个方法用于向HashMap中插入一个键值对，如果键已经存在，则替换旧值，如果键不存在，则创建一个新节点。

public V put(K key, V value) {// 调用putVal方法return putVal(hash(key), key, value, false, true);
}// 定义putVal方法，接受五个参数：哈希值、键、值、是否只在键不存在时插入、是否删除最旧的节点
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// 定义一个Node数组tab，用于存储HashMap中的节点Node<K,V>[] tab; // 定义一个Node对象p，用于遍历链表或树Node<K,V> p; // 定义两个整数n和i，分别表示数组长度和索引位置int n, i;// 如果数组tab为空或长度为0，则调用resize()方法重新分配空间，并赋值给nif ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 如果数组tab在索引位置i处没有节点，则创建一个新节点并赋值给该位置//(n - 1) & hash是取模运算if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 否则，说明该位置已经有节点存在，则执行以下操作：else {// 定义一个Node对象e，用于存储找到的匹配节点或插入的新节点Node<K,V> e; // 定义一个K对象k，用于存储当前遍历到的节点的键K k;// 如果当前遍历到的节点p的哈希值等于传入的哈希值，并且它们的键相等（通过==或equals判断），则将p赋值给e（表示找到了匹配节点）if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 否则，如果当前遍历到的节点p是一个树形结构（TreeNode），则调用putTreeVal方法，在树中查找或插入新节点，并将返回结果赋值给e（表示找到了匹配节点或插入了新节点）else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key,value);// 否则，说明当前遍历到的节点p是一个链表结构，则执行以下操作：else {// 定义一个整数binCount，用于记录链表长度for (int binCount = 0; ; ++binCount) {// 如果当前遍历到的节点p没有下一个节点，则创建一个新节点并赋值给它，并跳出循环（表示插入了新节点）if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);   // 如果链表长度超过阈值，则转换为树形结构break;}// 如果当前遍历到的下一个节点e的哈希值等于传入的哈希值，//并且它们的键相等（通过==或equals判断），则跳出循环（表示找到了匹配节点）if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;// 否则，将p指向下一个节点e，继续遍历链表p = e;}}// 如果找到了匹配节点e，则执行以下操作：if (e != null) { // 获取旧值oldValueV oldValue = e.value;// 如果onlyIfAbsent为false或者旧值为null，则将新值赋值给e.valueif (!onlyIfAbsent || oldValue == null)e.value = value;// 调用afterNodeAccess方法，用于LinkedHashMap的后续操作afterNodeAccess(e);// 返回旧值return oldValue;}// 如果没有找到匹配节点，则执行以下操作：// 增加修改次数modCount++modCount;// 增加HashMap大小sizeif (++size > threshold)// 如果大小超过阈值，则调用resize()方法重新分配空间resize();// 调用afterNodeInsertion方法，用于LinkedHashMap的后续操作afterNodeInsertion(evict);// 返回nullreturn null;
}

4.3.1 hash()

即 计算键的哈希值， hash()方法的设计是为了提高HashMap的性能和减少哈希冲突, 即解决4.1中的第一个问题。它的作用是对键对象的hashCode()方法返回值进行再散列，使得哈希值分布更均匀，从而减少链表的长度和查找时间。而且，由于右移16位后异或，可以使得哈希值在低16位上更加随机，从而减少哈希冲突。

hash算法的输入是key，输出是数组的下标（HashMap是数组+链表实现）

static final int hash(Object key) {int h;//第一步 取hashCode值，第二步 高位运算return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

注：使用哈希值对数组长度进行取模，以确定该键值对应该存储在数组的哪个位置, 即hash & (table.length - 1), 不使用%而使用&的好处是，当数组长度是2的幂次方时（例如16），计算索引值时只需要用哈希值和数组长度减一进行按位与运算（&），就可以得到结果。这样可以避免使用取模运算（%），提高效率。

这里引用一篇博文Java 8系列之重新认识HashMap - 美团技术团队 (meituan.com)中的图片举例说明，n为table长度：

4.3.2 resize()

resize()方法是在HashMap的容量达到阈值时，自动调用的方法，用于重新分配空间，提高性能。在put方法中，判断数组是否为空或者太小，如果是，则调用resize(int newCapacity)方法重新分配空间， 每次扩充为原来的2倍。扩容后，将旧数组中的元素复制到新数组中。

在jdk1.8及以后，hashmap的resize()方法是用来调整hashmap的容量和阈值的。当hashmap中的元素数量超过当前容量乘以负载因子时，就会触发resize()方法。resize()方法会创建一个新的数组，然后将原来数组中的元素重新计算哈希值并分配到新数组中。这个过程称为rehashing。

resize()方法还做了一些优化，比如使用了扰动函数来减少哈希冲突，使用了链表转红黑树来提高查找效率，使用了尾插法来保持链表顺序不变等。

resize()方法的源码如下：

final Node<K,V>[] resize() {// 获取旧数组Node<K,V>[] oldTab = table;// 获取旧数组长度int oldCap = (oldTab == null) ? 0 : oldTab.length;// 获取旧阈值int oldThr = threshold;// 定义新数组长度和新阈值int newCap, newThr = 0;// 如果旧数组长度大于0，则执行以下操作：if (oldCap > 0) {// 如果旧数组长度达到最大容量，则将新阈值设为整数最大值，并返回旧数组（不进行扩容）if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 否则，将新数组长度设为旧数组长度的两倍，并检查是否小于最大容量且大于默认初始容量（16）else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 如果是，则将新阈值设为旧阈值的两倍newThr = oldThr << 1; // double threshold}// 否则，如果旧数组长度等于0，旧阈值大于0，则执行以下操作：else if (oldThr > 0) // 将新数组长度设为旧阈值（第一次扩容时）newCap = oldThr;// 否则，旧数组长度、旧阈值等于0，说明是一个空表，则执行以下操作：else {               // 将新数组长度设为默认初始容量（16）newCap = DEFAULT_INITIAL_CAPACITY;// 将新阈值设为默认加载因子（0.75）乘以默认初始容量（16）得到的结果（12）newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 如果新阈值等于0，则执行以下操作：if (newThr == 0) {// 计算一个临时变量ft，等于新数组长度乘以加载因子得到的结果float ft = (float)newCap * loadFactor;// 将新阈值设为ft和最大容量中较小的一个，并且如果ft等于整数类型的最大容量，则将其减一（避免溢出）newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 创建一个新数组newTab，长度为新数组长度newCapNode<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 将新数组赋值给table属性table = newTab;// 将新阈值赋值给threshold属性threshold = newThr;// 如果旧数组不为空，则执行以下操作：if (oldTab != null) {// 遍历旧数组的每个元素efor (int j = 0; j < oldCap; ++j) {Node<K,V> e;// 如果当前元素e不为空，则执行以下操作：if ((e = oldTab[j]) != null) {// 将旧数组的当前位置设为null（释放空间）oldTab[j] = null;// 如果当前元素e没有下一个节点，则执行以下操作：if (e.next == null)// 将当前元素e放入新数组的对应位置（根据哈希值和新数组长度计算索引）newTab[e.hash & (newCap - 1)] = e;// 否则，如果当前元素e是一个树形结构，则执行以下操作：else if (e instanceof TreeNode)// 调用split方法将树形结构分割成两个链表或者两个子树，并放入新数组的对应位置((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 否则，说明当前元素e是一个链表结构，则执行以下操作：else { // 定义两个链表loHead和hiHead，分别用于存储低位和高位的节点Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;// 遍历链表的每个节点do {next = e.next;// 如果节点的哈希值与旧数组长度进行与运算得到0，则说明该节点在新数组中的索引不变（低位）if ((e.hash & oldCap) == 0) {// 如果低位链表为空，则将该节点设为低位链表的头部if (loTail == null)loHead = e;elseloTail.next = e;   // 否则，将该节点追加到低位链表的尾部loTail = e;           // 更新低位链表的尾部指针}else {                  // 否则，说明该节点在新数组中的索引需要加上旧数组长度（高位）if (hiTail == null)  // 如果高位链表为空，则将该节点设为高位链表的头部hiHead = e;else                 // 否则，将该节点追加到高位链表的尾部hiTail.next = e;  hiTail = e;          /}// 将当前节点e指向下一个节点nexte = next;} while (e != null);// 如果低位链表不为空，则将其放入新数组的对应位置（与旧数组相同）if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 如果高位链表不为空，则将其放入新数组的对应位置（加上旧数组长度）if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}// 返回新数组return newTab;
}

注：Java 8系列之重新认识HashMap - 美团技术团队 (meituan.com)这篇文章中有举例介绍扩容的过程，讲了为什么是扩容两倍，我就不具体展开介绍了。

注：图片引自Java 8系列之重新认识HashMap - 美团技术团队 (meituan.com)

4.4 get() 方法实现原理

HashMap 的 get() 方法用于查找键对应的值, get方法的基本步骤如下：

1. 根据键的哈希值(hash)来定位数组中的位置(index)，如果数组为空或者位置上没有元素，就返回null。
2. 如果位置上有元素，就比较元素的键和给定的键是否相等，如果相等，就返回元素的值。
3. 如果位置上有多个元素（发生了哈希冲突），就遍历链表或者红黑树，找到与给定键相等的元素，并返回其值。
4. 如果没有找到与给定键相等的元素，就返回null。

get方法的时间复杂度取决于数组中元素的分布情况。如果没有哈希冲突，那么get方法只需要一次数组访问，时间复杂度是O(1)。如果有哈希冲突，那么get方法需要遍历链表或者红黑树，时间复杂度是O(n)或者O(log n)。

public V get(Object key) { Node<K,V> e; //用来存储找到的节点// 调用getNode方法，传入键的哈希值和键本身，如果找到了匹配的节点，就返回它的值，否则返回nullreturn (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//如果table数组不为空，并且长度大于0//并且根据哈希值计算出的索引位置上有一个节点（称为first）if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 如果first节点的哈希值和传入的哈希值相同if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))return first;//那么就返回first节点//如果first节点有后继节点（称为e）if ((e = first.next) != null) {//如果first节点是一个树形结构（TreeNode）而不是链表结构（Node）if (first instanceof TreeNode)//那么就调用getTreeNode方法，在树形结构中查找匹配的节点并返回return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {//如果e节点的哈希值和传入的哈希值相同//并且e节点的键和传入的键相同（或者两者都不为空，并且equals方法返回true）if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;//那么就返回e节点} while ((e = e.next) != null);//否则继续遍历链表上的其他节点直到为空为止}}//如果没有找到匹配的节点，就返回nullreturn null;}

5. 面试题总结

上面讲了一大堆理论，先来实践一下吧。

挑选了几个比较常见的面试题目，如下：

1. HashMap为什么要用数组+链表/红黑树的结构？

   这个比较简单，数组+链表/红黑树(注意区别JDK1.7和1.8)

2. HashMap为什么要用数组+链表/红黑树的结构？

   为了提高HashMap的查询效率和空间利用率

   数组是一种连续的存储结构，它可以通过索引快速定位元素，但是它的长度是固定的，如果数组过大，会浪费空间；如果数组过小，会导致哈希冲突。

   链表是一种离散的存储结构，它可以动态地增加或删除元素，但是它需要遍历才能找到元素，如果链表过长，会降低查询效率。

   红黑树是一种平衡二叉搜索树，它可以保证在最坏情况下查询时间复杂度为O(logn)，但是它需要维护平衡性和颜色性质，增加了插入和删除的开销。

   因此，HashMap采用了数组+链表/红黑树的结构，即将哈希表分为多个桶（bucket），每个桶对应一个链表或红黑树。当插入一个键值对时，先计算键的哈希值，并根据哈希值确定桶的位置；然后在该桶中查找是否有相同的键存在；如果有，则覆盖旧值；如果没有，则将新节点插入到链表或红黑树中。当查询一个键时，也是先计算键的哈希值，并根据哈希值确定桶的位置；然后在该桶中遍历链表或红黑树查找是否有匹配的键存在；如果有，则返回对应的值；如果没有，则返回null。（结合了数组、链表、红黑树的优点）

   这样做的好处是：

   • 可以利用数组快速定位桶的位置；
   • 可以利用链表或红黑树动态地存储元素；
   • 可以利用负载因子控制哈希表的填充程度；
   • 可以利用扩容机制动态地调整哈希表的大小；
   • 可以利用红黑树提高长链表查询效率。

3. HashMap如何解决哈希冲突？

   HashMap是一种基于数组和链表的数据结构，它使用哈希算法来计算每个元素的存储位置。当两个或多个元素的哈希值相同时，就会发生哈希冲突。

   HashMap有四种方法来解决哈希冲突：

   • 开放地址法：当发生冲突时，寻找下一个空闲的位置存储元素。
   • 链地址法：当发生冲突时，将具有相同哈希值的元素组织成一个链表存储在同一个位置。
   • 再哈希法：当发生冲突时，使用另一个哈希函数计算新的位置存储元素。
   • 建立公共溢出区：当发生冲突时，将所有冲突的元素存储在一个单独的区域。

   其中最常用的方法是链地址法，因为它比较简单且效率较高。JDK 1.8后，还引入了红黑树来优化链表过长的情况。

4. HashMap如何扩容？扩容时会发生什么？

   HashMap扩容是指当HashMap内部的数组无法容纳更多的元素时，需要创建一个新的数组并将原来的元素复制过去。

   HashMap扩容时会发生以下步骤:

   • 计算新的数组长度，一般是原来的两倍。
   • 创建一个新的数组，并将原来的数组引用赋给一个临时变量。
   • 遍历原来的数组，对每个元素进行重新哈希和定位，然后放入新的数组中。
   • 将新的数组引用赋给HashMap内部的table变量。

   HashMap扩容时会影响性能，因为需要重新计算哈希值和复制元素。所以建议在创建HashMap时指定合适的初始容量和负载因子。

   扩展延伸

   为什么默认长度和扩容后的长度都必须是 2 的幂

   HashMap的长度必须是2的幂，主要有以下两个原因:

   • 为了提高哈希值和数组下标的计算效率。这个之前有提到过，hash & (n - 1), 如果长度是2的幂，那么只需要用哈希值和长度减一做按位与运算，就可以得到数组下标。这比用取模运算要快很多。
   • 为了让元素在数组中分布更均匀。如果长度是奇数，那么哈希值和长度减一做按位与运算后，只能得到偶数下标。这样就浪费了一半的空间，并且增加了哈希冲突的可能性。而如果长度是2的幂，那么哈希值和长度减一做按位与运算后，可以得到任意奇偶数下标。这样就充分利用了数组的空间，并且降低了哈希冲突的可能性。

5. HashMap的默认初始容量和负载因子是多少？它们有什么影响？

   HashMap的默认初始容量是16，默认负载因子是0.75。

   初始容量是指HashMap内部数组的长度，它决定了HashMap可以存储的元素个数。如果设置过大，会浪费内存空间；如果设置过小，会导致频繁扩容，影响性能。

   负载因子是指HashMap中的元素个数与数组长度的比值，它反映了HashMap的填充程度。当负载因子达到某个阈值时，HashMap会自动扩容。如果负载因子过高，会增加哈希冲突和链表长度，降低查询效率；如果负载因子过低，会增加数组空间和扩容次数，降低插入效率。

   默认负载因子0.75是一个折中的选择，既考虑了时间效率又考虑了空间效率。

6. HashMap和Hashtable有什么区别？

   • 线程安全性。Hashtable是线程安全的，因为它的方法都用synchronized修饰了，多个线程可以共享一个Hashtable；而HashMap是非线程安全的，如果没有正确的同步，多个线程不能共享一个HashMap。

   • 键值是否允许为空。HashMap可以接受null作为键或值，而Hashtable不允许null作为键或值。

   • 效率。由于Hashtable需要进行同步操作，所以它的效率比HashMap低；而HashMap不需要进行同步操作，所以它的效率比Hashtable高。

     ……

7. HashMap在多线程环境下会出现什么问题？如何避免？

数据丢失。当多个线程同时对HashMap进行put操作时，可能会导致某些键值对被覆盖或丢失。

死循环。hashmap中死循环是指在多线程环境下，使用hashmap进行put操作时，可能会导致链表形成环状结构，从而使得get操作无法找到正确的元素，陷入无限循环。这是因为hashmap在扩容时，会使用头插法重新散列链表(JDK1.7及以前)，如果有多个线程同时进行扩容，可能会出现链表倒序或相互指向的情况。

举例说明：

假设有两个线程A和B，同时对一个hashmap进行put操作，触发了扩容，假设原来的链表是1->2->3，扩容后的数组长度是8，那么可能会出现以下情况：

• 线程A先将1插入到新数组的第一个位置，此时新数组的第一个位置是1，旧数组的第一个位置是2->3。
• 线程B也将1插入到新数组的第一个位置，此时新数组的第一个位置是1->1，旧数组的第一个位置是2->3。
• 线程A再将2插入到新数组的第一个位置，此时新数组的第一个位置是2->1->1，旧数组的第一个位置是3。
• 线程B也将2插入到新数组的第一个位置，此时新数组的第一个位置是2->2->1->1，旧数组的第一个位置是3。
• 线程A再将3插入到新数组的第一个位置，此时新数组的第一个位置是3->2->2->1->1，旧数组的第一个位置是null。
• 线程B也将3插入到新数组的第一个位置，此时新数组的第一个位置是3->3->2->2->1->1，旧数组的第一个位置是null。

这样就形成了一个环状链表，如果此时有其他线程对这个hashmap进行get操作，就会陷入死循环。

一文看懂 jdk8 中的 ConcurrentHashMap - 掘金 (juejin.cn)这篇博文有图更清晰一点

在JDK1.8中，对于死循环有所改进(知识减少发生概率)：

• 当链表长度超过一定阈值时，会转换为红黑树，提高查找效率。
• 在扩容时，不再使用头插法，而是使用尾插法，避免了链表倒序的问题。

这样就减少了死循环的可能性。但是，并不是说JDK1.8完全解决了死循环的问题。还有一些特殊情况下，可能会出现死循环：

• 当链表转换为红黑树时，如果多个线程同时操作同一个节点，可能会导致树结构破坏。
• 当多个线程同时对同一个桶进行put操作时，如果没有正确处理并发问题，可能会导致链表断裂或形成环。

要避免这些问题，有以下几种方法:

• 使用Hashtable。Hashtable是线程安全的，它的方法都用synchronized修饰了，但是它的效率比较低。
• 使用ConcurrentHashMap。ConcurrentHashMap是线程安全的，它采用了分段锁的机制，提高了并发性能。
• 使用Collections.synchronizedMap()方法。这个方法可以将一个非线程安全的Map包装成一个线程安全的Map。

• 8. HashMap中key和value可以为null吗？为什么？

  HashMap中key和value都可以为null，而Hashtable中key和value都不可以为null。

  这是因为HashMap是后来引入的类，它的接口Map表达的意义更为广泛，也许HashMap的设计者认为null作为key和value是有实际意义的，所以才允许为null。

  而Hashtable是早期的类，它的接口Dictionary表达的意义更为狭隘，它认为null作为key和value是没有意义的，所以不允许为null。

  另外，HashMap中如果key为null，那么它的哈希值就直接为0，不用调用key.hashCode()方法，这样可以避免空指针异常。而Hashtable中如果key为null，那么调用key.hashCode()方法就会抛出空指针异常。

面试题还可参考：

HashMap精选面试题（2021版） - 知乎 (zhihu.com)

HashMap面试题及答案（2022版） - Java团长 - 博客园 (cnblogs.com)

---

上面有提到一些hashmap的线程不安全问题，下面就介绍一种线程安全的解决方案

6. ConcurrentHashmap(JDK8)

6.1 基本概念

ConcurrentHashMap 是 Java 并发包中提供的一个线程安全的哈希表实现，它允许多个线程同时读取和写入，而不需要使用显式的锁或同步机制。与 Hashtable 和 synchronizedMap 等传统的同步哈希表实现不同，ConcurrentHashMap 摒弃了 jdk7 中的分段锁设计，使用了 Node + CAS + Synchronized 来保证线程安全, 其数据结构同的 HashMap 数据结构一样，都是 数组+链表+红黑树。

ConcurrentHashMap的并发安全是通过对Node数组的某个索引位置的元素加锁来实现的，这样只有当两个线程同时操作同一个Node对象时，才会争抢同一把锁，否则可以并行操作。同时，ConcurrentHashMap还利用了CAS（无锁算法）来实现一些原子性的操作，比如插入一个新的Node对象，或者扩容Node数组。CAS是一种基于硬件的原子指令，它可以比较并交换一个内存地址的值，如果值没有被其他线程修改，就可以成功更新，否则就重试，直到成功为止。这样就避免了使用锁，提高了性能。

注：这里使用了volatile关键字，它是Java提供的一种轻量级的同步机制，等总结到了并发再讲，有兴趣的小伙伴可以自行百度

上面有点绕，我举个例子：

假设我们有一个ConcurrentHashMap对象，它的Node数组的长度为16，现在我们要插入一个键值对(“a”, 1)，这个操作大家应该熟悉了吧！

1. 计算它的hashcode，假设是5
2. 用hashcode和数组长度-1做一个位运算，得到它在数组中的索引，假设是5
3. 检查数组的第5个位置是否为空
   • 如果为空，就用CAS操作尝试插入一个新的Node对象，如果成功，就结束了，如果失败，说明有其他线程也在操作这个位置，就重试，直到成功为止。
   • 如果数组的第5个位置不为空，就说明有冲突，就要判断这个位置的元素是链表还是红黑树
     • 如果是链表，就遍历链表，看是否有相同的key，如果有，就替换value，如果没有，就在链表的末尾插入一个新的Node对象，这个过程要加锁，以保证并发安全。
     • 如果是红黑树，就按照红黑树的规则插入一个新的Node对象，这个过程也要加锁，以保证并发安全。插入的过程中，还要检查是否需要扩容，如果数组的容量达到了一个阈值，就会用CAS操作尝试扩容，扩容的过程是创建一个新的数组，然后把旧数组的元素复制到新数组中，这个过程可以并行进行，不同的线程可以负责不同的区域，以提高效率。代码如下：

//创建一个ConcurrentHashMap对象，指定初始容量为16
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(16);//插入一个键值对("a", 1)
map.put("a", 1);//计算hashcode，假设是5
int hash = hash("a");//计算索引，数组长度-1 = 15， 假设是5
int index = (hash & 15);//情况一：
//获取数组的第5个位置的元素，假设为空
Node<String, Integer> node = map.table[index];//用CAS操作尝试插入一个新的Node对象
if (node == null) {if (map.casTabAt(index, null, new Node<>(hash, "a", 1, null))) {break; //成功插入，结束循环}//失败，重试continue;
}//情况二（情况三同）：
//获取数组的第5个位置的元素，假设不为空，是一个链表
Node<String, Integer> node = map.table[index];//加锁，锁住当前节点
synchronized (node) {//遍历链表，看是否有相同的key，如果有，替换value，如果没有，插入新的Node对象Node<String, Integer> p = node;while (p != null) {if (p.hash == hash && p.key.equals("a")) {p.value = 1; //替换valuebreak;}p = p.next;}if (p == null) {//插入新的Node对象node.next = new Node<>(hash, "a", 1, node.next);}
}

6.2 put方法

put 方法是向map中存入元素，本质上调用了 putVal，核心的方法之一

1. put方法的主要逻辑是先尝试在数组中找到对应的节点，如果没有则创建一个新的节点并插入到数组中，如果有则尝试用CAS更新节点的值，如果失败则加锁并重试。

2. 检查数组的长度是否超过阈值，如果超过则触发扩容操作，扩容操作会创建一个新的数组，然后将旧数组中的节点复制到新数组中，同时保证并发的安全性和可见性。

3. 检查节点是否是树形结构，如果是则调用相应的树形操作，如果不是则调用链表操作，树形结构的目的是为了优化在高并发和高冲突的情况下的性能。(在对应数组有节点的情况)

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(); //不允许key或value为空int hash = spread(key.hashCode()); //计算key的hash值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) & hash)) == null) { //如果数组对应位置为空，则尝试用CAS插入新节点//使用CAS（比较并交换）机制来更新数组中的某个位置的节点。参数有四个，分别是数组tab，索引i，期望值c，新值v//如果tab[i] == c，则更新tab[i] = v，并返回true，否则返回false。//成功插入，结束循环if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break;                   // no lock when adding to empty bin}/**MOVED是一个常量，它的值是-1，表示当前节点是一个ForwardingNode，也就是一个转发节点，*它的作用是在数组扩容的时候，指向新的数组，让其他线程可以访问新的数组。*/else if ((fh = f.hash) == MOVED) //检查当前节点是否是一个特殊的节点，表示数组正在扩容或者转化为红黑树//根据转发节点的指向，将旧数组中的节点复制到新数组中，或者将链表转化为红黑树//同时也会让当前线程参与扩容或者转化的过程!!!(注意是参与协助扩容，也就是多线程扩容)tab = helpTransfer(tab, f);else { //如果数组对应位置不为空，则加锁并重试V oldVal = null;synchronized (f) { //加锁,保证代码块在同一时刻只能被一个线程执行，避免并发问题if (tabAt(tab, i) == f) { //再次检查，如果当前槽位的头结点没有变化，说明没有其他线程修改过这个槽位if (fh >= 0) { //如果是链表，哈希值大于等于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)))) { //如果找到相同的key，则更新valueoldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}// 记录当前结点的前驱结点Node<K,V> pred = e;if ((e = e.next) == null) { //如果没有找到相同的key，则在链表尾部插入新节点pred.next = new Node<K,V>(hash, key,value, null);break;}}}else if (f instanceof TreeBin) { //如果是树Node<K,V> p;// 初始化一个计数器，用来记录树的高度binCount = 2;// 调用TreeBin类的putTreeVal方法，将键值对插入到红黑树中，如果已经存在这个键，那么就返回这个结点if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) { oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}if (binCount != 0) { //如果链表或树的长度不为0if (binCount >= TREEIFY_THRESHOLD) //如果超过阈值，则转化为树treeifyBin(tab, i);if (oldVal != null) //如果更新了旧值，则返回旧值return oldVal;break;}}}//给 map 已存储的数量 +1，在 addCount 方法中判断是否需要扩容addCount(1L, binCount); return null; //返回空
}

关于MOVED再做点补充：

MOVED变量是一个int类型的常量，它的值是-1，它是用来表示当前节点的哈希值，而不是表示当前节点本身。

ForwardingNode是一个内部类，它继承了Node类，它的作用是在数组扩容的时候，作为一个转发节点，指向新的数组，让其他线程可以访问新的数组。ForwardingNode的构造方法如下：

ForwardingNode(Node<K,V>[] tab) {super(MOVED, null, null);this.nextTable = tab;
}

可以看到，它的哈希值是MOVED，它的key和value都是null，它的nextTable是新的数组。

简单补充一下CAS算法

CAS算法是一种乐观锁的实现方式，它的全称是“比较并交换”（Compare-And-Swap）或者“比较并设置”（Compare-And-Set）。它的基本思想是:

当多个线程同时尝试更新一个共享变量时，只有一个线程能够成功，而其他线程会失败并重试，直到成功为止。这样就避免了使用传统的悲观锁，即在更新共享变量之前，必须先获取锁，然后释放锁，这会导致性能下降和死锁的风险。

CAS算法的核心是一个原子操作，即CAS(V, A, B)，它的含义是，如果共享变量V的值等于期望值A，那么就将V的值更新为新值B，否则不做任何操作。这个操作是原子的，也就是说，它不会被其他线程的操作打断。CAS操作的返回值是一个布尔值，表示是否更新成功。

Java中提供了一些原子类，如AtomicInteger, AtomicLong等，它们内部使用了CAS算法来实现一些基本的原子操作，比如自增，自减，加法，减法等。这些类可以帮助我们简化一些多线程编程的场景，比如计数器，累加器等。

6.3 应用场景

ConcurrentHashMap是一个高并发且线程安全的Map容器，它可以用来替换其他线程安全的Map容器，比如Hashtable和Collections.synchronizedMap。ConcurrentHashMap的使用场景是需要在多线程环境下对Map进行频繁的读写操作，而又不希望锁住整个Map的情况。

假设我们有一个需求，需要统计每个用户的访问次数，我们可以使用一个ConcurrentHashMap<String, Integer>来存储用户ID和访问次数的映射，然后在每次用户访问时，更新对应的访问次数。

代码如下：

// 创建一个ConcurrentHashMap实例
ConcurrentHashMap<String, Integer> userVisitCountMap = new ConcurrentHashMap<>();// 模拟用户访问的方法
public void userVisit(String userId) {// 如果用户ID不存在于Map中，就初始化为0userVisitCountMap.putIfAbsent(userId, 0);// 使用原子操作来增加访问次数userVisitCountMap.computeIfPresent(userId, (k, v) -> v + 1);
}// 模拟多线程环境下的用户访问
public static void main(String[] args) {// 创建一个线程池ExecutorService executorService = Executors.newFixedThreadPool(10);// 创建一个随机数生成器Random random = new Random();// 循环100次，模拟100次用户访问for (int i = 0; i < 100; i++) {// 随机生成一个用户IDString userId = "user" + random.nextInt(10);// 提交一个任务，调用userVisit方法executorService.submit(() -> userVisit(userId));}// 关闭线程池executorService.shutdown();// 等待所有任务完成try {executorService.awaitTermination(1, TimeUnit.MINUTES);} catch (InterruptedException e) {e.printStackTrace();}// 打印最终的用户访问次数System.out.println(userVisitCountMap);
}

注：computeIfPresent方法是一个Java 8中新增的方法，它可以对Map中指定的key的值进行重新计算，前提是该key存在于Map中，并且与一个非空值相关联。computeIfPresent方法的语法为：

map.computeIfPresent(K key, BiFunction remappingFunction)

其中，key是要重新计算的键，remappingFunction是一个函数接口，它接受两个参数，一个是key，一个是原来的value，返回一个新的value。如果remappingFunction返回null，那么key对应的键值对会被移除。

举个例子，假设我们有一个Map<String, Integer>，存储了一些人的姓名和年龄，我们想要给所有年龄大于18的人加一岁，我们可以这样写：

Map<String, Integer> nameAgeMap = new HashMap<>();
nameAgeMap.put("Alice", 20);
nameAgeMap.put("Bob", 15);
nameAgeMap.put("Charlie", 18);
nameAgeMap.put("David", 22);// 遍历Map中的所有键，对每个键调用computeIfPresent方法
for (String name : nameAgeMap.keySet()) {nameAgeMap.computeIfPresent(name, (k, v) -> v > 18 ? v + 1 : v);
}// 打印更新后的Map
System.out.println(nameAgeMap);

输出结果是：

{Alice=21, Bob=15, Charlie=18, David=23}

6.4 相关面试题

• ConcurrentHashMap是什么？它有什么优点？

• ConcurrentHashMap是一个存放键值对的容器，和HashMap一样，使用hash算法来获取值的地址，时间复杂度是O(1)。
• ConcurrentHashMap的优点是兼顾了性能和线程安全，可以在多线程的环境下，对同一个key值进行有序的赋值动作，而不会出现数据丢失或覆盖的问题。

• ConcurrentHashMap是如何实现线程安全的？

• ConcurrentHashMap是通过CAS操作和synchronized关键字来实现线程安全的，它使用了一种叫做synchronized+CAS的优化方案，即在不同的场景下，使用不同的同步策略。
• ConcurrentHashMap的get方法是不需要加锁的，因为使用了volatile关键字来保证内存可见性，当一个线程修改了某个节点的值后，其他线程可以立即看到最新的值，而不会出现数据不一致的问题。
• ConcurrentHashMap的put方法和扩容方法是需要加锁的，但是它的锁的粒度很小，只是锁住了链表或红黑树的头节点，而不是整个数组，这样可以减少锁的竞争和阻塞，提高并发度。

• ConcurrentHashMap的结构是怎样的？它和HashMap有什么区别？

• JDK1.8中，ConcurrentHashMap的结构简化了，它是由一个Node数组和多个链表或红黑树组成，Node数组的每个元素是一个链表或红黑树的头节点，链表或红黑树里存放着键值对，当链表的长度超过8时，会转换为红黑树，以提高查找效率。
• ConcurrentHashMap和HashMap的区别主要有以下几点：
  • ConcurrentHashMap是线程安全的，HashMap是线程不安全的。
  • ConcurrentHashMap使用CAS算法，HashMap不使用锁。
  • ConcurrentHashMap不允许null作为key或value，HashMap允许null作为key或value。
  • ConcurrentHashMap的迭代器是弱一致性的，HashMap的迭代器是快速失败的。

• ConcurrentHashMap的put和get方法是如何工作的？

JDK8中，ConcurrentHashMap的put和get方法是基于CAS和synchronized实现的。put方法是先通过hash定位到table数组的某个位置，然后尝试用CAS操作插入新节点，如果失败则加锁后重试或者扩容。get方法是直接通过hash定位到table数组的某个位置，然后遍历链表或者红黑树找到对应的节点，无需加锁。

• ConcurrentHashMap为什么不允许null作为key或value？

ConcurrentHashMap不允许null作为key或value的原因是为了避免歧义和并发问题。如果ConcurrentHashMap允许存放值为null的value，那么当调用get方法返回null时，就无法判断是因为没有找到对应的key，还是因为存的值就是null。这在多线程的环境下会造成混乱和错误。而且，ConcurrentHashMap的内部实现也依赖于key和value不为null的假设，比如使用CAS操作和链表遍历。

• ConcurrentHashMap的并发度是什么？它是如何调整的？

JDK8中，ConcurrentHashMap的并发度是指可以同时更新map的线程数。默认的并发度是16(并发度默认是16的原因可能是为了平衡内存占用和并行度，但是这个值并不是固定的，可以根据实际的并发情况进行调整)。ConcurrentHashMap的并发度是通过CAS操作和synchronized锁的机制来实现的，即将table数组分成若干个节点，每个节点有自己的锁，这样不同的线程可以同时操作不同的节点，提高并发性。

ConcurrentHashMap的并发度可以在构造函数中指定，也可以根据实际的并发情况动态调整。如果并发度过高，会导致内存占用和锁竞争增加；如果并发度过低，会导致并行度降低和性能下降。

• ConcurrentHashMap和HashTable有什么区别？

ConcurrentHashMap是非同步的，而HashTable是同步的。这意味着ConcurrentHashMap不需要在每个操作上加锁，而HashTable需要。这样，ConcurrentHashMap可以提供更高的并发性能和吞吐量。

ConcurrentHashMap使用CAS操作和synchronized锁的机制来保证线程安全，而HashTable使用内部锁的机制。这样，ConcurrentHashMap可以减少锁的粒度和竞争，提高并发性能。

ConcurrentHashMap可以指定并发度，即可以同时更新map的线程数，而HashTable没有这个选项。这样，ConcurrentHashMap可以根据实际的并发情况进行调整，提高性能和内存效率。

• ConcurrentHashMap在JDK1.7和JDK1.8中有什么变化？

ConcurrentHashMap是一个线程安全的HashMap实现

JDK1.7中，ConcurrentHashMap采用了数组+Segment+分段锁的方式实现，每个Segment相当于一个小的HashMap，可以并发地对不同的Segment进行操作，提高了并发性能。

JDK1.8中，ConcurrentHashMap放弃了Segment的设计，改为使用数组+链表+红黑树的方式实现，同时引入了synchronized和CAS来保证线程安全。

这样做的好处是减少了内存占用，简化了代码逻辑，提高了扩容和查找的效率。

7. LinkedHashMap

LinkedHashMap 继承自 HashMap，并在其基础上增加了按照插入顺序或访问顺序进行遍历的功能。具体来说，它在 HashMap 的基础上维护了一个双向链表，用于存储键值对的插入顺序或访问顺序。

在 LinkedHashMap 中，每个键值对都包含了一个 before和after属性，它们分别指向了该键值对在双向链表中的前一个节点和后一个节点。此外，LinkedHashMap 还维护了两个指针head和 tail，它们分别指向了双向链表的头节点和尾节点。当使用插入顺序遍历 LinkedHashMap 时，它会按照键值对的插入顺序来遍历，也就是说，先插入的键值对先遍历。此时，每次插入新的键值对时，它会被插入到双向链表的尾部。

当使用访问顺序遍历 LinkedHashMap 时，它会按照键值对的访问顺序来遍历，也就是说，最近访问的键值对先遍历。此时，每次访问一个键值对时，它会被移动到双向链表的尾部。在 LinkedHashMap 的实现中，除了维护双向链表之外，其他的实现和 HashMap 是一样的。

下面给了一篇介绍LinkedHashMap的文章, 已经写吐了，不想再写了，后面有时间在补！！！

参考文章：

java - HashMap的实现原理(看这篇就够了） - BAT架构技术与大厂面试 - SegmentFault 思否

Java 8系列之重新认识HashMap - 美团技术团队 (meituan.com)

一文看懂 jdk8 中的 ConcurrentHashMap - 掘金 (juejin.cn)

面试 ConcurrentHashMap ，看这一篇就够了！ - 知乎 (zhihu.com)

之前被问的 ConcurrentHashMap 面试题，我汇总了一下 - 知乎 (zhihu.com)

图解LinkedHashMap原理 - 简书 (jianshu.com)