image.png image.png

List：

• 1.可以允许重复的对象。
• 2.可以插入多个null元素。
• 3.是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。
• 4.常用的实现类有 ArrayList、LinkedList 和 Vector。ArrayList 最为流行，它提供了使用索引的随意访问，而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适。

1) ArrayList类

底层使用数组实现，查询快，增删慢
　　ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并 没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

和LinkedList一样，ArrayList也是非同步的（unsynchronized）。一般情况下使用这两个就可以了，因为非同步，所以效率比较高。
如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。

**数组：采用一段连续的存储单元来存储数据 **

2）LinkedList类

底层使用双向循环链表实现，查询慢，增删快
　　LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

注意:LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：List list = Collections.synchronizedList(new LinkedList(…));

单链表：每个节点包含值、链接到下一个节点的引用字段

image.png

双链表：双链表中的每个节点包含值，链接到下一个节点的引用字段、链接到上一个节点的引用字段

image.png

LinkedList中是双向链表

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

Set：

• 1.不允许重复对象
• 2. 无序容器，你无法保证每个元素的存储顺序，TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序。
• 3. 只允许一个 null 元素
• 4.Set 接口最流行的几个实现类是 HashSet、LinkedHashSet 以及 TreeSet。最流行的是基于 HashMap 实现的 HashSet；TreeSet 还实现了 SortedSet 接口，因此 TreeSet 是一个根据其 compare() 和 compareTo() 的定义进行排序的有序容器。

1）HashSet

底层使用哈希表实现
Hash表：Hash表也称散列表，也有直接译作哈希表，Hash表是一种根据关键字值（key - value）而直接进行访问的数据结构。它基于数组，通过把关键字映射到数组的某个下标来加快查找速度，但是又和数组、链表、树等数据结构不同，在这些数据结构中查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间级，但是对于哈希表来说，只是O(1)的时间级。

注意，这里有个重要的问题就是如何把关键字转换为数组的下标，这个转换的函数称为哈希函数（也称散列函数），转换的过程称为哈希化

哈希表基于数组，类似于key-value的存储形式，关键字值通过哈希函数映射为数组的下标，如果一个关键字哈希化到已占用的数组单元，这种情况称为冲突。用来解决冲突的有两种方法：开放地址法和链地址法。在开发地址法中，把冲突的数据项放在数组的其它位置；在链地址法中，每个单元都包含一个链表，把所有映射到同一数组下标的数据项都插入到这个链表中（HashMap）。

2）TreeSet：

底层使用二叉树实现
TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序 和定制排序，其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0

HashSet VS TreeSet

• 1、TreeSet 是二叉树实现的,Treeset中的数据是自动排好序的，不允许放入null值。
• 2、HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束。
• 3、HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的 String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。
• 4、HashSet是通过使用称为散列法的机制来存储信息的，元素并没有以某种特定顺序来存放；TreeSet提供一个使用树结构存储Set接口的实现(红黑树算法)，对象以升序顺序存储，访问和遍历的时间很快。

HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。

队列Queue：

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。

在并发队列上JDK提供了两套实现，一个是以ConcurrentLinkedQueue为代表的高性能队列（非阻塞队列），一个是以BlockingQueue接口为代表的阻塞队列，无论哪种都继承自Queue。

ConcurrentLinkedQueue：并发队列

是一个适用于高并发场景下的队列，通过CAS的无锁技术的方式，实现了高并发状态下的高性能，通常ConcurrentLikedQueue性能好于BlockingQueue。

它是一个基于链表节点的无界线程安全队列。该队列的元素遵循先进先出的原则。头是最先加入的，尾是最近加入的，该队列不允许null元素。

ConcurrentLinkedQueue重要方法：
add()和offer()都是加入元素的方法(在ConcurrentLinkedQueue中，这两个方法没有任何区别)。
poll()和peek()都是取头元素节点，区别在于前者会删除元素，后者不会。

BlockingQueue：阻塞队列

• ArrayBlockingQueue
  在ArrayBlockingQueue内部，维护了一个定长数组，以便缓存队列中的数据对象，其内部没实现读写分离，也就意味着生产和消费不能完全并行（并发性能差），它是一个有界队列。

• LinkedBlockingQueue
  基于链表的阻塞队列，其内部实现采用分离锁(读写分离两个锁)，从而实现生产者和消费者操作的完全并行运行，它是一个无界队列。线程安全
  LinkedBlockingQueue的吞吐量一般优于ArrayBlockingQueue，因为它实现了更加细粒度的锁操作。

• PriorityBlockingQueue：基于优先级的阻塞队列（优先级的判断通过构造函数传入的Compator对象来决定，也就是说传入队列的对象必须实现Comparable接口），在实现PriorityBlockingQueue时，内部控制线程同步的锁采用的是公平锁，它也是一个无界的队列。add()并不进行排序操作，只有在取数据时才进行排序。
  其内部排序采用的是堆结构，所有如果需要用到堆排序，可以直接用这个队列。

上面提到的队列都是单向队列，有些场景下我们需要双向队列，比如说我们要求队列中相邻的元素不能相同，这时候新插入元素时，就要和上一次插入的做对比，这时候就可以用到双向队列中的addFrist和getFrist来实现。

• ConcurrentLinkedDeque
• LinkedBlockingDeque

Map

1） HashMap

底层使用哈希表实现

2) TreeMap

底层使用红黑树实现

如何决定使用 HashMap 还是 TreeMap？

image.png

• HashMap：适用于在Map中插入、删除和定位元素。
• Treemap：适用于按自然顺序或自定义顺序遍历键（key）。
• HashMap通常比TreeMap快一点（树和哈希表的数据结构使然），建议多使用HashMap,在需要排序的Map时候才用TreeMap.
• HashMap： 非线程安全
• TreeMap： 非线程安全
• HashMap的结果是没有排序的，而TreeMap输出的结果是排好序的。

3） HashMap 底层实现

扩容机制：当hashMap put时，先查询hashMap 数组长度，当hashmap的size超过阈值（0.75，hasnMap默认初始化时长度为16）时，扩容；扩容是指，先建一个数组，数组长度为原有长度*2，然后再把原先数组中的值，重新添加到新的数组中；

hash算法：先对key取hashcode值，然后为了效率并不是直接取模，而是与 hashMap长度-1 做& 运算（这也就是HashMap的长度为什么要是2的n次方的原因）

• JDK1.7中
  HashMap使用一个Entry数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode相同，或者hashcode取模后的结果相同，那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表；
  在hash函数特别差的情况下，比如说所有key的hashcode都相同，这个链表可能会很长，那么put/get操作都可能需要遍历这个链表，也就是最差情况下时间复杂度为O（n）。

• JDK1.8中
  HashMap使用一个Node数组来存储数据，但是这个Node可能是链表结构，也可能是红黑树结构；如果插入的元素key的hashcode值相同，那么这些key也会被定位到Node数组的同一个格子里，当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率，当桶中链表元素个数小于等于6时，树结构还原成链表。
  那么即使所有key的hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要O（logn）的开销。

4） ConcurrentHashMap VS HashMap

• 4.1 HashMap
  我们知道HashMap是线程不安全的，在多线程环境下，使用Hashmap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap。
  是因为并发环境下，扩容时，可能会产生循环链表，后续如果有查询（无论是查询的迭代还是扩容）会触发死循环，引起CPU的100%问题，所以一定要避免在并发环境下使用HashMap。

  简单的说，就是在两个线程同时扩容时，A线程扩容完成后，B线程继续扩容（并发的原因AB线程扩容操作的是同一个table），因为A线程扩容已经完成了，这时候再操作扩容，那么数组长度并不会变化，如果链表只有一个元素，则B线程扩容操作会使其依然在原有的位置，但是如果链表有多个值相邻，则扩容时，由于使用的都是头插法（JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法），会使其形成循环链表。

  假如原先hasnMap链1位置是3->7->5；如下图

image.png

线程1 执行（Entry<K,V> next = e.next;）后，读取了3 和 next=7之后 线程时间片用完，线程挂起，调用线程2

线程2 完整的执行整个rehash操作，使hashmap的3位置链变成了7->3，1位置链变成了5->null（jdk1.7中hashmap的rehash用的是头插法）

image.png

第一次循环：把刚才读取到的3插入newTable的位置3，进入下一次循环，同时next=7
第二次循环：获取7并且继续插入位置3，同时由于线程2把7.next变成了3（7->3），所以下一次循环还是3，next=3
第三次循环：获取

继续执行线程1 的循环操作，采用头插法，先设置key==7的entry，然后再设置key==3的entry，这时候key==3的next引用是key==7（头插法，后插入的总是在头部），这样就形成了循环链表，那下次只要get 或者put操作的key hash 落到这个链表上，就会陷入死循环，容易导致cpu 100%

image.png

如果扩容前相邻的两个Entry在扩容后还是分配到table的相同位置上，就会出现死循环的BUG

总结：
HashMap是线程不安全的，其主要体现：
1.在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

• 4.2 HashTable
  HashTable和HashMap的实现原理几乎一样，差别无非是

  • HashTable不允许key和value为null
  • HashTable是线程安全的
    但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。
    多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

• 4.3 ConcurrentHashMap
  主要就是为了应对hashmap在并发环境下不安全而诞生的，ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响。

  我们都知道Map一般都是数组+链表结构（JDK1.8该为数组+红黑树）。

  ConcurrentHashMap避免了对全局加锁改成了局部加锁操作，这样就极大地提高了并发环境下的操作速度，由于ConcurrentHashMap在JDK1.7和1.8中的实现非常不同，接下来我们谈谈JDK在1.7和1.8中的区别。

  • 4.3.1 JDK1.7
    ConcurrentHashMap采用了数组+Segment（分段锁）的方式实现。
    使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问，内部结构图如下：
  image.png

  从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。
  第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。ConcurrentHashMap 有 16 个 Segments，所以理论上，最多可以同时支持 16 个线程并发写，这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。

  segment(分段锁)：ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。

  put实现：当执行put方法插入数据的时候，先通过hash值在segment中找到对应的位置，然后如果相应位置的segment还未初始化，则通过CAS进行赋值，接着执行segment对象的put方法通过加锁机制插入数据。

  size实现：因为concurrenthashmap是可以并发插入数据的，所以准确计算元素时有一定的难度，所以是先采用不加锁的方式，连续计算元素的个数，最多计算3次，如果前后两次计算结果相同，那么说明元素个数是准确的；如果前后两次计算结果都不相同，则给每个segment加锁，再计算一次元素的个数。

• 4.3.2 JDK1.8中
  放弃了segment的设计，参考了JDK8 HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，内部大量采用CAS操作Node数组。

  put实现 ：
  如果Node还未初始化，那么通过CAS插入相应的数据；
  如果Node不为空，且当前该节点不处于移动状态，那么对该节点加synchronized锁，如果该节点hash不小于0，则遍历链表更新节点或者插入新节点；
  如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节点；
  如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到8个，则通过treeifyBin方法转化为红黑树，如果oldVal不为空，说明是一次更新操作，没有对元素个数产生影响，则直接返回旧值；
  如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数baseCount；

  size实现：1.8中使用一个volatile类型的变量baseCount记录元素的个数，当插入新数据或则删除数据时，会通过addCount()方法更新baseCount。因为元素个数保存baseCount中，部分元素的变化个数保存在CounterCell数组中，通过累加baseCount和CounterCell数组中的数量，即可得到元素的总个数。

总结
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。

1. 数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
2. 保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
3. 锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。**对Segment加锁，segments数（并发数）在初始化后是不能扩容的，所以对Node加锁后，锁的粒度更细，可以支持更大的并发
4. 链表转化为红黑树：定位结点的hash算法简化会带来弊端，Hash冲突加剧，因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
5. 查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。