集合

⼀、集合分类

Java中的集合框架⼤类可分为Collection和Map，⽽collection⼜有两个⼦接⼝List和Set

1. List

• 特点：元素有顺序，能重复 ，可以插⼊多个 null 元素。

• List 接⼝有三个实现类：LinkedList，ArrayList，Vector

  • LinkedList：底层基于链表实现，链表内存是散乱的，每⼀个元素存储本身内存地址的同时还存储下⼀个元素的地址。链表增删快，查找慢

  • ArrayList 可变⻓数组，查询快，⾮同步，ArrayList 是⾮线程安全的，效率⾼；

  • Vector 是基于线程安全的，效率低

2. Set

• 特点：元素⽆⽆顺序，不能重复，只允许⼀个 null 元素

• 最流⾏的⼏个实现类是 HashSet、LinkedHashSet 以及 TreeSet

  • HashSet： HashSet 类按照哈希算法来存取集合中的对象，存取速度⽐较快

  • TreeSet ：TreeSet 类实现了 SortedSet接⼝，能够对集合中的对象进⾏排序。 TreeSet 通过 Comparator 或者Comparable 维护了⼀个排序顺序。

3. Map

• 特点：元素按键值对存储，⽆放⼊顺序
• 最流⾏的⼏个实现类是 HashMap、HashTable、TreeMap、ConcurrentHashMap、LinkedHashMap
  • HashMap:线程不安全的Map,最常用的Map
  • HashTable: 线程安全，在各个方法上添加了synchronize关键字，现在已经不再推荐使用HashTable了，因为现在有了ConcurrentHashMap这个专门用于多线程场景下的map实现类，其大大优化了多线程下的性能
  • TreeMap：TreeMap也是一个很常用的map实现类，因为他具有一个很大的特点就是会对Key进行排序
  • ConcurrentHashMap：是HahsMap的一个子类，但它保持了记录的插入顺序，遍历时先得到的肯定是先插入的，也可以在构造时带参数，按照应用次数排序，在遍历时会比HahsMap慢，不过有个例外，当HashMap的容量很大，实际数据少时，遍历起来会比LinkedHashMap慢（因为它是链啊），因为HashMap的遍历速度和它容量有关，LinkedHashMap遍历速度只与数据多少有关

⼆、常考集合底层实现

1. ArrayList

1. 底层实现

ArrayList底层是Object数组存储数据，查找快，增删慢。

new ArrayList()的初始容量，在jdk1.6中是为10，然⽽在1.8中，如果只是new ArrayList()，容量其实是 0，当第⼀次通过add(e)时，才扩充为10。但它的扩容还是到之前的1.5倍的⼤⼩,每次扩容都是将原数组的数据复制进新数组中。

2.如何避免ArrayList的并发问题？

1. 使⽤Vector

Vector 是线程安全的。它和 ArrayList 差不多，只是在⽅法上加了synchronized 锁，扩容为原来的两倍或原容量 加扩容因⼦（构造时指定）。

public synchronized boolean add(E e) { 
  modCount++;
  ensureCapacityHelper(elementCount + 1); elementData\[elementCount++\]= e;
  return true; 
}

2. 使⽤Collections.synchronizedList

使⽤Collections.synchronizedList()⽅法对ArrayList对象进⾏包装,SynchronizedList是线程安全的根本原因是使⽤Synchronized对SynchronizedList的add,delete等操作进⾏加锁，把原来ArrayList在⽅法上加锁替换成了在代码块加锁，但是这种锁的⼒度很⼤，所以这种⽅式效率低下。

public void add(int index, E element) { 
  synchronized(mutex){
    list.add(index, element);
  }
}

3. 使⽤并发容器CopyOnWriteArrayList

CopyOnWriteArrayList 是写时复制的容器，就是我们往容器⾥写东⻄时，不是直接写，⽽是先Copy当前容器，然后往新容器⾥添加元素，在将原容器的引⽤指向新容器。

• 这样做的好处是：可以并发的读，⽽不需要加锁，因为当前容器不会添加任何元素。如果在添加数据的期间，其他线程如果要去读取数据，仍然是读取到旧的容器⾥的数据。

• CopyOnWriteArrayList是⼀种读写分离的思想，只是在增删改上加锁，但是读不加锁，在读⽅⾯的性能就好于Vector，CopyOnWriteArrayList⽀持读多写少的并发情况。

• CopyOnWriteArrayList 中的add、set、remove等⽅法，都是 ⽤了 ReentrantLock 的lock()来加锁，unlock()来解锁。 当增加元素时使⽤Array.copyOf()来拷⻉副本，在副本上增加元素，然后改变原引⽤指向副本，读操作不加锁。适合读操作远远多于写操作的应⽤。

缺点：

（1） 内存占⽤问题；

（2）数据⼀致性问题CopyOnWrite机制只能保证最终的数据⼀致，不能保证实时数据⼀致，因此如果希望写⼊的数据能⻢上读到，就不应该⽤ CopyOnWrite;

public boolean add(E e) {
  final ReentrantLock lock = this.lock; 
  lock.lock();
  try {
    Object[] elements = getArray();
    int len = elements.length;
    Object[] newElements = Arrays.copyOf(elements, len + 1);
    newElements[len] = e;
    setArray(newElements);
    return true;
  } finally { 
    lock.unlock();
  }
} 

2. LinkedList

1.底层实现

LinkedList 是以双向链表实现，链表⽆容量限制，且增删快，查询慢。其内部主要成员为 first 和 last 两个 Node节点，在每次修改列表时⽤来指引当前双向链表的⾸尾部位，来对链表两头的进⾏操作。

• LinkedList线程不安全的，因为其内部添加、删除、等操作，没有进⾏同步操作。

2. 如何避免LinkedList的并发问题？

1. Collections.synchronizedList

2. ConcurrentLinkedQueue

   ConcurrentLinkedQueue 采⽤ CAS 乐观锁的机制实现⾮阻塞队列（BlockingQueue 阻塞队列）

3. hashMap

1.底层实现

hashMap底层原理

2. HashMap的put实现

当往hashmap里put(key,value)新元素时，

利用key计算出hash值，然后再计算下标；求解下标的具体过程为：得到key.hashcode进行高16位^低16位，得到hash值；根据下标index=(n - 1) & hash，即可计算出下标。
放入节点时，有以下4种情况（源码中用4个if、else实现）：

• 数组原本位置为空，直接放入。
• 数组原本位置不为空，且下面连接了链表，往链表中添加节点，当链表长度为8时，进行树形化，将链表转为红黑树。
• 数组原本位置不为空，且下面连接了红黑树，往树中添加节点，当红黑树的节点个数为6时，将红黑树转为链表。
• 数组原本位置不为空，但要放入的节点的key与当前节点的key相同，则进行值覆盖，用新值替换旧值。

3. HashMap 是如何扩容的？

HashMap出现扩容有两种情况：

在扩容的时候，首元素达到阈值了，即当前容量*0.75。

hashMap准备树形化但发现数组太短，即小于最小树形化的容量。

当扩容时有两种情况：

当前容量已达最大，即长度已经为2^30，则不进行扩容，返回当前数组。

否则，在现在基础上扩大二倍

4. 为什么以2的n次幂进行扩容？

在hashmap中数组下标的确定是通过index=(n-1)&hash计算的，2^n换成二进制都是“100000….”这种形式，减一后都是“011111..”.这种除了第一位后面几位都是1的二进制数

这样的话，相当于hashmap的位置，就只和hashcode的值有关，算出来的index是分布均匀的。

当不全为1，出现“01101”这样的形式，那么与0对应的那一位，不论hashcode值是0还是1，进行与运算后，都会放入同样的位置，这样会大大增加hash冲突。向扩容后的数组挪动的时候有以下3种情况

• 只有一个节点 ：将当前节点置空后，新的位置=hash & (newCap - 1)
• 数组下有链表：原下标+原容量
• 数组下有红黑树：进行分割

5. JDK1.7 和 JDK1.8 对 HashMap 的实现比较

1. 底层数据结构不同

在 HashMap 的 put 过程中，JDK1.7 时是没有红黑树这一概念的，直接是进行的链表存储，在 JDK1.8 之后才引入了红黑树的概念，来优化存储和查找。

2. 链表的插入方式不同

在 HashMap 向链表中插入元素的过程中，JDK1.7 时是在表头节点插入的，JDK1.8 之后是在尾节点插入的。简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后

3. 扩容后数存储位置的计算方式不同

扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，位置不变或索引+旧容量大小； 在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；

6. HashMap 的哈希函数怎么设计的吗？

hash 函数是先拿到通过 key 的 hashcode，是 32 位的 int 值，然后让 hashcode 的高 16 位和低 16 位进行异或操作。

为什么这么设计吗？

• 高16位与低16位：是为了避免没有高位参与运算引起的碰撞。
• 异或：因为异或属于逻辑运算，在硬盘上实现的，运算速度快，像+、-、这种都属于算数运算，速度较慢。

7. 链表的插入方式为什么从头插法改成了尾插法？

1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环； A 线程在插入节点 B，B 线程也在插入，遇到容量不够开始扩容，重新 hash，放置元素，采用头插法，后遍历到的 B 节点放入了头部，这样形成了环，

8. 如何避免hashMap的并发问题？

1. Hashtable

HashTable的主要⽅法的源码实现逻辑，与HashMap中⾮常相似，但它的所有的操作都是通过添加synchronized锁的，从⽽实现了线程安全，尽管JVM对它做了优化，但效率还是不⾼。

public synchronized V put(K key, V value) { 
  if (value == null) {
  throw new NullPointerException();
}

2 ConcurrentHashMap

我们常⽤的是java.util.concurrent包下的ConcurrentHashMap

1.原理概述

之前的版本：

1. ConcurrentHashMap通过在CAS和分段加锁来实现同步，分段加锁就是在ConcurrentHashMap 中，就是把 Map 分成了N 个 Segment（默认 16个），进⽽减⼩锁的⼒度。

2.put 和 get 的时候，都是现根据 key.hashCode()算出放到哪个 Segment中。Segment 在实现上继承了 ReentrantLock，这样就⾃带了锁的功能，在put
的时候需要锁住 Segment，get 时候不加锁，使⽤ volatile 来保证可⻅性。

jdk1.8：

1.ConcurrentHashMap 取消了 segment 分段锁，⽽采⽤ CAS 和 synchronized来保证并发安全。数据结构跟 HashMap1.8 的结构⼀样，也是在链表节点数达到 8个时，转为红⿊树。

2.synchronized只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要hash不冲突，就不会产⽣并发，效率⼜提升N倍。（之前是固定的段数N，现在是根据数组⻓度呈线性变化的)

2.put 实现

与hashmap⼤体⼀致，就是据 key 的 hash 值找到 node 数组相应位置后1.如果相应 node 还未初始化，则调⽤ CAS 操作插⼊相应数据。

2.如果相应位置 node 不为空，则使⽤synchronized同步代码块对链表和红⿊树进⾏更新插⼊操作。以此来实现同步。

final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        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) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        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;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

4 HashSet

1 底层实现

HashSet 底层是使⽤ HashMap来保存元素的,元素都存到HashMap键值对的Key上⾯，⽽Value它定义了⼀个统⼀的虚拟的Object对象。它最⼤的特点就是可以去重。

1. add ⽅法（HashSet去重原理）

add ⽅法调⽤的是 HashMap 的 put ⽅法向 HashSet添加元素，实际是往map成员变量⾥⾯添加对应的key和 value，map中的key实际就是要添加的元素，value是⼀个固定的对象，具体操作为：

1.HashSet 在存元素时会调⽤对象的 hashCode ⽅法计算出存储索引位置
2.如果其索引位置已经存在元素（哈希碰撞）则和该索引位置上所有的元素进⾏equals ⽐较，如果该位置没有其 他元素或者⽐较的结果都为 false就存进去，否则就不存。
3.所以可以看⻅元素是按照哈希值来找位置的，故⽽⽆序且可以保证⽆重复元素，因此我们在往HashSet 集合中存 储元素时，元素对象应该正确重写Object 类的 hashCode 和equals ⽅法，否则会出现不可预知的错误。

public boolean add(E e) {
  return map.put(e, PRESENT)==null; 
}

• HashSet 不是线程安全的，底层的 HashMap不是线程安全的，它⾃然就不是啦，可以使⽤Collections.synchronizedSet(new HashSet()) 来创建线程安全的 HashSet。

• 由于 hashMap 中的 key 不能重复，所以 hashSet 不能存储重复元素；

2.如何避免HashSet的并发问题？

1. CopyOnWriteArraySet

   CopyOnWriteArraySet底层实现是利⽤数组，它的上层实现是CopyOnWriteArrayList。

   CopyOnWriteArraySet是⼀个集合，所以它是不可以放置重复的元素的，它的取重逻辑是在add中体现的。

   CopyOnWriteArraySet 是利⽤ CopyOnWriteArrayList来实现的，因为CopyOnWriteArrayList 是线程安全 的，所以CopyOnWriteArraySet 操作也是线程安全的