[数据结构与算法]Inversion of Java Interview - Java集合篇

Inversion of Java Interview-Java容器篇

好奇心是驱动人类进步的动力之一

一、Java容器概况

Java容器分为Collection和Map两大类，Collection集合的子接口有Set、List、Queue三种子接口，我们常用的是Set、List和Map接口，注意Map不是Collection的子接口。此图很重要：

Collection接口继承了Iterable接口，Iterable接口提供迭代遍历集合的方法

上图很重要！下面都会应用到，使用图构建知识框架会快很多。

2.容器框架底层数据结构

Collection

List接口

• Arraylist： Object数组
• Vector： Object数组
• LinkedList： 双向循环链表

Set接口

• HashSet(无序且唯一)：基于HashMap 实现；
• LinkedHashSet： LinkedHashSet 继承于 HashSet，内部是基于 LinkedHashMap 实现；
• TreeSet（有序且唯一)： 红黑树(自平衡的排序二叉树)

Map

• HashMap： JDK1.8之前HashMap由数组+链表组成的，JDK1.8以后将链表转化为红黑树；
• LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• HashTable： 数组+链表组成的，数组是 HashTable 的主体，链表则是主要为了解决哈希冲突而存在的。
• TreeMap： 红黑树（自平衡的排序二叉树）。

3.线程安全的集合类

1. Vector：比Arraylist多了个同步化机制（线程安全），效率较低不建议使用。在web应用中优先考虑效率。
2. Statck：堆栈类，先进后出。
3. Hashtable：比Hashmap多了个线程安全。
4. Enumeration：枚举，相当于迭代器。

4.快速失败(fail-fast)和安全失败(fail-fast)

安全失败和快速失败都是对迭代器(Iterator)而言的。我们经常说xx是快速失败的迭代器。

快速失败(fail-fast)

在使用迭代器(Iterator)对集合对象进行遍历的时候，如果A线程对集合进行遍历，正好B线程对集合进行修改（增加、删除、修改），则A线程会尽量抛出ConcurrentModificationException异常。(为什么是尽量而不是一定，请看下面分析)

原理：迭代器在遍历集合时直接访问集合中的数据，在遍历过程中会借助于modCount变量。集合内容被修改的同时modCount也随着变化。每当迭代器使用next()遍历下一个元素之前，都会先检查modCount变量是否为expectedModCount值，是就继续遍历，不是就抛出ConcurrentModificationException异常，终止遍历。查看ArrayList内部类Itr源码，在next()方法执行时，会执行checkForComodification()方法：

@SuppressWarnings("unchecked")
public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

注意

1. 异常抛出条件判断 modCount != expectedmodCount 条件，如果modCount经过多次修改后刚好变为expectedmodCount，那么就不会抛出异常。所以是尽量抛出异常。且不能依赖此异常是否抛出来判断此集合能不能支持并发操作的编程，这种机制一般仅用于检测并发bug。
2. 在单线程和多线程下都有可能出现快速失败。
3. 解决快速失败有两种方法：
   • 单线程下调用迭代器的remove()方法，并不会修改modCount，迭代器的remove()方法只能删除当前遍历的元素，并不会影响之后数据的遍历；
   • 使用Java并发包(java.util.concurrent)中的类来代替ArrayList和HashMap。

安全失败(fail-fast)

采用安全失败的集合容器，在遍历时先复制原有集合内容，在拷贝的集合上进行遍历。避免了ConcurrentModificationException。

缺点：迭代器遍历的是一开始拷贝的数据，在遍历期间原集合数据修改迭代器是不知道的。Java.util.concurrent包下的容器都是采用安全失败机制。

5.怎么确保一个集合不能被修改

可以使用Collections.unmodifiableCollection(Collection c)方法来创建一个只读集合，此时改变集合的任何操作都会抛出UnsupportedOperationException异常

Collection<String> clist = Collections. unmodifiableCollection(new ArrayList<>());
clist. add("1"); // 运行时此行报错UnsupportedOperationException

6.Collection和Collections区别

Collection是集合类的上层接口，包含了集合的基本操作。

Collections是一个包装类，服务于Collection框架，他提供了一系列的静态方法实现对各种集合的搜索、排序、线程安全化等操作，另外此类不能实例化。

7.什么是内部排序和外部排序

根本区别是待排序的数据量不同。内部排序处理小数据量，外部排序处理大数据量。

7.1 内部排序

待排序数据量不是很大，直接数据放在计算机内存中进行排序的过程。可以依靠插入排序、快速排序、选择排序、归并排序、基数排序等实现。

7.2 外部排序

待排序数据量很大，以致于内存不能一次性容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程。实现过程是基于两个独立的阶段完成（IO+内部排序）：

1. 按照可用内存的大小把待排序文件分为若干段；
2. 把分好后的数据依次读取内存，并使用有效的内部排序方法对它们进行排序；
3. 将排序好的有序子文件出现写入外存，把这些有序子文件称为归并段；
4. 然后对这些归并段进行逐趟归并，直到整个文件有序为止。

7.3 衡量效率

内部排序以比较次数，即时间复杂度评判；外部排序以IO次数，即读写外存的次数评判。

8.Comparable和Comparator两种比较器的区别

8.1 Comparable接口

Comparable可以认为是一个内部比较器，对实现它的每个类的对象进行整体排序，实现Comparable接口的类可以自己和自己比较，就比如一个实现了Comparable接口的类，可以通过Collections.sort()或Arrays.sort()进行排序。

需要和另一个也实现了Comparable接口的类比较，就需要实现compareTo()方法，此方法也称为自然比较方法。compareTo()返回int类型的值，返回的int有三种情况：

1. 正整数：比较者大于被比较者；
2. 0：比较者等于被比较者；
3. 负整数：比较者小于被比较者。

a.compareTo(b)，a是比较者，b是被比较者

8.2Comparator接口

Comparator可以认为是一个外部比较器，对于本身不支持排序（无法实现Comarable接口）的类，有排序需求就可以使用Comparator。建立一个该类的比较器来进行排序，这个比较器只需要实现Comparator接口即可。下面写一个实例帮助理解：

publci class CustomComparator implements Comparator<T> {//T为需要比较的类
    @Override
    public int compare(T o1, T o2) {//和Comparable的compareTo()方法类似
        return 0;
    }
}

Comparator和Comparable接口能做的事不仅仅是排序，排序只是在它支持比较的基础之上衍生出来的

8.3 Comarabel和Comparator接口区别

Comparable接口将比较代码嵌入自身类中，而Comparator在一个独立的类中实现比较。

9.遍历Map集合的方法

遍历Map有四种方式，下面就来介绍一下：

map：存储由key-value的Map集合

9.1 通过Map.keySet获得key的集合

得到key的集合后，通过逐个key获取value

// map.keySet()返回map集合中的key的set集合
for (Object k : map.keySet()) {
    //map.keySet()返回的是所有key的值
    Object v = map.get(k);//得到每个key多对用value的值
    System.out.println(k + ":" + v);
}

9.2 通过Map.entrySet配合iterator()遍历

之后就是由iterator遍历key和value

Iterator<Map.Entry<Object, Object>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<Integer, String> entry = it.next();
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

简单说明一下

1. Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示的是Map中的一个实体（key-value）。接口中有我们常用的getKey(),getValue方法。
2. map.keySet()方法返回值是Map中key值的集合；
3. map.entrySet()的返回值是一个Set集合，此集合的类型为Map.Entry<K,V>。

还有迭代器Iterator，这个就不介绍了。

9.3 通过Map.entrySet遍历key和value（推荐使用）

map.entrySet()返回此映射中包含的映射关系的 Set视图。遍历即可

// 第三种：推荐，尤其是容量大时
for (Map.Entry<Object, Object> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

9.4 通过Map.values()遍历所有的value

map.values()返回的是vaule的Collection集合，遍历即可得到map中的各个value，缺点是不能遍历到key

//不能遍历到key
for (Object v : map.values()) {
    System.out.println("value:" + v);
}

二、Collection接口

Collection表示一组对象，这些对象也称为Collection的元素。有一些Collection允许有重复的元素，而有一些则不允许，又有一些Collection是有序的，而有一些是无序的。

1.迭代器Iterator和ListIterator

1.1 Iterator

Iterator接口提供遍历任何Collection的接口，我们可以从一个Collection中使用迭代器方法(iterator())来获取迭代器实例。迭代器Iterator取代了Java集合框架中的Enumeration，迭代器允许调用者在迭代过程中删除元素。

说明：迭代器一开始默认指向的是初始数据指针的前一个指针，也就是空位置

对API进行一些解释

1. hashNext()：判断下一个位置是否有元素，有就返回true，否则false；
2. next()：指针向下移动一次，并且返回移动后的数据；
3. remove()：删除当前指针上的数据，注意迭代器中的数据被删除了的同时，集合本身的数据也被删除，使用迭代器删除集合数据就避免了快速失败的ConcurrentModificationException。

1. 所以必须先移动指针后移（next()）才能执行一次remove()方法。同时hashNext()、next()和remove()方法配合可以实现遍历的同时删除数据；
2. Iterator.remove()是唯一安全的方式在迭代过程中修改集合。

使用示例

ArrayList<Integer> list = new ArrayList();
for (int i = 0; i < 5; i++) list.add(i);//添加数据
//1.获取Iterator实例
Iterator<Integer> iterator = list.iterator();//Iterator没有实例化方法
//2.hasNext()
while (iterator.hasNext()){//判断是否有下一个数据
    //3.next()
    Integer elem = iterator.next();//移动指针，返回数据
    System.out.print(elem + " ");
    iterator.remove();//删除数据
}

System.out.println("--------------");
//遍历list集合，看数据是否删除成功
for (Integer elem:list)
    System.out.println(elem);

输出如下数据，很显然list中的数据以及被输出掉了，并且是线程安全的！

0 1 2 3 4 --------------

迭代器Iterator不能直接遍历Map，下面详细的提到如何遍历Map集合

1.2 ListIterator

ListIterator继承于Iterator接口，只能用于各种List类型的访问操作。可以调用一个listIterator()产生一个指向List开始处的ListIterator，还可以调用ListIterator(index)创建一个一开始指向列表索引为index的元素处的ListIterator。

看API可以双向移动，另外可通过set()方法替换当前指针的值，可通过add(E e)方法在当前指针处插入数据，并且当前指针指向刚插入的数据，后序的指针索引序号后移。

1.3 Iterator和ListIterator区别

1. Iterator是支持所有 Collection(List,Set,Queue)的API，ListIterator仅支持List。它们主要区别：
2. ListIterator在Iterator基础上增加add()、set()方法，都可删除对象；
3. ListIterator和Iterator都可以实现顺序向后遍历，但是只有ListIterator可以实现逆向遍历。
4. ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。

刚刚看完迭代器，下面就在场景下分析一下

2.遍历一个List有几种方式，原理，Java中List遍历的最佳选择

遍历集合的方式有三种

1. for循环：在集合外部维护一个计数器，然后依次读取每一个位置的元素。for(int i=0;i<n;i++)中的i就是计数器。

2. 迭代器(Iterator/ListIter)：Java面向对象的一种设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口。

3. foreach：foreach内部采用Iterator的方式实现，使用时不需要显式声明Iterator或计数器，代码简洁，仅能遍历数据。

   foreach对数组相当于for，对于集合，就是使用Iterator接口实现

关于遍历List的最佳选择，这就要涉及到Java Collection框架的RandomAccess接口，它是用来标记List实现是否支持随机存取的（根据底层数据结构可知是否会实现RandomAccess接口，数组就支持随机存储，链表不支持）。

ArrayList、Vector底层数组，LinkedList底层链表，等等 … …

推荐做法是：支持RandomAccess接口的集合可用for循环遍历，否则建议使用Iterator和foreach。

3.List接口和Set接口联系和区别？

List使用toArray()方法可以转换为数组，使用Arrays.asList(arry)可把数组转换为List

1. List和Set都是Collection集合的子类，List保留插入顺序，Set不保留插入顺序；
2. List可以重复元素，Set不能重复元素(插入重复项会替换旧值)；
3. List可以存储多个null值，Set只能存储一个null值(不能重复的原因)；
4. List获取指定元素时，可以使用Iterator取出所有元素在逐一遍历，或直接使用get(int index)方法直接获取指定下标元素；而Set只能使用Iterator接口取得所有元素，在逐一遍历。
5. List接口包含一个遗留类Vector（Stack继承自此），Set接口没有任何遗留类；

4.ArrayList的优缺点

ArrayList底层数据结构为数组，查询快，增删慢

ArrayList优点

• 支持随机访问，实现了RandomAccess接口，查找时非常快；
• ArrayList在添加一个元素时非常快；
• 可自动扩容，且每次扩容1.5倍；

ArrayList的elementData要加上transient关键字，private transient Object[] elementData;，是因为ArrayList支持序列化操作，而加上此关键字就是为了使得elementData不被序列化。实现每次序列化已存入的元素，这样加快了序列化速度，还节省了空间。

ArrayList缺点

• 插入和删除效率较低（因为插入或删除后需要移动元素，浪费性能）；
• 根据内容查找元素的效率较低；

扩展

ArrayList和Array的区别

1. Array可以存储基本数据类型和对象，ArrayList只能存储对象；
2. Array固定大小，ArrayList自动扩容；
3. ArrayList内置方法多。

实现Array和List之间的转换

1. Array转List：Arrays.asList(arr)；
2. List转Array：List 的中的 toArray()。

5.ArrayList和LinkedList

两者性能对比测试戳我！！

5.1 ArrayList

ArrayList底层基于动态数组结构，根据下标随机访问数组元素的效率高（查找快），向尾部添加元素的效率高，删除数据和向数组中间添加数据效率低，因为需要移动数组。例如最坏的情况：删除第一个数组元素，n-1个的元素都得向前移1位。

当ArrayList中的元素超过容量的时候，ArrayList会进行扩容（默认值为10，JDK1.8扩容1.5倍），ArrayList中最大的数组容量是Integer.MAX_VALUE-8，空出的8位的作用：

1. 存储Headerwords（头信息，数组大小信息和指向类信息等）；
2. 避免一些机器内存溢出，减少出错几率；
3. 最大还是能支持到Integer.MAX_VALUE(当Integer.MAX_VALUE-8无法满足需求时)

(源码)无参构造后得到的对象，调用add()方法，return的是true，无论失败与否是都是true。

ArrayList线程不安全，需要线程安全建议使用Vector类。

5.2 LinkedList

LinkedList基于双向链表，增删快，查找慢（需要对链表进行遍历），操作方法和ArrayList差不多。LinkedList还实现了Deque接口，拥有push()和pop()等方法（可参考Deque接口方法），可以模拟栈、队列等。功能强大。

使用双向链表的优点（对比单向链表）：

1. 单向链表只能单向操作，双向链表可以双向操作；
2. 单向链表自我删除时需要依靠辅助节点（总是需要找到待删除节点的前一个节点），而双向链表可以自我删除；

在不考虑空间浪费的情况下，双向链表更加通用

5.3 两者区别

1. 数据结构实现：ArrayList底层是动态数组，LinkedList底层是双向链表；
2. 随机访问效率：ArrayList比LinkedList在随机访问时效率高，因为ArrayList支持随机访问，LinkedList得从链表首部逐步移动指针；
3. 增删效率：在非尾部的增删操作，LinkedList比ArrayList效率高，因为增删后ArrayList需要移动数据；
4. 内存空间占用：LinkedList底层是双向链表，比ArrayList更占内存。ArrayList的空间浪费主要体现在数据结尾会预留一定的容量空间（数组刚好充满就没有空间浪费），而LinkedList的空间花费主要体现在它的每一个元素节点都要存储数据之外的两个指针（一个指向前一个，一个指向后一个）；
5. 线程安全：两种都是线程不安全的。

综合来说，需要频繁读取集合元素时，推荐使用ArrayList，在插入和删除操作较多时，推荐使用LinkedList。

6.ArrayList和Vector的区别

Vector实现了同步的ArrayList，Stack类继承于Vector。另外查找效率：ArrayList > Vector > LinkedList。

ArrayList和Vector都实现(implements)了List接口，它们都保证了数据的插入顺序；

1. 线程安全：Verctor实现了RandomAccess接口，它使用Synchronized实现了线程安全，而ArrayList非线程安全；Vector类的所有方法都是同步的；
2. 性能：ArrayList在性能方面优于Vector；
3. 扩容：ArrayList和Vector都基于Object数组，ArrayList扩容1.5倍数，Vector扩容2倍；

如果非要在多线程场景下使用ArrayList，那么可以使用Collections类中的静态方法synchronizedList(List)转换成线程安全的容器。

7.HashSet原理

HashSet底层实现基于HashMap，HashSet的值存放在HashMap的key上，HashMap的value统一设置为PRESENT = new Object()，所以HashSet实现实现简单，HashSet封装了一些列的HashMap方法，依靠HashMap的key来存储元素值，HashSet不能存储重复值（会覆盖）。

public HashSet() {//无参构造方法，其他有参构造方法直接返回一个新创建的HashMap
    map = new HashMap<>();
}

HashSet判断重复元素通过 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 。这里的hash是对象的hashCode()，默认是通过地址计算的hash值。

所以HashSet的初始容量也为16，负载因子也为0.75。

存储数据使用推荐使用HashSet而不推荐使用数组，因为数组长度固定，无法自由增加长度，而HashSet可以扩容，并且在查找某个元素时性能由于数组，因为HashSet通过计算数据的hash值，直接通过hash值获取到下标是比数组遍历查询快得多的。

另外，使用HashSet存储可变对象时，必须十分小心，如果修改HashSet集合中的对象，有可能导致该对象与集合中的其他对象相等，导致数据访问错乱。

LinkedHashSet

LinkedHashSet是HashSet的子类，它也是根据元素的hash值来决定存储的位置，但同时它使用链表维护元素的次序，这样使得元素看起来是以插入顺序保存，即在遍历LinkedHashSet里的元素时，集合将会按元素的添加顺序来访问集合里的元素。

输出元素顺序总是与添加元素顺序一致，但LinkedHashSet依然是HashSet，它不允许集合重复。

8.HashSet如何检测重复，如何保证数据不重复

HashSet的add()方法会调用HashMap的put()方法，value默认为PRESENT

当HashSet调用add()方法时，会先获取到数据的hash值，之后进行hash值比较，如果hash值相同，调用equals()方法，判断是否存在。下面是HashSet的add()方法部分源码：

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
//HashSet无参构造
public HashSet() {
    map = new HashMap<>();
}
//HashSet的add方法
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

hashCode()和equals()、==和equals()的对比在前面的文章已经讨论过，这里就不再讨论：

https://blog.csdn.net/yeahPeng11/article/details/118460098

9.HashSet和HashMap的比较

HashSet底层实现是HashMap，诸多方法也是直接调用HashMap中的对应方法。而HashSet可通过计算数据的hash值快速定位数据位置，不用如数组一样需要逐个遍历确定某一元素是否存在数组中。

10.TreeSet类

TreeSet是SortedSet接口的实现类（中间还有一个NavigableSet接口），TreeSet可以保证元素处于排序状态，它的内部实现是**红黑树**，默认升序。

红黑树详解：https://blog.csdn.net/yeahPeng11/article/details/118197397

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4vxTtJie-1627738002536)(images/TreeSet.png)]

它内部提供了大连的API。

TreeSet支持两者排序方法：自然排序和定制排序，默认情况下采用自然排序。

10.1 自然排序

TreeSet会调用集合元素的compareTo(Objec obj)方法来比较元素之间的大小关系，然后将集合元素按升序排列，这就是自然排序。需要通过HashSet来存储的实体类就必须使用Comparable接口，该接口里定义了compareTo(Objec obj)方法，该方法返回一个整数值。对于obj1.compareTo(obj2)，返回0表示两个对象相等，正数表示obj1大于obj2，负数表示obj1小于obj2。

1. 重写compareTo(Objec obj)方法是用户自定义的写法，自定义排序写法；
2. 加入HashSet的类必须实现Comarable接口重写compareTo(Objec obj)方法，否则会抛出ClassCastException；
3. 不要修改已经存入集合的实例对象，这将会导致它与其他对象的大小顺序发送改变，但TreeSet不会再次调整已存入的元素的顺序；
4. TreeSet中不要添加一种以上类型的对象，否则TreeSet及易出现错乱；
5. 其实第一个加入TreeSet的数据可以不实现Comarable接口，但是在取出数据的时候仍然会抛出ClassCastException，这并不是一个好选择。

10.2 定制排序

TreeSet的自然排序是根据集合元素的大小，TreeSet将它们以升序排列。如果需要实现定制排序，例如降序排序，则可通过Comparator接口的帮助。该接口里包含一个int compare(T o1,T o2)方法，用于比较o1和o2的大小。由于Comparator是一个函数式接口，因此还可以使用Lambda表达式来代替Comparator子类对象。

TreeSet<Integer> nums = new TreeSet<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1-o2;//升序 默认
        //return o2-o1;//降序
    }
});

使用Lambda表达式来实现（匿名函数）：

TreeSet<Integer> nums = new TreeSet<>((a,b) -> (a-b));//升序 默认
TreeSet<Integer> nums = new TreeSet<>((a,b) -> (b-a));//降序

定制排序的特征和自然排序相同，不建议添加相同的对象。

10.3 HashSet和TreeSet的区别

1. 两者内部都是基于Map集合的类，HashSet基于HashMap，HashSet基于TreeMap。
2. 两者都实现(implements)了Set接口。
3. 两者都不能存储重复的数据（数据重复add方法返回false）。
4. HashSet不保留插入顺序，数据存储载hash表中；TreeSet维持升序(自定义数据类型需要程序员重写CompareTo()方法实现排序)。
5. HashSet由 哈希表 表示，TreeSet由 树结构 实现(红黑树)。
6. HashSet比TreeSet执行得更快（哈希表快于二叉树）。

TreeSet的迭代器是 快速失败的迭代器；

TreeSet存储自定义的数据的是需要实现Comparable接口的compareTo()方法，自定义存储顺序。

11.Queue接口

Queue队列接口，它继承自Collection集合，它有多个子接口，常用的有Deque和BlockingQueue。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-svzfJ5Kv-1627738002537)(images/Queue.png)]

Queue的add()和offer()方法区别

两者都是数据入队，但是add()方法在队列满后会抛出IllegalStateException("Queue full")，而offer()方法不会抛出异常，其实add()方法底层也是offer()方法，且offer()方法线程安全。

public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

Queue的remove()和poll()方法区别

两者都是删除并返回当前元素，它们的区别和add和offer区别类似，remove()方法在队列为空时会抛出NoSuchElementException，而poll()方法在队列为空时不会抛出异常，只会返回删除false。

public E remove() {
    E x = poll();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();//没有此类元素异常
}

12.BlockingQueue是什么

Java.util.concurrent.BlockingQueue是一个队列，继承了Queue接口，在进行检检索或移除一个元素的时候，它会等待一个队列变为非空；当在添加一个元素时，它会等待队列中的可用空间。

BlockingQueue接口是Java集合框架的一部分，主要用于实现生产者-消费者模式，我们不用担心生产者无可用空间或消费者无可消费对象，因为它都在BolckingQueue的实现类中被处理了。BlockingQueue的实现有：ArrayBlockingQueue、LinkedBlockingQueue和PriorityBlockingQueue等。

13.PriorityQueue是什么

对数据结构中的大小顶堆不清楚的请移步：https://blog.csdn.net/yeahPeng11/article/details/118309593

java.util.PriorityQueue是优先队列，用数组存储的顶堆（可以是大/小顶堆）。它也拥有队列的API，具体相关的描述这里就不在提及。

• 通过iterator()方法获取到的迭代器，通过迭代器获取的数据它并不是有顺序的数据，而是数组存储的数据结构（顶堆）。如果对顶堆有所了解，就很好理解这一点。
• PriorityQueue未实现同步（线程安全的优先级队列：PriorityBlockingQueue）。队列会自增。

三、Map(Mapping映射)

注意Map和Collection是同级的，不要以为List和Map同级

1.哈希表概述

1. 哈希表又称为散列表。

2. 哈希表的原理就是构建一个确定的映射，它能把关键字映射到一个唯一的存储位置。这种映射应该是我们可以进行计算的。已知关键字，我们能根据hash算法算出其地址；反之，已知地址，我们可以检索到对应的关键字。一旦建立起这种关系，那么给定关键字，我就能直接利用这个映射(即所谓的哈希函数)直接算出其地址并寻址。这可大大缩减确定关键字存储位置所花的时间。

3. 哈希表采用对象数组加链表（链表放在数组里）存储，当某一个数组（哈希桶）下的链表的长度大于8时，链表会转化为红黑二叉树；当哈希桶中的数据量减少到6时会由红黑树转换为链表。

   对象数组是指 存储对象的数组

4. 默认初始桶的数量16（可以指定），默认散列因子0.75(可以指定），数据存储达到散列因子（75%的桶存储得有值）后哈希表进行扩容2倍。后将原先的数据存储进去，这个过程称为重散列(rehashing)。

2.解决hash冲突的方式

哈希冲突：两个不同的输入值，根据同一散列函数计算出相同的散列值的情况。

2.1 拉链法

在Java语言中，保持数据有两种比较简单的数据结构 —— 数组和链表，数组的特点是寻址容易，插入和删除困难；链表的特点是寻址困难，但插入和删除容易。所以这里就采用拉链法将数组和链表组合在一起，发挥各自的优势以解决hash冲突。

每个位桶在实现的时候，我们采用链表（jdk1.8之后采用链表+红黑树）的数据结构来存取发生冲突的数据。一般是双向链表。场景如下：

• 插入：插入时发生哈希冲突，输入的数据映射到对应的位桶上，先检查是否存在相同的键（使用equals()方法）,再判断是否存储或覆盖。

• 删除：删除时发生哈希冲突，使用equals()去检索位桶上与之匹配的数据，找到以后执行删除操作。

• 查询：查找时发生哈希冲突，使用equals()去检索位桶上与之匹配的数据，找到以后返回该数据。

  以上插入、删除、查找的时间复杂度均为O(1)。下面的图片中的data表示：key-value

拉链法的优点

1. 拉链法处理冲突简单，且无堆积现象，平均查找长度较短；

2. 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于建表前无法确定表长的情况；

3. 开放定址法为减少冲突，要求装载因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；

   装载因子 = 数据量/位桶数

4. 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

拉链法的缺点

指针需要额外的空间，在节点规模较小时，开发地址法更加节省空间。

2.2 开放地址法

相较于开发地址法，拉链发对于数据量较大的情况下更优（性能优）；

相较于拉链法，开放地址法对于数据量较小的情况下更优（内存优）。

开放地址法又称为再哈希法、再散列法。所有的数据都是存放在哈希表中的，不像拉链法会把数据存放在链表中。开发地址法的位桶不需要任何的链表来实现，此哈希表的装载因子不会超过1。

原理

是在插入数据的时候，使用哈希函数来判断是否产生哈希冲突，发生哈希冲突就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若还是发生哈希冲突，就继续往下寻找，直到找到一个空的地址为止。几种常见的探查序列法：

• 线性探查：d =1，2，3，…,m-1；特点是冲突发生时，顺序查找表中下一个单元，直到找出一个空单元为止。

• 二次探查：d =1，-1，2，-2,…,k,-k(k<=m/2)；特点是冲突发生时，在表的左右进行跳跃式探测，比较灵活。

• 伪随机探查：d = 伪随机数；具体实现时，应建立一个伪随机数发生器，生成一个伪随机序列，并给定一个随机数做起点，每次去加上这个伪随机数就可以。

  伪随机数不是真正的随机数，而是通过某种算法实现的，如i=(i+p)%m（m是位桶数量）计数i的伪随机数

缺点： 每次冲突都需要再次计算hash值，时间成本增加。

2.3 HashMap解决hash冲突

概括来说

1. 使用拉链法（又称散列法）来链接拥有相同的hash值的数据；
2. 使用2次扰动函数（hash()函数）来降低哈希冲突的概率，使得数据分布更平均；一次位运算，一次异或运算。
3. 引入红黑树进一步降低遍历的时间复杂度，遍历更快。

详细分析

我们都知道hashmap在JDK1.8开始采用的数据结构是对象数组+链表+红黑树的，这三者组合使得hashmap在寻址、插入和删除都变得容易起来。而在此数据结构基础之上，可以使用拉链法的方式解决hash冲突，这样就可以将拥有相同哈希值的对象组织成一个链表或红黑树放在hash值所所对应的bukect下。

但是相比于hashcode()返回的int类型，我们HashMap初始的容量大小 DEFAULT_INITIAL_CAPACITY = 1 << 4(16)很小，所以我们如果只是单纯的对hashcode取余获取bucket这将会大大增加哈希碰撞的概率，这里还要对hashCode作一定的优化。

我们能够想到如果单单的对hashcode进行取余，对bucket取决定性作用的只有hashcode的低位，高位没有任何影响。现在让hashcode的高位也参与运算，进一步降低hash冲突的概率，这种操作称为扰动，在JDK1.8中的hash()函数如下：

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

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

所谓扰动：对hash值的产生变化的操作

JDK1.8新增红黑树。通过链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；

3.HashMap实现原理

HashMap使用拉链法解决hash冲突

HashMap是基于哈希表的Map接口的非同步实现。HashMap是一个存储键值对(Key-Value)的集合，这些键值对存储在许多个数组中(链表数组Node<K,V>[])，它不保证插入的映射顺序，且在扩容或链表转换为红黑树时不保证先前存储的顺序。

HashMap基于Hash算法实现

1. 每次数据操作都是通过计算key的hashCode，再通过hash算法得到对应的数组下标；
2. 存储时，如果出现hash值相同的key，equals()判断两key是否冲突，冲突就覆盖旧数据，不冲突就将当前key-value放入链表数组；
3. 获取/删除时，找到hash值对应的下标，使用equals()方法找到对应的key，将value返回/删除。

这里需要注意的是，JDK1.8把HashMap的实现做了优化，当链表的节点超过8个就转换为红黑树，从O(n)->O(logn)，当链表已经是红黑树时，链表节点数下降到6个时就会转换为链表。

4.HashMap在JDK1.7和JDK1.8的主要区别（HashMap底层）

众所周知，HashMap采用数组+链表存储数据

JDK1.8之前采用拉链法：数组+链表；JDK1.8开始：数组+链表+红黑树，链表长度大于阈值（默认为8），即将链表转化为红黑树，小于6红黑树转化为链表。JDK1.8主要优化：

1. resize()扩容优化；
2. 引入红黑树，避免单条链表过长影响性能；
3. 解决多线程的死循环问题，但是仍然是非线程安全的。

5.HashMap的put()方法具体流程

调用put()时首先计算key的hash值，调用hash()，而hash()实现代码为(h = key.hashCode()) ^ (h >>> 16)，此hash()方法计算的hash值由高位和低位一起决定，减少hash冲突；

按hash()函数注释：bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash，不做hash处理的话就只有几个低位bit生效，为减小冲突采用高低位异或来简单处理减少hash冲突，且JDK1.8采用时间复杂度为O(logn)的红黑树结构来提升冲突性能。

1. 判断Node<K,V>[]数组键值对是否为null，否则执行resize()扩容（初始化）；

2. 根据key计算数组索引值i，如果table[i]==null，直接添加新节点，转向序号7，如果table[i]不为空，转向序号3；

3. 判断table[i]的首个元素是否等于key，如果相同直接覆盖value，否则转向序号4；

   这里的等指的是hashCode与equals()判断之后的相等

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

5. 遍历table[i]，判断链表key是否存在，存在就覆盖value，否则插入新节点，转向序号6

6. 判断链表长度是否大于8，是就把链表转化为红黑树，转向序号7；

7. 插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过就进行扩容resize()。

源码：

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;
    // 步骤1：tab为空则创建 
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤2：计算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;
        // 步骤3：节点key存在，直接覆盖value 
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
        // 步骤4：判断该链为红黑树 
        // hash值不相等，即key不相等；为红黑树结点
        // 如果当前元素类型为TreeNode，表示为红黑树，putTreeVal返回待存放的node, e可能为null
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤5：该链为链表 
        // 为链表结点
        else {
            // 在链表最末插入结点
            for (int binCount = 0; ; ++binCount) {
                // 到达链表的尾部
                //判断该链表尾部指针是不是空的
                if ((e = p.next) == null) {
                    // 在尾部插入新结点
                    p.next = newNode(hash, key, value, null);
                    //判断链表的长度是否达到转化红黑树的临界值，临界值为8
                    if (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;
}

6.HashMap扩容操作的样实现

HashMap的扩容方法是resize()，它有以下约定：

1. 在JDK1.8中，resize()方法是在HashMap中的键值对大于阈值时或初始化时被调用，进行扩容操作；
2. 每次扩容2倍；
3. 扩容后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置（提高了扩容的效率）。

在上面的putVal()方法中，调用了两次resize()方法。resize()方法表示在进行初始化时会把容量设置为16；或者当数组的实际非空量大于其临界值（也就是散列因子*数组大小，第一次为16*0.75=12），这个时候在扩容的同时也会伴随桶上面的元素重新分配，这就是JDK1.8中优于的一点。在JDK1.7中，扩容之后需要去重新计算其每个key的hash值，再重新分配位置，但在JDK1.8中，则是根据在同一个桶中的位置进行判断(e.hash & oldCap) == 0，该元素的位置在新容器中要么是原位置坐标，要么是原位置+扩容量坐标。

当用户指定HashMap容量的时候，它会检查指定的容量是否是2的幂方（可使用(n & (n-1)) == 0判断），如果不是会自动扩容为2的幂方。为的就是在扩容的时候不用重复的计算hashCode值。

resize()的源码：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;//oldTab指向hash桶数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空
        if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值
            threshold = Integer.MAX_VALUE;
            return oldTab;//返回
        }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold
    }
    // 旧的容量为0，但threshold大于零，代表有参构造有cap传入，threshold已经被初始化成最小2的n次幂
    // 直接将该值赋给新的容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 无参构造创建的map，给出默认容量和threshold 16, 16*0.75
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新的threshold = 新的cap * 0.75
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 计算出新的数组长度后赋给当前成员变量table
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
    table = newTab;//将新数组的值复制给旧的hash桶数组
    // 如果原先的数组没有初始化，那么resize的初始化工作到此结束，否则进入扩容元素重排逻辑，使其均匀的分散
    if (oldTab != null) {
        // 遍历新数组的所有桶下标
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 旧数组的桶下标赋给临时变量e，并且解除旧数组中的引用，否则就数组无法被GC回收
                oldTab[j] = null;
                // 如果e.next==null，代表桶中就一个元素，不存在链表或者红黑树
                if (e.next == null)
                    // 用同样的hash映射算法把该元素加入新的数组
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果e是TreeNode并且e.next!=null，那么处理树中元素的重排
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // e是链表的头并且e.next!=null，那么处理链表中元素重排
                else { // preserve order
                    // loHead,loTail 代表扩容后不用变换下标，见注1
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead,hiTail 代表扩容后变换下标，见注1
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表
                    do {             
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                // 初始化head指向链表当前元素e，e不一定是链表的第一个元素，初始化后loHead
                                // 代表下标保持不变的链表的头元素
                                loHead = e;
                            else                                
                                // loTail.next指向当前e
                                loTail.next = e;
                            // loTail指向当前的元素e
                            // 初始化后，loTail和loHead指向相同的内存，所以当loTail.next指向下一个元素时，
                            // 底层数组中的元素的next引用也相应发生变化，造成lowHead.next.next.....
                            // 跟随loTail同步，使得lowHead可以链接到所有属于该链表的元素。
                            loTail = e;                           
                        }
                        else {
                            if (hiTail == null)
                                // 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 遍历结束, 将tail指向null，并把链表头放入新数组的相应下标，形成新的映射。
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

7.Map的对key的类型的要求

可以使用任何类作为Map的key，但是一定考虑一下几点：

1. 如果类重写了equals()方法，也应该重写HashCode()方法；
2. 类的所有实例需要遵循与equals()和HashCode()相关的规定；
3. 用于自定义的Key类最好是不可变的类，这样HashCode()值可以被缓存起来，hascode和equals()的结果在未来不会改变，解决可变相关的问题。

推荐使用String、Integer这样的wrapper包装类作为Key，因为包装类都是final类型，保证不可变性，且内部重写了equals()和HashCode()等方法（不重写这两个方法的类默认使用Object类的equals()和hashCode()方法），很少出现hash值计算错误情况。

默认使用Object()方法的HashCode()方法，它就是通过数据的内存地址获取到的hash值，随着内存的改变，再次重新获取hash自然也会改变，那么我存储的是没有重写HashCode()方法的类，那么在发生内存地址变化以后（比如JVM执行GC操作）对应的hash值是否也会变化？

答案是不会，不重写HashCode()方法的类，会在第一次调用HashCode()方法之后把该数据对应的hash值存储在header中，之后再调用该方法时不会再根据内存地址获取hash，而是直接读取到存储到header中的hash值，实现不曾改变hash的效果。

当使用自定义的对象作为键时，只要它遵循了equals()和hashCode()方法的定义规则，并且当对象插入到Map中后不在改变，就可以使用自定义的对象。否则很难在找到之前的数据。

8.HashMap为什么不直接使用HashCode()处理后的哈希值作为bucket位

HashCode()方法内容根据不同的类而不同，但是它们都返回int类型整数，范围是-2^31 ~ 2^31-1，而HashMap的容量范围是16 ~ 2^30，这hashcode范围就太大了，而map位置只有那么多，导致通过HashCode()计算出的哈希值可能不在数组范围内，进而无法匹配存储位置。

那怎么解决呢？

1. HashMap自己实现了hash()方法，通过两次干扰使得hash值由高低共同决定，降低哈希碰撞概率也是的数据分布更平均。

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

2. 在保证数组长度为2的幂次方的时候，使用hash()运算之后得到hash值h与数组长度进行：h&(length - 1)运算，使得取余操作效率极高。这也是就为什么hashmap数组长度必须是2的幂次方。

   仅有在数组长度length为2的幂次方时，h&(length-1) == h%length 才为真。

9.HashMap和HashTable的区别

两者都实现了Map接口，两者主要区别有：线程安全，和效率。

HashMap几乎等价于HashTable，除了HashMap是非同步、可以接收null（HashMap中的key和value都允许为null，而HashTable不行）

1. 两者都实现实现了Serializable和Cloneable接口，都支持可序列化和能被克隆。
2. 底层数据结构：HashTable底层是数组+链表；JDK1.8开始HashMap使用数值+链表+红黑树存储数据。
3. 线程安全：HashMap是非线程安全的，HashTable是线程安全的，HashTable内部方法基本都经过synchronized修饰。JDK1.5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable扩展性更好。
4. 效率：HashTable保证线程安全，在并发情况下，HashMap比HashTable效率高（HashTable基本被淘汰）。
5. 对Null key和Null value的支持：HashMap中能存储一个null的key，和多个null的value；HashTable的key和value都不能为null。
6. 扩容和初始化容量：HashTable默认11，扩容2*n+1；HashMap默认值16，扩容2*n。如果指定初始化容量，HashTable会直接采用该初始化容量，而HashMap的容量必须满足2的幂次，不是就补到2的幂次。
7. 计算哈希值：HashTable是调用hashCode()得到最终的hash值；HashMap通过hashCode()得到一个hash值，再将hash值右移16位相 异或(^)，即 (h = key.hashCode()) ^ (h >>> 16) 得到新的hash值。
8. 计算索引值：HashTable得到hash后采用取余(%)方式计算索引值；HashMap得到hash后采用位运算(&)，即**h & (len - 1)**，效率高于%，但是得到的结果是一样的。
9. 迭代器：HashMap的迭代器(Iterator)是快速失败迭代器，HashTable的迭代器(enumerator)的安全失败迭代器。所以当其他线程改变了HashMap的结构，可能会抛出ConcurrentModificationException异常。
10. 推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。

10.ConcurrentHashMap的底层实现

JDK1.8之前采用Segment数组+HashEntry的方式实现，具体的就不看了，现在基本用不到。从JDK1.8开始，就摒弃了Segment臃肿的设计，使用Node + CAS + synchronzed来保证并发安全进行实现。synchronzed只锁住了当前链表或红黑树的头节点，这样只要没有hash冲突，就不会产生并发，效率高。结构：

CSA：Compare and Swap，比较和替换。这种机制中使用了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。更新一个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为B。

11.ConcurrentHashMap和HashTable的区别

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

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

底层数据结构：JDK1.8开始ConcurrentHashMap采用和HashMap一样的数据结构，数组+链表/红黑树；HashTable采用**数组+链表**（与JDK1.8之前的HashMap数据结构一致）。

实现线程安全的方式：ConcurrentHashMap在JDK1.8开并发控制使用synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap；HashTable是使用synchronized同一把锁来保证线程安全，效率非常低下，同一时刻，只能一个线程操作数据（一个线程在put，另一个线程get也不行）。

两者对比图：

HashTable：

ConcurrentHashMap JDK1.8：

ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步，HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的 分段锁 ，效率比较高（只要操作的不是同一个哈希桶，就不用排队。当操作的是同一个哈希桶，就得排队执行）。