常用类包括但不限于：

• List
• Set
• Map

List

最常用的就是ArrayList，其本质上就是一个数组

ArrayList是如何扩容的？

通过grow函数，创建size右移一位的数组，再addAll一遍

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Set

本质利用equals方法，不允许重复元素的集合

Set的add是比较低效的

因为每次set都要遍历一遍，挨个equals过去，o(n)的复杂度

HashSet

最常⽤，最⾼效的Set实现

• 使⽤HashSet对ArrayList去重
• HashSet是⽆序的, 如果有需要可以使⽤LinkedHashSet

hashCode：Java世界⾥第⼆重要的约定
同⼀个对象必须始终返回相同的hashCode

在HashSet中，利用hash桶，将同样的hashcode的value塞到同一个桶里，如此往复，判断equals的时候，就可以通过判断hashcode到对应的hash桶里遍历，o(log2n)的复杂度

约定：

• 同⼀个对象必须始终返回相同的hashCode
• 两个对象的equals返回true，必须返回相同的hashCode
• 两个对象不等，也可能返回相同的hashCode

哈希冲突: 大量的key的hashcode都一样，导致全部分配到了一个hash桶里，这样将导致hashset的高效性大大降低，成为了一个set

Map

一种key,value形式的数据结构， 一个map不能包含重复的key。用来取代Dictionary类的存在

常用方法：

• C/U: put()/putAll()
• R: get()/size()/containsKey()/containsValue()/keySet()/values()/entrySet()
• D: remove()/clear()

HashMap

HashMap的扩容

HashMap的keySet本质上也是一个HashSet，他利用了hash桶的高效性。
但是因为哈希冲突无法完全避免，因此为了提高HashMap的性能，HashMap不得尽量缓解哈希冲突以缩短每个桶的外挂链表长度。

所以当存储Entry较多的时候，就需要考虑增加hash桶的数量，也就涉及到了扩容

public HashMap(int initialCapacity, float loadFactor) ;

• 第一个参数：初始容量，指明初始的桶的个数；相当于桶数组的大小。
  第二个参数：装载因子，是一个0-1之间的系数，根据它来确定需要扩容- 的阈值，默认值是0.75。

  put() {
    ...
    if (++size > threshold)  resize();
  }
  // HashMap在Put的时候会判断size，然后动态扩容
  

  if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
      oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold
    }

HashMap在Put的时候会判断size, 始终保持 2^n，扩容后数组大小为当前的 2 倍

扩容的数组的长度为什么保持 2^n？
其实这是为了保证通过hash方式获取下标的时候分布均匀。数组长度为2的n次幂的时候，不同的key 算得得 index 相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

HashMap的线程不安全性

HashMap和HashSet本质上是⼀种东⻄

  * Returns a {@link Set} view of the keys contained in this map.
  * The set is backed by the map, so changes to the map are
  * reflected in the set, and vice-versa. 
  // HashMap的keySet是一个HashSet，对hashSet的改变会反馈到map，反之亦然
 

HashMap在Java 7+后的改变：链表->红⿊树

HashMap的存储方式：数组 + 链表 + 红黑树

indexFor： hash & （length -1）

先利用indexFor来给每一个put的数据分到对应的数组下标

数组下标对应的链表，但链表数据膨胀依然会导致查询效率下降

链表大于8个数据会转化为红黑树

转换为红黑树后，利用hash(key)的大小，根据红黑树的特性，可将时间复杂度从链表的o(n)转化为 o(log2n)

扩展

有序集合TreeSet/TreeMap

使用红黑树存储的数据结构，使⽤Comparable约定，认为排序相等的元素相等

Collections⼯具⽅法集合

• emptySet(): 等返回⼀个⽅便的空集合
• synchronizedCollection: 将⼀个集合变成线程安全的
• unmodifiableCollection: 将⼀个集合变成不可变的（也可以
  使⽤Guava的Immutable）

Collection的其他实现

• Queue/Deque
• Vector/Stack （replaced by Deque）
• LinkedList
• ConcurrentHashMap
• PriorityQueue

Guava

• Lists/Sets/Maps
• ImmutableMap/ImmutableSet
• Multiset/Multimap
• BiMap