什么是Map

1.不同于List单列的线性结构，Map提供的是一种双列映射的存储集合，它能够提供一对一的数据处理能力，双列中的第一列我们称为key，第二列就是value，一个key只能够在一个Map中出现最多一次，通过一个key能够获取Map中唯一一个与之对应的value值，正是它的这种一对一映射的数据处理关系，在实际应用中可以通过一个key快速定位到对应的value。综合上面的概念，可以概括出以下几个核心点：

2.Map存储是以k-v键值对的方式进行存储的，是双列的

Map中的key具有唯一性，不可重复

每个key对应的value值是唯一的

3.Java中Map是一个接口，它不继承任何其他的接口，可以说它是java中所有Map的顶级父接口。它的设计理念完全遵循上面的规则，只是具体的实现类种类很多，对应不同应用场景的使用，所以可能具体细节以及设计上存在差异。

Java的Map中提供了三种Map视图以便于展示Map中的内容：

1.只包含key的Set集合

2.只包含value的Collection

3.同时包含key-value映射的EntrySet

另外需要额外注意：不能使用可变的对象作为Map的key，因为一旦该对象出现变化它会导致Map的行为无法预期(这里的变化指的是影响equals方法比较结果的变化)；同时不能将Map本身作为一个Map的key，但是允许将Map本身作为value存入Map结构中。

使用Map的时机

1.存储双列结果

有很多情况下我们都需要将数据梳理成双列的结果集存储起来，最常见的就是当查询数据库时，它返回的结果集中，对应字段名key和记录值value就是一个map，当然如果是列表查询，还会在Map的基础上包装一层List，但是它的每一条记录结果的表示形式就是借助Map来存储的，再比如在数据接收时，如果没有合适的对象接收时，可以考虑使用Map进行接收，最常见的就是前端传入json字符串，后端使用Map来接收数据，但是现在基本都采用JSONObject的方式来接收了，但是Map也是可以作为一个备用选项，在没有其他第三方插件可用的情况下，可以考虑使用Map，或者String接收，然后转成Map。

2.快速定位数据

因为Map的一对一映射的数据关系，利用这一特性，可以快速定位具体数据，现在的一些缓存操作就是利用的这一特点，我们将数据以Map的形式存储在内存中，在缓存的众多数据当中，未来如果需要获取数据时只需要给一个指定的key，可以快速定位到缓存的内容，而不必像List结构那样，需要记住具体的位置才能快速定位，当然如果能够确切记得元素位置，也可以使用List，而且效率更高，但是更多时候是不现实的，我们需要记住每一个元素在List中的位值，数据过多时就比较麻烦了，而且写出来的程序可读性也很差，因为只是通过整型的Index获取，而Map的key可以是任何类型，完全可以定义一个具有明确意义的内容。

3.需要唯一性存储的时候

因为Map的key具有唯一性的特点，我们完全可以利用这一特点作为一个“变异版”的Set来使用，我们知道Set的特点就是不可重复，实际上在Java中，HashSet确实就是这么干的，它将存入的元素放入一个HashMap(Map的一种实现)的key中，而Map中所有的value都是一个固定的Object类型的PRESENT常量，因为它的key不可冗余的特性正好符合了Set的特点，所以在HashSet的底层实现就依托于HashMap，而且Map本身也是无需的，注意：这里的“无序”是“不保证有序”，而不是“保证无序”，这两个概念是有区别的，前者说明结果可能会有序，也可能无序，不能保证；而后者说明结果一定是无序的。所以有时可以发现在遍历HashSet时竟然是有序的，这其实并不冲突。

Map的实现原理

因为Java中Map只是一个接口，它只是定义了一些方法以及规范，所以提到实现原理，还得结合具体的实现类来说明，而且Map的不同实现类，实现的原理也有所不同；Map的实现类很多，就以我当前使用的Java 10.0.2为例，Map接口的实现类就达到了31个之多(包括抽象类)，这还只是JDK内部的实现类，不包括第三方库的实现。所以这里仅仅以几个常见的Map来详细说明，也是面试中经常被提及的几个Map类型：HashMap、HashTable、ConcurrentHashMap、LinkedHashMap等。

HashMap

概念

它是基于Hash表对Map接口的实现，所谓Hash其实就是散列，这里只需要记住：散列就是将一段变长的数据转换成一个固定长度的数据，这个过程称之为散列。在这个过程中会有一系列的算法计算，这里暂不深究；而Java获取对象的hash值比较方便，因为Object类中定义了一个hashCode方法，所以Java中的任何类都有直接或间接继承了hashCode方法，而HashMap就是根据key的hash散列结果来具体定位Map中的元素的；另外在HashMap中是可以使用null键和null值的；而且HashMap不是线程安全的；如果抛去这两点来看，HashMap其实与HashTable大致是相同的。它不能保证映射的顺序恒久不变，即：无法保证有序性；它的容量和加载因子紧密关系着它的迭代性能。

实现原理

整体设计概念上来说，HashMap采用的是数组加链表的方式来存储元素，因为hash可能存在冲突的问题，所以增加链表来存储hash值相同的元素，这种解决hash冲突的方法也叫链地址法。

首先，如果要深入了解HashMap，就必须明白以下四个概念：

capacity：它是指HashMap的容量，表示的是当前HashMap中最大可以存储的数据个数。

size：它反映的是当前HashMap中已经存放的元素个数

loadFactor：加载因子，它表示当前HashMap中的装满程度，默认为0.75,，它跟threshold计算有关

threshold：表示临界值，因为HashMap的容量不是一层不变的，当达到一定程度，就需要对HashMap进行扩容，而这个扩容的临界值就是用threshold表示，它的计算方式是capacity*loadFactor；因为加载因子默认是0.75，也就是说达到最大容量的四分之三时，再往里面加元素，就会扩容。

上面只是一个大致的介绍，下面就来逐步深入介绍相关的设计原理。

hash冲突

hash本身的意思就是散列，它的作用前面也介绍过，就是将一个变长的数据散列成一个固定长度的数据，在Java中，散列的结果是一个int整形数，也就是说hash的结果最大也不会超过Java中整型的最大值，任何对象都具有hashCode方法，我们可以重写hashCode方法，但是对象的数量是海量的，但是hash值就那么多，所以必然存在一种情况：hash值相同但是对象不同，这种现象就是hash冲突。在Java中如果是比较两个对象是否相同也是有策略的，首先会比较两个对象的hashCode方法，hashCode不同，对象肯定不同，这种判断可以隔绝大多数的比较了，而当hashCode相同时，会再去调用equals方法比较，如果equals也为true，这才能说明两个对象是相等的。所以equals为true的对象，hashCode一定是相等的，反之则不然。

HashMap的内部存储容器

map中最基础的存储结构就是数组，具体在HashMap中就是一个Node<K, V>类型的数组table(即hash表)，这是一个可以存储键值对的数据类型组成的数组，我们放入map中的元素全部都被存入到这个数组中，而map容量的扩充实际上也就是对这个数组的不断变更。

HashMap的初始容量设计

使用HashMap的时候，最常用的就是无参的构造方法，然后调用put方法放入键值对，这种方式采用的是默认的初始化策略，此时当我们刚刚new出一个HashMap对象时，它的内部table数组实际上是一个null(我这里是以java 10.0.2为版本介绍的，其他版本可能略有不同)。只有当我们第一次调用put时才会进行table的初始化。此时它的capacity会被设置为DEFAULT_INITIAL_CAPACITY = 1 << 4，也就是16。加载因子loadFactor是默认的0.75，所以这时候它的threshold是12。

但是我们在创建HashMap时也可以指定capacity甚至是loadFactor，这里一般不推荐修改loadFactor：

//DEFAULT_LOAD_FACTOR = 0.75f

public HashMap(int initialCapacity) {

 this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

需要注意的是：它传入的initialCapacity并不是最终我们构建的HashMap对象的容器大小，它会经过一次运算，得到一个比initialCapacity值稍大的数值，并且一定是离initialCapacity最近的那个2的N次幂的值，比如：我们传入5，它就会找到8，传入9，就会找到16。也就是说最终得到的capacity的值一定是2的某个次幂。这个过程是需要计算的，JDK中采用是一种比较高效的位移运算，具体如下：

首先来看几个简单示例：

5   0000 0000 0000 0101      |      19  0000 0000 0001 0011

7   0000 0000 0000 0111      |      31  0000 0000 0001 1111

8   0000 0000 0000 1000      |      32  0000 0000 0010 0000

—————————————————————————————————

9   0000 0000 0000 1001      |      37  0000 0000 0010 0101

15  0000 0000 0000 1111      |      63  0000 0000 0011 1111

16  0000 0000 0001 0000      |      64  0000 0000 0100 0000

根据上面的数据展示，可以看到如果我们想要将5最终变成离它最近的那个8，需经历：5 — 7 — 8这么一个过程，也就是将它的原本二进制数据有效部分全部转换成1，然后在此基础上加1就可以得到目标值，同理9到16,19到32等也是如此，而JDK中HashMap源码采用就是这种不断右移然后按位或运算，最终得到一个有效数据部分全为1的数值，然后加1得到结果，这样再来看HashMap的这部分计算源码就不会迷惑了：

static final int tableSizeFor(int cap) {

 int n = cap – 1;

 n |= n >>> 1;

 n |= n >>> 2;

 n |= n >>> 4;

 n |= n >>> 8;

 n |= n >>> 16;

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

}

可以看到，最终计算出来的n与MAXIMUM_CAPACITY比较，只要比它小，就会加1，而在此之前的逻辑主要就是为了将对应的二进制位全部转换成1。这里有一点需要注意：按照上面介绍的逻辑会有有个情况，就是如果我们传入的数值本身就是2的次幂值，那就会有问题，因为此时传入的capacity本身就已经可以作为初始容量了，解决方式很简单，就是上面方法中的第一步操作，先将传入的capacity减1，再进行计算，此时如果传入的是8，那么减1之后，n其实是7，经过计算后正好是8，符合逻辑；那如果此时传入的是9，虽然减1后得到了8，但是此时需要的是更大数值的16，经过位移计算，正好得到15，加1后得到16，所以逻辑上也没有问题。

HashMap的存储

HashMap的存储方式就是利用了map中的key的hash值作为定位基础的，具体做法就是：我们在存入一个k-v键值对的时候，它会计算key的hash值，也就是调用key对象的hashCode方法，因为hashCode的取值范围是整个整型范围，所以可能会非常大，为了让它能够和table数组的下标index挂钩，这里就会将得到的hashCode值与table的长度取模，这样得到的数据肯定是在table.length之内的整数，然后用它作为数组对应的下标。注意：这里JDK采用了一定的优化，它的取模并不是常规的hash % table.length，它使用的是hash & (table.length – 1)这种按位与的操作，这么做有两个好处：

首先就是效率很高，比正常的取模运算符要快

避免了负数问题，结合前面的初始容量设计可以知道，table.length – 1得到的一定是一个正数值，所以它的最高位一定是0，而0与任何数按位与运算，得到的一定是0，此时无论hashCode值是整数还是负数，计算出来的结果一定是正数。

而为何会出现hash & (table.length – 1) == hash % table.length呢？其实想想也能明白：

经过前面分析可以得到table的长度必然是：table.length == 2^N，则hash % table.length实际上就是hash / table.length然后取余数，也就是hash >> N 位移运算过程中，移出的那部分数据即为需要的模运算结果。而table.length – 1的结果必定是一个二进制有效位全为1的数据(参考前面容量初始化设计)，此时hash与减1后的值进行按位与，可以保证低位的结果保留，而超过table.length – 1数值的高位部分得0，这个结果正好就是前面位移运算过程中需要得到的那个移出的部分。

按照上面的介绍，最终可以根据key的hash得到一个对应的数组位置index，但是我们也知道hash是会冲突的，这里如果出现了冲突，经过计算后得到的index位置上已经有元素了怎么办，这时候链表结构就发生作用了，它会将最新添加的元素放在数组中，将该位置上之前的元素以链表的形式放在新加入的元素的后面，Node的设计本身就是一种链表存储格式：

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

 final int hash;

 final K key;

 V value;

 Node<K,V> next;

 …

}

所以：数组中的元素肯定是最新放入的元素，之前的老元素会按照链表的方式挂在最新元素的后面。这种存储就是数组加链表的存储方式。

需要注意的是：HashMap中使用到的hash值并非是对应key对象上调用hashCode方法，它又经历了一步计算：

static final int hash(Object key) {

 int h;

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

}

这么做的目的也就是为了降低hash冲突，尽可能的让key的每一位数据都会影响到散列的结果，所以它会对hash进行扰动计算，防止hashCode的高位不同但低位相同导致的hash冲突，将hash的高位和低位的特征结合起来，共同影响hash结果，尽可能将每一位数据都与hash结果相关联，从而降低冲突。具体的计算，强烈推荐H大的博文：透彻分析hash()

随着数据的不断增多，冲突的可能性就会越来越大，极端情况就是链表部分会变得很长，而链表结构的增删的效率很高，但查询的效率很低，这样如果链表过长，会影响Map的查询性能，所以JDK1.8之后，对链表部分做了改动，一旦链表的长度超过了8个Node，就会直接转换成红黑树结构，检索的时间复杂度大大降低。

另外对于扩容方面，如果元素个数超过了capacity*threshold的值，容器就会调用resize方法扩容，扩容很简单：就是将原来的oldCapacity << 1，也就是直接扩大一倍，这样也保证了capacity的值始终都是2的指数值。

使用HashMap时机

总体上来说，HashMap的查找效率比较高，常见的应用场景中，需要使用Map的地方，HashMap足以解决大多数问题，而且它的效率也是很高的，如果数据量较大，这个效率提升还是很可观的，如果没有线程安全的要求，并且可以允许Key出现null值的情况下，可以考虑使用HashMap。

HashMap的问题

线程安全

观察HashMap的源码，可以看到，没有任何线程安全的概念，对于put，remove等操作方法，没有任何加锁、同步化的操作，所以它是线程不安全的，在多线程环境下，可以考虑如下方案：

使用HashTable，但是效率极低，它是方法加锁，加锁粒度很粗糙，性能较低

使用Collections工具类可以创建一个线程安全的HashMap，实际的结果跟前面一种类似，也是一种方法加锁，不推荐

可以考虑在自己的业务逻辑中自行实现同步逻辑，灵活性较高，但是会影响代码的整体阅读逻辑

可以使用ConcurrentHashMap，它是也是线程安全的map，引入了段加锁机制，效率比HashTable要高很多

另外，据网上有些博客提出：在并发状况下，多个线程同时对一个map进行put，可能会导致get死循环，具体可能表现为：

多线程put操作后，get操作导致死循环。

多线程put非NULL元素后，get操作得到NULL值。

多线程put操作，导致元素丢失。

但是这种情况我写了一些demo，暂时没有出现上面这种情况，可能是因为JDK版本的缘故，新版本的HashMap做了一定的优化，故暂时无法重现这个问题。

性能开销

hash函数的计算会影响这个性能，对于一些极端情况，例如对象比较复杂，hash的计算可能比较耗时，这部分性能的损耗也应该考虑在后续实际生产中，如果Map中存储的key比较复杂，就要考虑是否需要换一种存储方式了。

初始容量设置问题

我们在创建一个HashMap的时候，一般都是用默认的无参构造方法，这种方法虽然方便，但是性能上面可能并不是最符合我们当前正在运行的程序环境，所以一般都建议指定一个初始容量，这样可以尽可能保证减少map扩容带来的性能耗损问题，同时也减少了rehash(扩容后重新进行hash计算)的次数，对性能的提升也有一定好处。

但是初始容量的设计也是有讲究的，不能越大越好，要最符合当前的应用环境，当然前提是能够预知到map中到底会存储多少元素，否则默认的构造方法是最好的选择。在阿里巴巴的Java开发者手册中给出了一个计算初始容量的公式：

capacity = (要存储元素个数 / 加载因子loadFactor) + 1

//加载因子loadFactor默认0.75

其实这种计算方案在Google的Java开源工具库guava也有，最终的灵感来源还是JDK源码中HashMap的putAll方法得来的，它里面采用的就是这种计算方式，它这么设计是有一定的好处的：

例如现在需要加入7个元素，如果只是直接传入7，那么最终的HashMap容量会被设置为8，但是由于此时threshold = 8 * 0.75 = 6，所以在加入第七个元素的时候会有一个hash表扩容，这个是比较耗费资源的操作。而如果使用上面推荐的公式，可以计算最终传入的值为：7 / 0.75 + 1 = 10；那么最终计算后的capacity为16，在进行元素装入的时候就可以有效避免过于频繁的hash表扩容操作，从而提升性能。

其他

说到HashMap，这里顺便说一下HashSet，它在前面也稍微提到了一下，它是一种Set，Set的特性就是：无序，唯一。而HashSet的底层实现就是利用的HashMap的key唯一性特点，而且HashMap本身也是不保证有序的，所以正好与Set的特性不谋而合，所以HashSet在存储元素的时候，都是将元素存入HashMap的key中，value部分始终都是一个固定的常量Object对象，没有实际意义。

HashTable

首先在概念上，它基本上与HashMap没有太大区别，甚至于使用的方式都差不多，不同的只是它的底层设计上与HashMap存在一定的差异，而正是这些差异，使它的使用场景更加单一。另外：HashTable是不存能出null值的，无论是key还是value，这点与HashMap完全不同，而且它是线程安全的。

实现原理

它的整体设计思路基本和HashMap差不多，都是基于Node数组进行存储，这个Node实际上就是一个链表的节点类型，内部维护一个Node类型的数组，Node的结构设计基本都差不多，下面主要从几个与HashMap不同的地方说明以下具体的细节差异。

线程安全

首先明确一点，HashTable是线程安全的，看它的源码就知道了，它里面的所有涉及到更新HashTable的操作都被加了synchronized锁。

继承关系

与HashMap不同的是HashTable继承自Dictionary(HashMap继承自AbstractMap)，这是一个非常古老的抽象类，它从java1.0的时候就已经存在了，现在连这个类的头部注释中都说这个类已经是obsolete（过时的）类了，对于现在的JDK而言，Dictionary所能达到的效果，Map接口都能达到，甚至还比它的灵活性更高(因为接口可以多实现，类只能单继承)，所以官方推荐后续的实现都基于Map接口了。

迭代

HashTable的遍历使用的是枚举Enumeration，而不是我们常见的Iterator迭代器，例如我们如果调用它的keys方法，它会返回一个Enumeration类型的对象，这个查看一下源码就可以很清楚的看到。当然，它本身也是有Iterator的，Enumeration是因为历史遗留问题才一直存在的。它的Iterator迭代与HashMap都是支持fast-fail的，fail-fast这里就不再赘述，参考Java集合–List。

初始容量设计

它默认的初始容量为11，并非HashMap的16，但是它的默认加载因子loadFactor却仍然是0.75，官方采用0.75做加载因子其实也是经过时间空间的消耗权衡得到的结果，按照官方的注释解释：如果过高，虽然会减少空间上的开销，但是会增加查询上的时间成本，所以才说不建议修改loadFactor。

扩容设计

它的扩容不同于HashMap的直接翻倍，每次当容量达到threshold后，新的capacity = 2 * oldCapacity + 1。所以它的到的capacity值始终都是一个奇数，默认是从11开始的。另外它也没有对传入的capacity再计算的过程，它的源码中只有如下设计：

if (initialCapacity==0)

 initialCapacity = 1;

this.loadFactor = loadFactor;

table = new Entry<?,?>[initialCapacity];

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

可以看到，只是对initialCapacity进行了是否为0的判断，如果为0，默认赋值为1，否则capacity的值就是传入的值。所以我们在构建HashTable对象时，如果需要传入capacity，最好也按照它的设计初衷，传入一个奇素数。

hash计算

HashTable的hash计算就是直接调用key对象的hashCode方法，没有进行进一步扩散计算，而且它的取模运算也没有HashMap那种采用效率更高的&操作，据说这是跟HashTable的长度数值有关，当哈希表的大小为素数时，简单的取模，哈希的结果会更加均匀。没有具体深入研究过，有待探讨。

HashTable的问题

性能

它的性能问题是广为诟病的，因为它的synchronized锁都是加在方法上的，synchronized本身就是重量级锁，并且加锁粒度又很粗糙(方法级锁)，我们在现实场景中，其实99%的情况可能都不会出现线程安全问题，所以仅仅为了那1%的并发安全去使用它多少有点浪费性能，完全可以自己控制同步，而且如果有选择，选择ConcurrentHashMap也是一种不错的方案。只有在一些特殊的应用场景中可能会采用HashTable存储数据。

并发迭代修改

虽然HashTable被描述为线程安全的，似乎在多线程环境下就不存在任何问题了，但是仍需注意，如果我们使用迭代器对HashTable进行遍历的时候，它采用的是fail-fast机制，所以仍然有可能抛出ConcurrentModificationException异常。另外HashTable的另一种迭代方式：Enumeration，它是不支持fail-fast的，所以如果有需要检测这种并发修改迭代的情况，Iterator是唯一的选择。

ConcurrentHashMap

原理

因为HashTable的加锁粒度过大，所以JDK1.5以后出现了这个同样支持并发操作的Map结构，ConcurrentHashMap引入了Segment（段）的机制，所谓段，就是将Map的容器进行分段(也就是常说的“桶”)，每段单独加锁，所以当并发修改时，如果不是同时操作同一个段内的数据，段与段之间是互不影响的，这就是所谓的锁分段技术，正是因为段与段之间是独立的加锁，所以大大提升了并发性能。

对于java6和java7的版本中，主要就是segment机制的引入，内部拥有一个Entry数组，数组中每个元素又是一个链表结构，但是同时也是一个ReentrantLock(Segment继承了ReentrantLock)。

而Java8以后，ConcurrentHashMap做了很大的改动，有些甚至是颠覆性的，它摒弃了之前一直使用的Segment机制，虽然源码中仍然存在该类，但是源码的注释中已经说明了它是一个unused(无用的)类，它只是用来兼容之前版本的ConcurrentHashMap。新版本的ConcurrentHashMap采用了CAS算法，无锁化的操作大大提高了性能，底层仍然采用HashMap的那套实现，即：“数组+链表+红黑树”的方式。同时为了做到并发，也增加了一些辅助类，如：TreeBin、Traverser等内部类。

继承关系

ConcurrentHashMap除了和HashMap一样继承了AbstractMap，同时它也实现了一个叫ConcurrentMap的接口，这个接口的作用主要是为Map提供线程安全以及原子性的保证。另外不同于HashMap，它没有实现Cloneable接口，所以如果涉及对象复制，需要额外考虑其他方式。其他的基本都与HashMap一致了。

初始化容量和扩容机制

对于初始容量的设置，默认加载因子以及扩容的方式，ConcurrentHashMap采用的方案与HashMap的机制是一模一样，所以对于HashMap的那一套在这里是通用的，它的内部结构也是一个Node数组，并且它的Node类的内部定义几乎与HashMap的一致，不同的是此时的Node中代表Value的val和指向下一个Node节点的引用next是volatile修饰的，这个也是为了在高并发情况下，为不同线程间数据可见性而考虑的。而且不仅仅是这两个字段，在整个类中，除去静态常量，其余的变量几乎全部都用volatile修饰。

如果在创建ConcurrentHashMap对象时，我们手动传入了capacity值，这里它不是像HashMap那样直接对传入的capacity值进行计算求取最近的2的指数值，而是会将传入的initialCapacity进行如下运算：

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

而这里的tableSizeFor方法就是根据传入的值，对capacity进行不断位移以及按位或的操作，最终求出一个合适的2的指数值。即：如果创建ConcurrentHashMap对象时，如果指定了capacity，在实际创建最大容量时，会先对传入的capacity扩大3倍并加1，再根据此时的值再此进行求取最近的不小于该值的2的指数幂值。

几个重要的属性

前面HashMap中介绍过的几个重要属性这里就不再重复了，这里就重点提一下sizeCtl属性，它的作用很大，用途比较多，根据不同的值，可以分为以下几种情况：

负数代表正在进行初始化或扩容操作

-1代表正在初始化

-N表示当前有N – 1个线程正在进行扩容

整数或0代表hash还没有被初始化，此时它的值表示的是初始化大小或者是下一次扩容的大小，有点类似于前面介绍过的threshold(阈值)的概念，它的值始终是当前ConcurrentHashMap容量的0.75倍，与loadFactor正好相对应。

//下面两个值主要是用于与hash值进行比较时使用，判断当前节点类型

static final int MOVED     = -1; // hash值是-1，表示这是一个forwardNode节点

static final int TREEBIN   = -2; // hash值是-2  表示这时一个TreeBin节点</pre>

MOVED和TREEBIN在容器扩容，遍历以及存放元素的时候，有很重要的作用。

核心类

Node

跟HashMap一样，它是包装了K-V键值对的类，前面说过，它的整体设计思路跟HashMap几乎一样，只是它的value和next属性使用了volatile修饰，保证了在并发环境下线程间的可见性，同时比较有意思的是它的setValue方法：

public final V setValue(V value) {

 throw new UnsupportedOperationException();

}

可以看到，它不允许直接使用setValue方法对Node中的value属性进行修改，如果这么做，会直接抛出异常。这个方法在HashMap中是可以正常使用的。同时，相较于HashMap，它又新增了一个find方法，注释上解释它的功能主要是为了辅助map.get方法，在子类中会进行重写。

TreeNode

当Node的链表结构过长时（一般是为8个元素），HashMap就是将其转换成红黑树形式，而转换的基础就是直接借助TreeNode，但是ConcurrentHashMap中却不是直接使用TreeNode，它是将这些TreeNode节点放在TreeBin对象中，然后由TreeBin完成红黑树的包装，而且这里的TreeNode是继承自ConcurrentHashMap中的Node类。

TreeBin

TreeBin的作用很明确，它的构造函数就一个，接收的参数就是TreeNode，它对TreeNode进行包装，甚至于当链表转换成树结构的时候，哪怕它的根节点也是TreeBin，并非HashMap中的TreeNode，所以可以说：ConcurrentHashMap中，如果数组中某个数组位置上的结构转变成了树结构，那么存储在数组中的实际元素就是TreeBin对象。而对于其他没有转换成树结构的位置(链表长度仍然在8个以内)，仍然是原本的Node类型。

ForwardingNode

一个用于连接两个table的节点类，这个类在进行扩容的时候有很大的作用，它内部包含了一个nextTable引用，类型是Node类型，而且它的key、value以及next都是null，hash值为-1，后面在介绍扩容的时候会说道它的作用。

CAS无锁化

UnSafe静态代码块

在我当前使用的java10.0.2版本中，源码的6373行到6403行这段代码是无锁化的静态语句块部分，它里面利用了jdk.internal.misc.Unsafe类对一些重要属性的修改采用CAS操作，大大提高了程序的性能，因为没有锁的开销问题，许多锁带来的问题也就不存在了。

三个无锁化的核心方法

//获取tab数组中i位置上的Node

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {

 return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);

}

//利用CAS设置tab数组中i位置上的Node节点，这里就是典型的CAS操作，设置值的时候，传入待修改的值v和比较值c

//在修改时，将c的值与内存中的值比较，只有相等时，才将该位置上的Node设置为传入的v，否则修改失败

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,

 Node<K,V> c, Node<K,V> v) {

 return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);

}

//顾名思义，这个方法就是利用CAS操作，将tab数组中的i位置设置为传入的v

static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {

 U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);

}

正是有了上面这三个核心操作，才保证了ConcurrentHashMap的线程安全的特性。

初始化initTable

在构建ConcurrentHashMap对象的时候，它的构造方法采用的策略和HashMap中的大致是一样，在构造方法中其实并没有对具体的存储数组进行指定，只是简单初始化了一些必要的参数指标，具体的table的初始化都是放在插入元素时进行的，在插入前会对table进行null值判断。

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

  Node<K,V>[] tab; int sc;

  while ((tab = table) == null || tab.length == 0) {

    //根据前面的介绍，此时sizeCtl若小于0，表示有其他线程正在进行初始化操作

    //此时当前线程放弃初始化，自旋直至其他线程初始化结束

    if ((sc = sizeCtl) < 0)

      Thread.yield(); 

    else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {

      //此时表示当前线程得到了初始化权限，此时将sizeCtl设置为-1，阻止其他线程进入

      try {

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

          //DEFAULT_CAPACITY = 16

          int n = (sc > 0) ? sc : DEFAULT_CAPACITY;

          @SuppressWarnings("unchecked")

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

          table = tab = nt;

          //此时n是当前table容器的大小，n>>>2实际上就等于0.25n

          //所以sc = 0.75n

          sc = n – (n >>> 2);

        }

      } finally {

//修改sizeCtl的值为当前容器大小的0.75倍值

        sizeCtl = sc;

      }

      break;

    }

}

return tab;

}

扩容transfer方法

由于这个方法过长，这里就不再贴它的源码了，强烈建议琢磨一下源代码，它里面的涉及到的设计思路还是比较精妙的，它的大致扩容思路是这样的：

开始的时候它会进行一次CPU的可用线程的计算，根据可用线程数目和 Map 数组的长度，平均分配处理当前待扩容的“桶”。默认的是每个线程需要处理16个“桶”，所以换句话说，如果当前map的容量为16的时候，那么扩容阶段就只有一个线程在扩容。

它在扩容时需要用到一个额外的数组空间nextTable，它的大小是原table的两倍，一旦扩容完成，原来的table就会被新的nextTable所取代。

扩容后，就是将原来数组中的内容复制到新的nextTable数组中去，这里的复制转移并不是简单的copy，它是有策略的

通过前面的分析我们知道，数组中的元素存在不同的情况，既有Node(此时说明是链表结构)，也会有TreeBin(链表过长转换成了红黑树)以及null(这部分是还未存放元素的“桶”)。

首先在进行遍历复制的时候，原数组中null的位置在新的数组中同样位置上会插入一个占位符forwarNode节点，当其他线程在遍历到当前节点是forwardNode类型，就直接跳过该节点，继续向后遍历。

剩下的链表和红黑树结构中，在复制到新的数组中时会对其进行拆分，拆分的规则是将当前节点的hash值与length进行取余操作，假如在原数组中的位置是index，那么根据取余的结果，如果为0，就在新数组的index位置防止，否则不为0的话，就将其放在index+n的位置，这里的n一般就是16。

这样原来数组中的链表和红黑树部分就都各自被拆分成了两份存储在新的数组中，原来的null位置依然为null，没有任何变化，这样就完成了数组的扩容操作。下面一份关于扩容的示意图：

首先我们现在假设当前map的容量为16：

concurrentHashMap01.png

其余数组中的内容暂时不用考虑，单独看这里的index为1和4的位置上的内容，假设其他位置上的内容都是null，那么扩容后，数组的容量就会变成32，然后1位置上的蓝色节点会组成一个新的链表，放在新数组中的1位置上，而1位置上的黄色节点会组成新的链表放在新数组的17位置上。同样的4位置上此时链表长高度达到8，应为树结构，但是为了方便表示，这里也将其画成了链表结构，在拆分后，蓝色黄色节点各自组成新的链表，且长度减到了4，重新变成了链表结构，如果拆分后链表长度仍然过长，扩容后仍然会保持红黑树结构。

concurrentHashMap02.png

put方法存放元素

首先需要明确的是，ConcurrentHashMap中put是不能存放key或者value为null的元素的，否则会直接抛出空指针异常，这一点有别于HashMap。另外因为ConcurrentHashMap可以运行于多线程环境中，所以它的put方法逻辑比较复杂，简单来说，它的put方法的主要逻辑就是：

首先根据传入的key计算对应的table中的位置index

判断table[index]当前位置中是否存在元素，如果没有元素，直接放入，没有加锁操作

如果当前位置上已经存在元素了，节点上锁，然后依次遍历链表节点，如果遇到了key和hash都是一致的元素，就更新这个位置上的value，注意这里的上锁的节点可以理解为hash值相同组成的链表的头结点。

如果一致遍历到节点链的末尾，都没有找到key和hash都相同的元素，那么就可以认为它是一个插入操作，此时就把这个节点插入到链表末尾。

如果table[index]位置上的内容为树节点，就按照树的方式是插入节点

在插入结束后，如果是链表结构，需要判断当前链表长度是否达到了8，如果是，还需要将其转换成红黑树。

最后同步更新一下当前map中的元素数量

可以看到，新版本的ConcurrentHashMap中，put时锁住的是Node节点，而不是像之前JDK1.6和1.7那样锁住整个segment。而且在锁住Node之前的操作也是线程安全的，它的线程安全就依托于前面介绍过的三个核心的CAS方法。

size属性

因为可能存在高并发的情况，所以不像HashMap那样直接调用size方法就可以准确获取当前map中的元素个数，在高并发下，可能存在当我们需要获取size值的时候，其他线程正在往map中写数据，我们不能像虚拟机的垃圾回收一样，在统计时“Stop The World”，所以得到的size值其实并不是一个精确的值。对于这个大概的size值的获取，ConcurrentHashMap也是利用了一些策略才得到的，并非直接返回size属性值。

辅助的内部类和变量

@jdk.internal.vm.annotation.Contended static final class CounterCell {

 volatile long value;

 CounterCell(long x) { value = x; }

}

//它是一个基于计数器的值，其实也就是存放的是map中的元素个数，使用CAS更新

//但是它并不是强制的等于当前map中元素的个数

private transient volatile long baseCount;

//当调整大小、创建CounterCells时用于CAS自旋锁操作

private transient volatile int cellsBusy;

//计数表，当非空的时候，它的容量是2的幂

private transient volatile CounterCell[] counterCells;

size方法

public int size() {

 long n = sumCount();

 return ((n < 0L) ? 0 :

 (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :

 (int)n);

}

//JDK1.8开始新增的一个方法，它与size方法很类似，而且从它的注释上来看，很推荐使用它来代替size方法

public long mappingCount() {

 long n = sumCount();

 return (n < 0L) ? 0L : n; // ignore transient negative values

}

//无论是size还是mappingCount，都没有直接返回baseCount的值

//而是在baseCount的基础上继续进行了计算，即便如此，它得到的仍然是一个估计值

final long sumCount() {

   CounterCell[] as = counterCells; CounterCell a;

   long sum = baseCount;

   if (as != null) {

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

       if ((a = as[i]) != null)

         sum += a.value;

       }

     }

   return sum;

}

addCount方法

前面在介绍put方法的时候，在最后一步说到“同步更新一下当前map中的元素数量”，这句话在put方法的代码中其实就是调用addCount方法，而这个方法会做两件事情：利用CAS对baseCount的值进行更新，然后判断此时是否需要扩容。

ConcurrentHashMap的问题

size的准确性

上面说过，它的size方法得到的值并不是一个准确的值，但是在大多数情况下，这个值是可以保证的，只有在极端并发环境下才有可能出现不一致的情况，所以我们在使用时，不能依赖于size方法来确定map中精确的元素个数，应当有适当误差。并且现在也更加推荐了mappingCount方法来代替size方法使用。

数据覆盖问题

当我们在高并发环境下，纯粹put或者get操作，其实是没有问题的，但是当我们调用get之后，在下次调用put方法之前，如果有其他线程也对该map调用了put方法，那么后续在调用put方法的时候，就有可能把刚才其他线程填入的值覆盖掉，即使ConcurrentHashMap中使用CAS操作，仍然不可能完全避免这种情况。但是这中属于具体编码问题，控制合理的话，编码人员可以避免这样做，只要稍加注意，可以采用一些额外的手段保证它的一致性。

空值问题

一定不能使用ConcurrentHashMap的put方法放入一个key或value为null的元素，否者直接NullPointerException。

LinkedHashMap

原理

可以看以下它的定义：

public class LinkedHashMap<K,V>

 extends HashMap<K,V>

 implements Map<K,V>

从它的定义中可以明显的看出，它就是HashMap的子类，所以它的一切都是基于HashMap的，查看它的源代码可以看到，它的初始化，扩容，元素的存放与获取底部都是基于HashMap的那一套原理，所以这里就不再继续介绍了，但是它有一个HashMap没有的特点，就是双向链表，简单来说就是：它的本身的存储结构依然采用HashMap的那套数组加链表的方式，但是它的节点内部又多维护了两个引用before和after，before指向当前元素之前放入的元素，next指向紧接着放入的元素引用，所以它们的引用关系与放入Map中的元素顺序有关，也就是说它除了之前介绍的每个“桶”内部的链表结构，桶与桶之间的不同节点也有一个引用在维护，并且是双向的链表结构，这样整体的感觉就是：

LinkedHashMap01.png

概括起来就是：它的主体存储结构仍然是HashMap的那套逻辑，只是在HashMap的基础上，每个节点又多维护了一份之前存入的元素引用以及之后存入的元素引用，这样每个节点内部算起来实际上有三个引用（HashMap本身就有一个链表引用，主要是hash值相同的元素之间的引用，然后又有了这个新增的两个引用）。

LinkedHashMap02.png

特点

从它的结构可以看出，HashMap所拥有的特性它都是存在的，同时因为加入了双向链表的维护，所以它是一个有序的Map，前面说过，HashMap是不保证有序的，也就是它遍历的结果可能与它放入的顺序不是一致的（不保证结果有序性，并不是一定是无序的），而LinkedHashMap的结果必定是有序的，所以如果需要使用有序的Map场景，可以考虑使用LinkedHashMap。

使用场景

前面介绍过的Map的使用时机这里都完全可以适用于LinkedHashMap，此外它还可以保证结果的有序性，所以如果对遍历的有序性有要求，可以使用它。

另外：它还可以用来实现LRU(Least recently used, 最近最少使用)算法，这是因为它内部有一个removeEldestEntry方法，这个方法的返回值为boolean类型，如果我们需要实现LRU，可以继承自LinkedHashMap，重写它的方法，此时，如果需要使用实现LRU，它有一个属性必须设置为true，那就是：accessOrder，只有它为true的时候，双向链表中的元素就会按照访问先后顺序排列。这里有一个简单使用的例子：

public class LRU<K, V> extends LinkedHashMap<K, V> implements Map<K, V> {

   public LRU(int initialCapacity, float loadFactor, boolean accessOrder) {

   super(initialCapacity, loadFactor, accessOrder);

 }

 @Override

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

   //保证map中元素个数

   return size() > 6;

 }

 public static void main(String[] args) {

   LRU<Character, Integer> lru = new LRU<Character, Integer>(

     16, 0.75f, true);

   String s = "abcdefghijk";

   for (int i = 0, len = s.length(); i < len; i++) {

     lru.put(s.charAt(i), i);

   }

   System.out.println(lru); //{f=5, g=6, h=7, i=8, j=9, k=10}

 }

}

最终得到的结果可以看到，map中始终都是只包含6个元素，如果过多，之前插入的节点都会被抛弃，抛弃的都是最近最少使用的节点。

存在的问题

总体来说，前面说道到的HashMap的存在的问题在这里仍然是存在的，它不是线程安全的，而且它的存储开销比HashMap更大，这个也好理解，毕竟它又多了一个双向链表的维护，所以无论是复杂度还是维护成本都会高一些。

ConcurrentSkipListMap

介绍

最后再来看一个基于跳表的数据结构，它是一个支持排序和并发的Map，是线程安全的，这种跳表的结构我们正常开发中很少用到，所以对于我而言，它是一个知识盲点，下面就简单介绍一下这个跳表。

原理

在介绍跳表之前，首先需要知道传统的链表结构是什么样子，传统的链表是一个线性结构，如果我们需要查询某个元素，需要从链表的头部挨个遍历访问，然后找出目标元素。所以，链表结构的查询需要O(n)的时间，它与链表长度紧密相关。而跳表就是基于传统链表上做的一次改进，它是采用空间换时间的方式来提高查询效率，这里以一个最简单的方式来描述一下它的数据结构，实际情况中它的结构会比下面的图示复杂一点，后面会介绍：

SkipListMap1.png

上面的结构就是最简单的一种跳表的结构，首先需要明确的是：跳表天然是有序的，所以上面的链表结构是有序的。它除了正常的链表结构(有一个引用指向下一个节点)外，每个节点多了一个引用，用于指向下下个节点，这里，如果我们查询一个值为12的元素，具体查询步骤就是：

SkipListMap2.png

首先12与1比较，比1大，向后找到6节点

12与6比较，比6节点大，向后找到9节点

12与9比较，比9节点大，向后找到17节点，说明12在9节点与17节点之间

12与9比较，比9节点大，向后找到12节点，即为目标节点

可以看到，它的查询是跳跃式进行的，跳过了中间的3和7节点，所以它查询的时间复杂度为O(n/2)。但是前面也说过了，这只是最简单的一种方式，实际情况中，一个链表节点的内部可能包含的不仅仅只有两个引用(下一个节点+下下个节点)，每个节点内部到底会带有多少个后续节点的引用是随机生成的，所以实际情况可能是这样：

SkipListMap3.png

每个节点中拥有的后续节点的引用个数不定，这是一种概率均衡技术，而不是强制性均衡约束，所以对于节点的插入和删除比传统的平衡树算法更为简洁高效。

查找

SkipListMap4.png

例如查找值为12的元素，就会按照红色箭头上的数字步骤查询即可，这里就不再赘述了。

插入

找到需要插入的位置

申请新的节点

调整指针

SkipListMap5.png

上图的解释如下：

假设我们这里需要插入一个值为15的节点，最后找到的位置就是上图中红色圆圈的位置，然后申请新的节点，将节点调整指针，放入12的后面即可，这里有一个技巧：使用一个update数组保存将要插入位置之前的节点直接引用，这里就是上图中红色线框框住的三个引用，因为在插入节点时，只有这三个引用可能涉及到指针的调整。调整后的情况即为：

SkipListMap6.png

删除

删除操作其实和插入很类似，找到节点，将其删除，然后调整指针即完成整个删除操作，插入逻辑中用到的update数组技巧在这里仍然适用。

Java中的ConcurrentSkipListMap实现

在java中，跳跃表是具有层级结构的，即所谓的level，整体结构大致如下：

SkipListMap7.png

跳表的结构具备以下特征：

最底层包含所有节点的一个有序的链表

每一层都是一个有序的链表

每个节点都有两个指针，一个指向右侧节点（没有则为空），一个指向下层节点（没有则为空）

必备一个头节点指向最高层的第一个节点，通过它可以遍历整张表，如上图中的左上角的蓝色节点BASE_HEADER

在新增节点时，假设此时我们加入一个值为80的节点，它是通过如下步骤来添加的：

首先，它会将80节点加入level1中的链表中

SkipListMap8.png

根据概率算法，计算处一个level值，这里假设为4，然后根据跳表算法描述，构建新的索引

SkipListMap9.png

将各个索引层次上的节点连接

SkipListMap10.png

其他

目前常用的key-value数据结构有三种：Hash表、红黑树以及SkipList，它们各自有着不同的优缺点（不考虑删除操作）：

Hash表：插入、查找最快，为O(1)，数据的有序化需要显式的排序操作

红黑树：插入、查找为O(logN)，但是常数项较小，如果采用无锁化实现，复杂度很高，一般需要加锁，数据天然有序

SkipList：插入、查找为O(n)，常数项比红黑树要大，底层结构为链表，可无锁实现，数据天然有序