Java 集合 — Map 接口

java突击队2025/12/19大约 24 分钟

📋 本文节选自《Java 集合面试题》，返回查看全部章节

三、Map接口

27. 什么是Hash算法

哈希算法是指把任意长度的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈希值。

28. 什么是链表

链表是可以将物理地址上不连续的数据连接起来，通过指针来对物理地址进行操作，实现增删改查等功能。
链表大致分为单链表和双向链表

1、单链表:每个节点包含两部分,一部分存放数据变量的data,另一部分是指向下一节点的next指针；

![ ][nbsp 1]

2、双向链表:除了包含单链表的部分,还增加的pre前一个节点的指针；

![ ][nbsp 2]

链表的优点

插入删除速度快（因为有next指针指向其下一个节点，通过改变指针的指向可以方便的增加删除元素）
内存利用率高，不会浪费内存（可以使用内存中细小的不连续空间（大于node节点的大小），并且在需要空间的时候才创建空间）
大小没有固定，拓展很灵活。
链表的缺点
不能随机查找，必须从第一个开始遍历，查找效率低

29. 说一下HashMap的实现原理？

HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap的数据结构：在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
HashMap 基于 Hash 算法实现的

1、当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标；

2、存储时，如果出现hash值相同的key，此时有两种情况；(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中

3、获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值；

4、理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比；

需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)

30. HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现

在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做拉链法的方式可以解决哈希冲突。

HashMap JDK1.8之前

JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

![ ][nbsp 3]

HashMap JDK1.8之后

相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

![ ][nbsp 4]

JDK1.7 VS JDK1.8 比较

JDK1.8主要解决或优化了一下问题：

1、 resize扩容优化；

2、引入了红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考；

3、解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题；

不同	JDK 1.7	JDK 1.8
存储结构	数组 + 链表	数组 + 链表 + 红黑树
初始化方式	单独函数： inflateTable()	直接集成到了扩容函数 resize() 中
hash值计算方式	扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算	扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算
存放数据的规则	无冲突时，存放数组；冲突时，存放链表	无冲突时，存放数组；冲突 & 链表长度 <8：存放单链表；冲突 & 链表长度 > 8：树化并存放红黑树
插入数据方式	头插法（先讲原位置的数据移到后1位，再插入数据到该位置）	尾插法（直接插入到链表尾部/红黑树）
扩容后存储位置的计算方式	全部按照原来方法进行计算（即hashCode ->> 扰动函数 ->> (h&length-1)）	按照扩容后的规律计算（即扩容后的位置=原位置 or 原位置 + 旧容量）

31. 什么是红黑树

说道红黑树先讲什么是二叉树

二叉树简单来说就是每一个节上可以关联俩个子节点

大概就是这样子：
		  a
		/\
	b  c
	 /\ /\
	d  e  f  g
/ \/ \/ \/ \
  hi jk lm no

红黑树

红黑树是一种特殊的二叉查找树。红黑树的每个结点上都有存储位表示结点的颜色，可以是红(Red)或黑(Black)。
红黑树的每个结点是黑色或者红色。当是不管怎么样他的根结点是黑色。每个叶子结点（叶子结点代表终结、结尾的节点）也是黑色 [注意：这里叶子结点，是指为空(NIL或NULL)的叶子结点！]。
如果一个结点是红色的，则它的子结点必须是黑色的。
每个结点到叶子结点NIL所经过的黑色结点的个数一样的。[确保没有一条路径会比其他路径长出俩倍，所以红黑树是相对接近平衡的二叉树的！]
红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的结点之后，红黑树的结构就发生了变化，可能不满足上面三条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转和变色，可以使这颗树重新成为红黑树。简单点说，旋转和变色的目的是让树保持红黑树的特性。

32. HashMap的put方法的具体流程？

当我们put的时候，首先计算 key 的 hash 值，这里调用了 hash 方法， hash 方法实际是让key.hashCode() 与 key.hashCode()>>>16 进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幂，计算下标 index = (table.length - 1) & hash ，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。
putVal方法执行流程图

![ ][nbsp 5]

public V put( K key, V value )
{

	return(putVal( hash( key ), key, value, false, true ) );
}
static final int hash( Object key )
{

	int h;
	return( (key == null) ? 0 : (h = key.hashCode() ) ^ (h >>> 16) );
}
/* 实现Map.put和相关方法 */
final V putVal( int hash, K key, V value, boolean onlyIfAbsent,
		boolean evict )
{

	Node<K, V>[] tab; Node<K, V> p; int n, i;
	/*
	 * 步骤①：tab为空则创建
	 * table未初始化或者长度为0，进行扩容
	 */
	if ( (tab = table) == null || (n = tab.length) == 0 )
		n = (tab = resize() ).length;
	/*
	 * 步骤②：计算index，并对null做处理
	 * (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
	 */
	if ( (p = tab[i = (n - 1) & hash]) == null )
		tab[i] = newNode( hash, key, value, null );
	/* 桶中已经存在元素 */
	else {

		Node<K, V> e; K k;
		/*
		 * 步骤③：节点key存在，直接覆盖value
		 * 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
		 */
		if ( p.hash == hash &&
		  ( (k = p.key) == key || (key != null && key.equals( k ) ) ) )
			/* 将第一个元素赋值给e，用e来记录 */
			e = p;
		/*
		 * 步骤④：判断该链为红黑树
		 * hash值不相等，即key不相等；为红黑树结点
		 * 如果当前元素类型为TreeNode，表示为红黑树，putTreeVal返回待存放的node, e可能为null
		 */
		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 );
					/* 判断链表的长度是否达到转化红黑树的临界值，临界值为8 */
					i f( binCount >= TREEIFY_THRESHOLD - 1 ) /* -1 for 1st */
					/* 链表结构转树形结构 */
					treeifyBin( tab, hash );
					/* 跳出循环 */
					break;
				}
				/* 判断链表中结点的key值与插入的元素的key值是否相等 */
				if ( e.hash == hash &&
				  ( (k = e.key) == key || (key != null && key.equals( k ) ) ) )
					/* 相等，跳出循环 */
					break;
				/* 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表 */
				p = e;
			}
		}
		/* 判断当前的key已经存在的情况下，再来一个相同的hash值、key值时，返回新来的value这个值 */
		if ( e != null )
		{

			/* 记录e的value */
			V oldValue = e.value;
			/* onlyIfAbsent为false或者旧值为null */
			if ( !onlyIfAbsent || oldValue == null )
				/* 用新值替换旧值 */
				e.value = value;
			/* 访问后回调 */
			afterNodeAccess( e );
			/* 返回旧值 */
			return(oldValue);
		}
	}
	/* 结构性修改 */
	++modCount;
	/*
	 * 步骤⑥：超过最大容量就扩容
	 * 实际大小大于阈值则扩容
	 */
	if ( ++size > threshold )
		resize();
	/* 插入后回调 */
	afterNodeInsertion( evict );
	return(null);
}

1、判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

2、根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向；⑥，如果table[i]不为空，转向③；

3、判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的；是hashCode以及equals；

4、判断table[i]是否为treeNode，即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值；对，否则转向5；

5、遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操；作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

6、插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩；容。

33. HashMap的扩容操作是怎么实现的？

1、在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进；行扩容；

2、每次扩展的时候，都是扩展2倍；

3、扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置；在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

34. HashMap是怎么解决哈希冲突的？

答：在解决这个问题之前，我们首先需要知道什么是哈希冲突，而在了解哈希冲突之前我们还要知道什么是哈希才行；

什么是哈希？

Hash，一般翻译为“散列”，也有直接音译为“哈希”的， Hash就是指使用哈希算法是指把任意长度的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈希值。

什么是哈希冲突？

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。

HashMap的数据结构

在Java中，保存数据有两种比较简单的数据结构：数组和链表。
数组的特点是：寻址容易，插入和删除困难；
链表的特点是：寻址困难，但插入和删除容易；
所以我们将数组和链表结合在一起，发挥两者各自的优势，就可以使用俩种方式：链地址法和开放地址法可以解决哈希冲突：

![ ][nbsp 6]

链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；
开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。
但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4 （即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化

hash()函数

上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：

static final int hash(Object key) {

	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
}

这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）；

总结

简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：
链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；
开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。

35. 能否使用任何类作为 Map 的 key？

可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：* 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。* 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。* 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。* 用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。

36. 为什么HashMap中String、Integer这样的包装类适合作为K？

答：String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率
都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
内部已重写了 equals() 、 hashCode() 等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况；

37. 如果使用Object作为HashMap的Key，应该怎么办呢？

答：重写 hashCode() 和 equals() 方法

1、重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；

2、重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性；

38. HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

答： hashCode() 方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过 hashCode() 计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
那怎么解决呢？

1、 HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；

2、在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度-1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；

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

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
这个算法应该如何设计呢？
我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。
那为什么是两次扰动呢？答：这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；

40. HashMap 与 HashTable 有什么区别？

1、线程安全：HashMap是非线程安全的，HashTable是线程安全的；HashTable内部的方法基本；都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap ）；

2、效率：因为线程安全的问题，HashMap要比HashTable效率高一点另外，HashTable基本被；淘汰，不要在代码中使用它；（如果你要保证线程安全的话就使用 ConcurrentHashMap ）；

3、对Nullkey和Nullvalue的支持：HashMap中，null可以作为键，这样的键只有一个，可以有；一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。

4、初始容量大小和每次扩充容量大小的不同：；

5、创建时如果不指定容量初始值，Hashtable默认的初始大小为11，之后每次扩充，容量变为原来；的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。

6、创建时如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其；扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小，后面会介绍到为什么是2的幂次方。

7、底层数据结构：JDK1.8以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈；值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

8、推荐使用：在Hashtable的类注释可以看到，Hashtable是保留类不建议使用，推荐在单线程环；境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。

41. 什么是TreeMap 简介

TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。
TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
TreeMap是线程非同步的。

42. 如何决定使用 HashMap 还是 TreeMap？

对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。

43. HashMap 和 ConcurrentHashMap 的区别

1、 ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁；进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。）

2、 HashMap的键值对允许有null，但是ConCurrentHashMap都不允许；

44. ConcurrentHashMap 和 Hashtable 的区别？

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8之前的 HashMap 的底层数据结构类似都是采用数组+链表的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式：

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

1、 HashTable:；

![ ][nbsp 7]

2、** JDK1.7的ConcurrentHashMap：；

![ ][nbsp 8]

3、 JDK1.8的ConcurrentHashMap（TreeBin:红黑二叉树节点Node:链表节点）：；

![ ][nbsp 9]

答：ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步，HashTable 考虑了同步的问题使用了synchronized 关键字，所以 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。

45. ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？

JDK1.7

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式进行实现，结构如下：
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

![ ][nbsp 10]

1、该类包含两个静态内部类HashEntry和Segment；前者用来封装映射表的键值对，后者用来充当；锁的角色；

2、 Segment是一种可重入的锁ReentrantLock，每个Segment守护一个HashEntry数组里得元；素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁。

JDK1.8

在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
结构如下：

![ ][nbsp 11]

附加源码，有需要的可以看看
插入元素过程（建议去看看源码）：
如果相应位置的Node还没有初始化，则调用CAS插入相应的数据；

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

		if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
		break; // no lock when adding to empty bin
	}

如果相应位置的Node不为空，且当前该节点不处于移动状态，则对该节点加synchronized锁，如果该节点的hash不小于0，则遍历链表更新节点或插入新节点；

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

			oldVal = e.val;
			if (!onlyIfAbsent)
			e.val = value;
			break;
		}
		Node<K,V> pred = e;
		if ((e = e.next) == null) {

			pred.next = new Node<K,V>(hash, key, value, null);
			break;
		}
	}
}

1、如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节；点；如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到10个，则通过treeifyBin方法转化为红黑树，如果oldVal不为空，说明是一次更新操作，没有对元素个数产生影响，则直接返回旧值；

2、如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数baseCount；