接口
Collection Map
List Set
实现类
List下有ArrayList，LinkedList，Vector
Set下有HashSet，TreeSet
Map下有HashMap，LinkedHashMap，TreeMap，HashTable

List

有序，可以重复

ArrayList

底层数据结构为数组，查询快，增删慢
线程不安全，效率高
内部维护了一个可变长的对象数组，集合内所有对象存储于这个数组中，并实现这个数组长度的动态伸缩。
使用数组拷贝实现指定位置的插入和删除。

LinkedList

底层数据结构是链表，查询慢，增删快
线程不安全，效率高
其实现了静态类Node，集合内的每个对象都由一个Node保存，每个Node都拥有自己前一个和后一个node的引用。
LinkedList是一个实现了List接口和Deque接口的双端链表。 LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性;
LinkedList不是线程安全的，如果想使LinkedList变成线程安全的，可以调用静态类Collections类中的synchronizedList方法：

  1. List list=Collections.synchronizedList(new LinkedList(...));

Vector

底层数据结构为数组，查询快，增删慢
线程安全，效率低

Set

HashSet

底层数据结构为哈希表，也叫散列表，实际上是一个HashMap实例
元素都存在hashMap键值对的key上边，而value是有一个同一的值
private static final Object PRESENT = new Object();(定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final)
当有新值插入时，底层的HashMap会判断key值是否存在，如果不存在就插入，如果存在就不插入
对于HashSet中保存的对象，主要要正确重写hashcode方法和equals方法，以保证放入set对象的唯一性

TreeSet

底层数据结构是红黑树，实际上是一个TreeMap的实例

Map

TreeMap是有序的，HashMap和HashTable都是无序的
Map将key和value封装到一个叫做Entry对象中，map实际存储的元素是Entry

HashMap

Jdk1.8之前，底层数据结构是数组（O(1)）+链表(O(n))。数组是hashmap的主体，链表是为了解决哈希冲突而存在的。
1.8之后，是数组+链表（红黑树O(log(n))）。当链表长度大于8时，将链表转为红黑树，可以提高查找效率；链表长度小于6，将红黑树转为链表
我们使用put方法传递键和值时，由每个Entry中的key的哈希值决定该Entry在数组中的位置。这种特性实现通过key快速查找到Entry，从而获得该key对应的Value。在不发生哈希冲突的前提下，查找的时间复杂度为O（1）
如果两个不同的key计算出的index是一样的，就会发生两个key都对应数组同一个位置，就是哈希冲突
解决哈希冲突，使用链地址法
也就是数组中每个位置存储的是一个Entry链表。链表中每个Entry都拥有指向链表后一个Entry的引用，在发生哈希冲突时，将冲突的Entry追加到链表的头部。

如果两个对象的hashcode相同，如何获取值对象？
先使用键对象的hashcode找到bucket位置，调用keys.equals()方法找到链表中正确的节点，最终找到要找的值对象。

平衡二叉树（AVL树）

平衡二叉树必须具备如下特性：

  • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1

  • 并且左右两个子树都是一棵平衡二叉树

    为什么要使用红黑树，不用其他树？

    选择红黑树可以解决二叉查找树的缺陷：二叉查找树在特定情况下会变成一条线性结构，这就跟链表一样了，遍历查找会特别慢。而红黑树在插入数据后，通过左旋，右旋，变色这些操作保持平衡。引入红黑树就是为了查找数据快，解决链表查询深度的问题。我们知道红黑树属于平衡二叉树，为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少。所以当长度大于8的时候，会使用红黑树；如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

    为什么不使用AVL树？

    AVL树查找效率很高，但是它的旋转比红黑树的旋转更难，所以增删效率低
    红黑树查找，增删效率都较好，并不是严格的平衡二叉树。

    红黑树的特点？

  • 每个节点非红即黑

  • 根节点总是黑色的
  • 如果一个节点是红色的，那它的父、子节点都是黑色
  • 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的
  • 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点

image.png

HashMap的扩容机制

hashmap的初始桶(bucket)的数量为16，负载因子(loadFact)为0.75,当桶里面的数据记录超过阈值的时候，HashMap将会进行扩容则操作，每次都会变为原来大小的2倍，直到设定的最大值之后就无法再resize了。
HashMap的扩容是调用resize方法

为什么hashMap大小是2的次幂？

因为在计算元素存放位置时，用到的算法是将元素的hashcode与当前map长度-1进行与运算。

  1. static int indexFor(int h, int length) {
  2.     // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
  3.     return h & (length-1);
  4. }

如果map长度为2的幂次，那长度-1的二进制一定为11111…这种形式，进行与运算就看元素的hashcode，但是如果map的长度不是2的幂次，比如为15，那长度-1就是14，二进制为1110，无论与谁相与最后一位一定是0，0001，0011，0101，1001，1011，0111，1101这几个位置就永远都不能存放元素了，空间浪费相当大。也增加了添加元素是发生碰撞的机会。减慢了查询效率。所以Hashmap的大小是2的幂次。

HashMap为什么是线程不安全的？

  1. put时导致多线程数据不一致

put方法和addEntity方法都不是同步的
比如有线程A和线程B，线程A调用put方法插入数据，先调用hashcode方法计算出hashcode值，再找到该桶里的链表头结点，此时线程A的时间片用完了，线程B开始执行，跟线程A一样执行，然后线程B成功将数据插入到桶中，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么在B成功插入后，A再次执行时，将B的数据给覆盖掉了，造成了数据不一致

  1. get操作可能因为resize导致死循环

resize方法不是同步的。

HashMap和HashTable的区别

  • Hashmap是线程不安全的，效率高；HashTable是线程安全的，效率低
  • hashmap可以存储null键和null值；hashTable无论key和value都不能为null
  • hashmap的初始容量为16，hashtable的初始容量为11，hashmap要求底层数组的容量一定要为2的整数次幂，hashtable不要求
  • hashmap扩容时，将容量变为原来的2倍；hashtable扩容时，将容量变为原来的2倍加1

    ConcurrentHashMap

    hashTable之所以效率低下主要是因为其实现了synchronized关键字对put等操作加锁，而synchronized关键字加锁是对整个对象进行加锁，也就是说在进行put等修改hash表操作时，锁住了整个Hash表，从而同一时刻只能有一个线程进行操作。
    采用锁分段技术，首先将数据分成一段一段存储，然后给每一段数据配一把锁，当一个线程占用锁访问一段数据时，其他段的数据也能被其他线程访问。有些方法需要跨段，比如size()和containsValue()，他们可能需要锁定整个表，这需要按顺序锁定所有段，操作完毕后，又要按顺序释放所有段的锁，按顺序很重要，否则容易死锁。

在jdk1.8之前，ConcurrentHashMAp是由segment数组结构+hashEntry数组结构组成。
segment是一种可重入锁ReentrantLock，HashEntry负责存储键值对数据。一个ConcurrentHashMap里包含一个segment数组，segment的数据结构也是数组+链表。一个segment里包含hashEntry数组，每个hashEntry是一个链表结构的元素，每个segment守护着一个hashEntry数组里的元素，当对hashEntry数组里的元素进行修改时，必须先获得它对应的segment锁。每当一个线程占用锁访问一个segment时，不会影响到其他的segment。

image.png
image.png
jdk1.8,底层是数组+链表+红黑树，加锁是synchronized+CAS算法。
取消了segment分段锁的数据结构，采用数组+链表+红黑树。
取消对segment分段加锁，并发控制使用synchronized+CAS来操作，
现在是对每个数组元素加锁（Node）node是一个继承Map.Entry的链表，保存的key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。
image.png
image.png

TreeMap

底层数据结构为红黑树