【面试】Java 集合

1、常见的集合有哪些

Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection 接口，主要用于存放单一元素，另一个是 Map 接口，主要用于存放键值对。对于 Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。Java 集合框架如下图所示：

2、说说 List、Set、Queue、Map 四者的区别

• List：存储的元素是有序的、可重复的。
• Set：存储的元素是无序的、不可重复的。
• Queue：按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
• Map：使用键值对存储，保存键值对映射，映射关系可以一对一、多对一。

3、Collection 和 Collections 有什么区别

首先说下 collection，collection 它是一个接口，collection 接口的意义是为各种具体的集合提供统一的操作方式，它继承 Iterable 接口，Iterable 接口中有一个最关键的方法， Iterator iterator()方法迭代器，可以迭代集合中的元素。
Collections 是操作集合的工具类，其中最出名的就是 Collections.sort(list) 方法进行排序，使用此方法排序集合元素类型必须实现Comparable接口重写compareTo()方法，否则无法实现排序。

4、Comparable 和 Comparator 的区别

对集合排序最常见的就是 Collections.sort(arrayList) 方法，但是用这个方法排序，arrayList这个集合的元素类型必须实现 Comparable 接口并实现其中的 compareTo 方法并写排序规则才能完成排序。

或者对集合排序也可使使用 sort 的一个重载方法 sort(List list, Comparator<? super T> c) 来实现排序，就是第一个参数为 arrayList 这个集合也不用再去实现 Comparable 接口了，而是在第二个参数写 Comparator 的实现 compare 方法，例如

 Collections.sort(arrayList, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});

5、ArrayList 和 LinkedList 的区别是什么

• 底层数据结构： ArrayList 底层使用的是 Object 数组，LinkedList 底层使用的是 双向链表 数据结构。

• 随机访问性能：ArrayList基于数组，所以它可以根据下标查找，支持随机访问，当然，它也实现了RandmoAccess 接口，这个接口只是用来标识是否支持随机访问。LinkedList基于链表，所以它没法根据序号直接获取元素，它没有实现 RandmoAccess 接口，标记不支持随机访问。
• 插入和删除是否受元素性能：LinkedList 的随机访问集合元素时性能较差，但在插入，删除操作是更快的。因为 LinkedList 不像 ArrayList 一样，不需要改变数组的大小，不需要在数组装满的时候要将所有的数据重新装入一个新的数组，对于插入和删除操作，LinkedList 优于 ArrayList。
• 内存空间占用：LinkedList 需要更多的内存，因为 ArrayList 的每个索引的位置是实际的数据，而 LinkedList 中的每个节点中存储的是实际的数据和前后节点的位置。

6、ArrayList 和 Vector 的区别是什么

• Vector 的方法都是同步的，线程安全；ArrayList 非线程安全，但性能比 Vector 好。
• Vector 扩容默认扩容2倍，ArrayList 只增加1.5倍。

7、ArrayList 和 Vector 的扩容机制

ArrayList 是基于数组的集合，数组的容量是在定义的时候确定的，如果数组满了，再插入，就会数组溢出。所以在插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容

ArrayList 的扩容是创建一个1.5倍的新数组，然后把原数组的值拷贝过去。

底层代码：

ArrayList无参构造

// Object类型的数组 elmentData []
transient Object[] elementData;
// {}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ArrayList无参构造方法
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

底层用的是一个Object类型的数组elementData，当使用无参构造方法ArrayList后elementData是空的，也就是说使用无参构造方法后容量为0。

// 容量为10
private static final int DEFAULT_CAPACITY = 10;
// add添加元素方法
public boolean add(E e) {
	// 按照元素个数+1，确认数组容量是否够用，所需最小容量方法
    ensureCapacityInternal(size + 1);
    // 将数组第size位置添加为该元素
    elementData[size++] = e;
    return true;
}

// 所需最小容量方法
private void ensureCapacityInternal(int minCapacity) {
	// 空数组初始所需最小容量为10，非空数组所需最小容量是元素个数+1
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 是否需要扩容方法
    ensureExplicitCapacity(minCapacity);
}

// 是否需要扩容方法
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 所需最小容量当前数组能否存下，如果现在数组存不下进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 容器扩容方法
private void grow(int minCapacity) {
    // 旧容量（原数组的长度）
    int oldCapacity = elementData.length;
    // 新容量（旧容量加上旧容量右移一位，也就是1.5倍）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果计算出的新容量比最小所需容量小就用最小所需容量作为新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果计算出的新容量比MAX_ARRAY_SIZE大, 就调用hugeCapacity计算新容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 数组扩容成新容量
    elementData = Arrays.copyOf(elementData, newCapacity);
}

由此看出只有当第一次add添加元素的时候，才初始化容量，因为是空数组所需的最小容量为10，而 elementData 大小为0，新容量算出类也是0，此时最小所需容量作为新容量为10。

例如：

ArrayList<Object> objects = new ArrayList<>();
长度:  1 容量： 10
长度:  5 容量： 10
长度:  11 容量： 15
长度:  15 容量： 15
长度:  21 容量： 22

ArrayList有参构造

//有参构造方法
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

有参构造和无参构造区别就是给数组初始化了长度initialCapacity并且数组不为空，不为空的数组最小所需容量就是集合元素长度，集合元素长度超过初始化长度initialCapacity值才扩容，扩容逻辑和无参构造一致。

例如：

ArrayList<Object> objects = new ArrayList<>(5);
长度:  3 容量： 5
长度:  5 容量： 5
长度:  7 容量： 7
长度:  11 容量： 15
长度:  15 容量： 15
长度:  19 容量： 22
ArrayList<Object> objects = new ArrayList<>(13);
长度:  15 容量： 19
长度:  17 容量： 19
长度:  21 容量： 28
长度:  25 容量： 28
长度:  29 容量： 42

Vector 扩容机制

Vector 的底层也是一个数组 elmentData，但相对于 ArrayList 来说，它是线程安全的，它的每个操作方法都是加了锁的。如果在开发中需要保证线程安全，则可以使用 Vector。扩容机制也与 ArrayList 大致相同。唯一需要注意的一点是，Vector 的扩容量是2倍。

结论

LinkedList，链表结构，且是是双向链表，不涉及扩容的问题。

8、CopyOnWriteArrayList 了解多少

CopyOnWriteArrayList 就是线程安全版本的 ArrayList。

它的名字叫 CopyOnWrite —— 写时复制，已经明示了它的原理。

CopyOnWriteArrayList 采用了一种读写分离的并发策略。CopyOnWriteArrayList 容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

CopyOnWriteArrayList 添加新元素是否需要扩容

CopyOnWriteArrayList 底层并非是动态扩容数组，不能动态扩容，其线程安全是通过ReentrantLock来保证的。当向其添加元素时候，线程获取锁的使用权，add方法中会新建一个容量为旧容量加一的数组，然后将旧数据拷贝到该数组，然后把新数据放在数组尾部。

9、为什么 ArrayList 不是线程安全的

ArrayList 和 Vector 线程安全区别就是add方法没有被synchronized修饰，这样的ArrayList会出现两种线程安全问题，第一种就是集合数据出现NULL的情况，线程A 是第一次add的时候，他知道他要去扩容，他自己扩容完复制成一个新的数组，然后给数组第一个下标赋值，此时size下标加1，如果线程A没有扩容完时候，线程B进入add方法时候，不巧也是以为要扩容，复制成一个新的数组，再赋值的时候，如果线程A把size加1了，那么线程B赋值时候就只能从第二个下标开始了。 [null , B的UUID值] 。

还有一种出现java.util.ConcurrentModificationException 并发冲突情况，modCount是修改记录数，expectedModCount是期望修改记录数，初始化的时候 expectedModCount=modCount，ArrayList的add函数、remove函数 操作都有对modCount++操作，当expectedModCount和modCount值不相等， 那就会报并发错误了。

实现 ArrayList 线程安全的方法

1.最简单的方式， 也是面经上经常看到的  使用 Vector ：
List<String> resultList = new Vector<>();

2.使用 Collections里面的synchronizedList ：
List<String> list1 = Collections.synchronizedList(list);

3.使用juc包下的 CopyOnWriteArrayList ：
CopyOnWriteArrayList list2 = new CopyOnWriteArrayList();

拓展：set 因为实现类都是线程不安全的，所以解决方法有

// 方式一：使用Collections集合类
// Set<String> set = Collections.synchronizedSet(set1);
// 方式二：使用CopyOnWriteArraySet

10、HashSet 的实现原理

HashSet底层其实是一个HashMap实例，数据存储结构都是数组+链表。HashSet中的元素都存放在HashMap的key上面，而value都是一个统一的对象PRESENT。

private static final Object PRESENT = new Object();

HashSet中add方法调用的是底层HashMap的put方法。如果是在HashMap中调用put方法，首先会去判断key是否已经存在，如果存在，则修改value的值，如果不存在，则插入这个k-v对。而在Set中，value是没有用的，所以也就不存在修改value的情况，故而，向HashSet中添加新的元素，首先判断元素是否存在，不存在则插入，存在则pass，这样HashSet中就不存在重复值了。

11、TreeSet 的实现原理

TreeSet底层实际是用TreeMap实现的，Treeset 底层是由红黑树实现的，内部维持了一个简化版的TreeMap，通过key来存储Set的元素。 TreeSet对存储的元素进行排序，如果未指定比较器，TreeSet 会使用元素的自然顺序（即元素必须实现 Comparable 接口）。如果指定了比较器，TreeSet 会使用比较器来排序元素。

12、Queue 与 Deque 的区别

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
|

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

/**
  * 测试队列 特殊的线性表，队列中限制了对线性表的访问只能从线性表的一端添加元素，从另一端取出，遵循先进先出(FIFO)原则
  */
 @Test
 public void test01() {
     Queue<String> que = new LinkedList<String>();
     // 添加队尾
     que.offer("3");
     que.offer("1");
     que.offer("2");

     // 获取队首
     String str = que.peek();
     System.out.println(str);// 3

     // 移除队首
     que.poll();
     System.out.println(que);// [1, 2]
 }

 /**
  * 栈是队的子接口，栈是继承队的，定义类"双端列"从队列的两端可以入队(offer)和出队(poll)
  * LinkedList实现了该接口，如果限制Deque双端入队和出队，将双端队列改为单端队列即为栈，栈遵循先进后出(FILO)的原则
  */
 @Test
 public void test02() {
     Deque<String> stack = new LinkedList<String>();
     // 压栈
     stack.push("aaa");
     stack.push("bbb");
     stack.push("ccc");
     System.out.println(stack);// [ccc, bbb, aaa]

     // 弹栈
     String lastStr = stack.pop();
     System.out.println(lastStr);// ccc
     lastStr = stack.pop();
     System.out.println(lastStr);// bbb
     lastStr = stack.pop();
     System.out.println(lastStr);// aaa
 }

13、ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

• ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
• ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
• ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

14、HashMap 的数据结构

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

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

其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。

• 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置。
• 如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素。
• 如果链表长度 > 8 并且数组大小 >= 64，链表转为红黑树。
• 如果红黑树节点个数 < 6 ，转为链表。

15、HashMap 的put流程

• 对 Key 求 Hash 值，然后再计算下标
• 如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的 Hash 值相同，需要放到同一个 bucket 中）
• 如果碰撞了，以链表的方式链接到后面
• 如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于 6，就把红黑树转回链表
• 如果节点已经存在就替换旧值
• 如果桶满了(容量 16*加载因子 0.75)，就需要 resize（扩容 2 倍后重排）
  • initialCapacity：初始容量。指的是 HashMap 集合初始化的时候自身的容量。可以在构造方法中指定；如果不指定的话，总容量默认值是 16 。需要注意的是初始容量必须是 2 的幂次方。
  • size：当前 HashMap 中已经存储着的键值对数量，即 HashMap.size()
  • loadFactor：加载因子。所谓的加载因子就是 HashMap (当前的容量/总容量) 到达一定值的时候，HashMap 会实施扩容。加载因子也可以通过构造方法中指定，默认的值是 0.75 。
  • threshold：扩容阀值。即 扩容阀值 = HashMap 总容量 * 加载因子。当前 HashMap 的容量
    大于或等于扩容阀值的时候就会去执行扩容。扩容的容量为当前 HashMap 总容量的两倍。

举个例子，假设有一个 HashMap 的初始容量为 16 ，那么扩容的阀值就是 0.75 * 16 = 12 。也就是说，在你打算存入第 13 个值的时候，HashMap 会先执行扩容，那么扩容之后为 32 。

16、HashMap 怎么查找元素的呢

首先，调用键的 hashCode() 方法，计算键的哈希值，然后，通过 HashMap 的哈希函数将哈希值映射到桶数组的索引。根据索引找到对应的桶（链表或红黑树的头节点）。遍历链表或红黑树，比较每个节点的键与目标键：

• 如果键相等（通过 equals() 方法判断），则返回对应的值。
• 如果遍历完链表或红黑树仍未找到，则返回 null。

17、为什么 HashMap 的容量是2的倍数呢

1. 优化索引计算：通过位运算 (n - 1) & hash 替代取模运算，提高性能。
2. 均匀分布哈希值：充分利用哈希值的所有位，减少哈希冲突。
3. 扩容优化：扩容时只需简单判断高位，避免重新计算所有元素的索引。

HashMap 初始化容量设置多少合适

return (int) ((float) expectedSize / 0.75F + 1.0F);

18、1.8 对 HashMap 主要做了哪些优化

1. 引入红黑树，在 Java 8 之前，HashMap 的冲突解决方式是完全基于链表的。当哈希冲突较多时，链表会变得很长，导致查找效率下降（时间复杂度为 O(n)）。当链表的长度超过阈值（默认是 8）时，HashMap 会将链表转换为红黑树（一种自平衡的二叉搜索树）。红黑树的查找、插入和删除操作的时间复杂度为 O(log n)，显著提高了性能。
2. 优化哈希函数，Java 8 的哈希函数更加简洁，只进行一次异或运算（h ^ (h >>> 16)）。
3. 改进扩容机制，Java 7 扩容时，所有元素需要重新计算索引，并插入到新的桶数组中。Java 8扩容时，HashMap 利用了 高位掩码 的特性，将元素分为两类，避免了重新计算所有元素的索引，提高了扩容的效率。

19、HashMap 和 Hashtable 有什么区别

• 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）
• 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它。
• 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
• 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间（后文中我会结合源码对这一过程进行分析）。Hashtable 没有这样的机制。
• 初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

20、HashMap 和 TreeMap 区别

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

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

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

TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });

综上，相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

21、为什么 HashMap 线程不安全

Java8中已经不再采用头插法，改为尾插法，即直接插入链表尾部，因此不会出现死循环和数据丢失，但是在多线程环境下仍然会有数据覆盖的问题。

首先我们看一下Java8中put操作的源码

注意红色框内的部分，如果插入元素没有发生hash碰撞则直接插入。

如果线程A和线程B同时进行put，刚好两条数据的hash值相同，如果线程A已经判断该位置数据为null，此时被挂起，线程B正常执行，并且正常插入数据，随后线程A继续执行就会将线程A的数据给覆盖。发生线程不安全。

Java7中头插法扩容会导致死循环和数据丢失，Java8中将头插法改为尾插法后死循环和数据丢失已经得到解决，但仍然有数据覆盖的问题。

有什么办法能解决HashMap线程不安全的问题呢

并发环境下推荐使用 ConcurrentHashMap（ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用 CAS + synchronized） 。或者

// 方式一：使用古老实现类Hashtable（是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大）
// Hashtable<String, String> table = new Hashtable<>();

// 方式二：使用Collections集合类（ 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现）
// Map<String, String> map1 = Collections.synchronizedMap(map);

22、怎么确保一个集合不能被修改

final关键字可以修饰类，方法，成员变量，final修饰的类不能被继承，final修饰的方法不能被重写，final修饰的成员变量必须初始化值，如果这个成员变量是基本数据类型，表示这个变量的值是不可改变的，如果说这个成员变量是引用类型，则表示这个引用的地址值是不能改变的，但是这个引用所指向的对象里面的内容还是可以改变的。

集合（map，set，list…）都是引用类型，所以我们如果用final修饰的话，集合里面的内容还是可以修改的。我们可以采用Collections包下来让集合不能修改：

1. Collections.unmodifiableList(List)
2. Collections.unmodifiableSet(Set)
3. Collections.unmodifiableSet(map)

23、LinkedHashMap 怎么实现有序的

LinkedHashMap维护了一个双向链表，有头尾节点，同时 LinkedHashMap 节点 Entry 内部除了继承 HashMap 的 Node 属性，还有 before 和 after 用于标识前置节点和后置节点。

可以实现按插入的顺序或访问顺序排序。

24、ConcurrentHashMap 实现原理

HashMap 在我们日常的开发中使用频率最高的一个工具类之一，然而使用 HashMap 最大的问题之一就是它是线程不安全的，如果我们想要线程安全, 这时候就可以选择使用 ConcurrentHashMap，ConcurrentHashMap 和 HashMap 的功能是基本一样的，ConcurrentHashMap 是 HashMap 的线程安全版本。

ConcurrentHashMap 原理

ConcurrentHashMap 是 HashMap 的线程安全版本，如何实现线程的安全性？

加锁。但是这个锁应该怎么加呢？在 HashTable 中，是直接在 put 和 get 方法上加上了 synchronized，理论上来说 ConcurrentHashMap 也可以这么做，但是这么做锁的粒度太大，会非常影响并发性能，所以在 ConcurrentHashMap 中并没有采用这么直接简单粗暴的方法，其内部采用了非常精妙的设计，大大减少了锁的竞争，提升了并发性能。

ConcurrentHashmap线程安全在jdk1.7版本是基于分段锁实现，在jdk1.8是基于CAS + synchronized实现。

jdk1.7 基于分段锁

在JDK1.7中，ConcurrentHashMap使用了分段锁技术，即将哈希表分成多个段，每个段拥有一个独立的锁。这样可以在多个线程同时访问哈希表时，只需要锁住需要操作的那个段，而不是整个哈希表，从而提高了并发性能。

虽然JDK1.7的这种方式可以减少锁竞争，但是在高并发场景下，仍然会出现锁竞争，从而导致性能下降。

在 JDK1.7 版本中，ConcurrentHashMap 由数组 + Segment + 分段锁实现，其内部分为一个个段（Segment）数组，Segment 通过继承 ReentrantLock 来进行加锁，通过每次锁住一个 segment 来降低锁的粒度而且保证了每个 segment 内的操作的线程安全性，从而实现线程安全。下图就是 JDK1.7 版本中 ConcurrentHashMap 的结构示意图

实际上就是相当于每个Segment都是一个HashMap，默认的Segment长度是16，也就是支持16个线程的并发写，Segment之间相互不会受到影响。

+-------------------+       +-------------------+
| Segment 1         |       | Segment 2         |
| +---------------+ |       | +---------------+ |
| | HashEntry[]   | |       | | HashEntry[]   | |
| +---------------+ |       | +---------------+ |
+-------------------+       +-------------------+

put流程

整个流程和HashMap非常类似，只不过是先定位到具体的Segment，然后通过ReentrantLock去操作而已，后面的流程，就和HashMap基本上是一样的。

1. 计算hash，定位到segment，segment如果是空就先初始化
2. 使用ReentrantLock加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功
3. 遍历HashEntry，就是和HashMap一样，数组中key和hash一样就直接替换，不存在就再插入链表，链表同样操作

get流程

get也很简单，key通过hash定位到segment，再遍历链表定位到具体的元素上，需要注意的是value是volatile的，所以get是不需要加锁的。

但是这么做的缺陷就是每次通过 hash 确认位置时需要 2 次才能定位到当前 key 应该落在哪个槽：

• 通过 hash 值和 段数组长度-1 进行位运算确认当前 key 属于哪个段，即确认其在 segments 数组的位置。
• 再次通过 hash 值和 table 数组（即 ConcurrentHashMap 底层存储数据的数组）长度 - 1进行位运算确认其所在。

jdk1.8 基于CAS + synchronized

在JDK1.8中，ConcurrentHashMap的实现方式进行了改进，使用CAS+Synchronized的机制来保证线程安全。实现线程安全不是在数据结构上下功夫，它得数据结构和hashMap一样，，ConcurrentHashMap会在添加或删除元素时，首先使用CAS操作来尝试修改元素，如果CAS操作失败，则使用Synchronizeds锁住当前槽，再次尝试put或者delete。这样可以避免分段锁机制下的锁粒度太大，以及在高并发场景下，由于线程数量过多导致的锁竞争问题，提高了并发性能。

+---+    +---+    +---+
| 0 | -> | A | -> | B | -> null
+---+    +---+    +---+
| 1 | -> null
+---+
| 2 | -> | C | -> null
+---+    +---+
|...|
+---+
| n | -> null
+---+

put流程

1. 首先计算hash，遍历node数组，如果node是空的话，就通过CAS+自旋的方式初始化
2. 如果当前数组位置是空则直接通过CAS自旋写入数据
3. 如果哈希槽处已经有节点，且hash值为MOVED，说明需要扩容，执行扩容
4. 如果都不满足，就使用synchronized写入数据，写入数据同样判断链表、红黑树，链表写入和HashMap的方式一样，key hash一样就覆盖，反之就尾插法，链表长度超过8就转换成红黑树

get查询

get很简单，和HashMap基本相同，通过key计算位置，table该位置key相同就返回，如果是红黑树按照红黑树获取，否则就遍历链表获取。

25、ConcurrentHashMap 和 Hashtable 区别

HashTable 使用的是 Synchronized 关键字修饰，ConcurrentHashMap 是JDK1.7使用了锁分段技术来保证线程安全的。JDK1.8ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。

synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

26、Iterator 怎么使用

/**
 * 测试Collection迭代对象的方式 迭代器的方式 Iterator接口，定义了迭代Collection 容器中对象的统一操作方式 集合对象中的迭代器是采用内部类的方式实现 这些内部类都实现了Iterator接口
 * 使用迭代器迭代集合中数据期间，不能使用集合对象 删除集合中的数据
 */
 @Test
 public void test02() {

     Collection<String> c1 = new HashSet<String>();
     c1.add("java");
     c1.add("css");
     c1.add("html");
     c1.add("javaScript");
     Iterator<String> it = c1.iterator();
     while (it.hasNext()) {
         String str = it.next();
         System.out.println(str);// css java javaScript html
         if (str.equals("css")) {
             // c1.remove(str);//会抛出异常
             it.remove();
         }
     }
     System.out.println(c1);// [java, javaScript, html]
 }

27、Java 集合使用注意事项总结

① 集合判空

判断所有集合内部的元素是否为空，使用 isEmpty() 方法，而不是 size()==0 的方式。

② 集合转 Map

在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。

List<Person> bookList = new ArrayList<>();
bookList.add(new Person("jack","18163138123"));
bookList.add(new Person("martin",null));
// 空指针异常
bookList.stream().collect(Collectors.toMap(Person::getName, Person::getPhoneNumber));

③ 集合遍历

不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。

通过反编译你会发现 foreach 语法底层其实还是依赖 Iterator 。不过， remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add方法这就导致 Iterator 莫名其妙地发现自己有元素被 remove/add ，然后，它就会抛出一个 ConcurrentModificationException 来提示用户发生了并发修改异常。这就是单线程状态下产生的 fail-fast 机制。

fail-fast 机制 ：多个线程对 fail-fast 集合进行修改的时候，可能会抛出ConcurrentModificationException。 即使是单线程下也有可能会出现这种情况，上面已经提到过。

④ 集合去重

可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains() 进行遍历去重或者判断包含操作。

⑤ 集合转数组

使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的是类型完全一致、长度为 0 的空数组。toArray(T[] array) 方法的参数是一个泛型数组，如果 toArray 方法中没有传递任何参数的话返回的是 Object类 型数组。

String [] s= new String[]{
    "dog", "lazy", "a", "over", "jumps", "fox", "brown", "quick", "A"
};
List<String> list = Arrays.asList(s);
Collections.reverse(list);
//没有指定类型的话会报错
s=list.toArray(new String[0]);

由于 JVM 优化，new String[0]作为Collection.toArray()方法的参数现在使用更好，new String[0]就是起一个模板的作用，指定了返回数组的类型，0 是为了节省空间，因为它只是为了说明返回的类型。

⑥ 数组转集合

使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法， 它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。

基本数据类型数组转集合

错误代码如下（示例）：

int[] arr = {1, 2, 3};
List list = Arrays.asList(arr);
System.out.println("集合为：" + list + " 长度为：" + list.size());
//集合为：[[I@4554617c] 长度为：1

当把基础数据类型的数组转为集合时，由于Arrays.asList参数为可变长泛型，而基本类型是无法泛型化的，所以它把int[] arr数组当成了一个泛型对象，所以集合中最终只有一个元素arr。

正确代码如下（示例）：

//（1）通过for循环遍历数组将其转为集合
int a[] = {1, 2, 3};
ArrayList<Integer> aList = new ArrayList<>();
for (Integer i : a) {
    aList.add(i);
}

//（2）使用Java8的Stream实现转换（依赖boxed的装箱操作）
int [] myArray = { 1, 2, 3 };
List myList = Arrays.stream(myArray).boxed().collect(Collectors.toList());

包装数据类型数组转集合

 Integer[] arr = {1, 2, 3};
 List list = Arrays.asList(arr);
 System.out.println("集合为：" + list + " 长度为：" + list.size());
//集合为：[1, 2, 3] 长度为：3

使用集合的修改方法: add()、remove()、clear()会抛出异常。

List myList = Arrays.asList(1, 2, 3);
myList.add(4);//运行时报错：UnsupportedOperationException
myList.remove(1);//运行时报错：UnsupportedOperationException
myList.clear();//运行时报错：UnsupportedOperationException

Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类，这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

28、如何利用List实现LRU

LRU 即最近最少使用策略，基于时空局部性原理（最近问的，未来也会被访问），往往作为缓存淘汰的策略，如Redis和GuavaMap都使用了这种淘汰策略。

我们可以基于LinkedList来实现LRU，因为LinkedList基于双向链表，每个结点都会记录上一个和下一个的节点，
具体实现方式如下：

package com.example.test.other.base;

import java.util.LinkedList;

public class LruListCache<E> {

    private final int maxSize;
    private final LinkedList<E> list = new LinkedList<>();

    public LruListCache(int maxSize) {
        this.maxSize = maxSize;
    }

    public void add(E e) {
        if (list.size() < maxSize) {
            list.addFirst(e);
        } else {
            list.removeLast();
            list.addFirst(e);
        }
    }

    public E get(int index) {
        E e = list.get(index);
        list.remove(e);
        add(e);
        return e;
    }

    @Override
    public String toString() {
        return list.toString();
    }

    public static void main(String[] args) {
        LruListCache lruListCache = new LruListCache(2);
        lruListCache.add(1);
        lruListCache.add(2);
        lruListCache.add(3);
        System.out.println(lruListCache.get(1));
        System.out.println(lruListCache.toString());

    }
}