集合框架总体结构
Collection 顶层接口下细分为三个类型，分别为
- List，一种有序的集合。根据索引可以方便的插入，访问。允许重复元素。
- LinkedList，较高性能的删除插入操作，毕竟指针指一下就好了。
- ArrayList，根据下标的高性能随机访问。
- Vector，线程安全的和 ArrayList 几乎功能一样的结构。
- Set，存储不重复元素的集合。通过 equals 方法来判断
- HashSet，基于哈希表，保证存储唯一元素的结构。
- TreeSet，底层利用了许多 TreeMap 的 API。
- Queue/Deque，Java 提供的标准队列实现，其中 Deque 双端队列支持队列的两端操作。
- Map，最常用的键值对存储结构。
- HashMap，提供高效的插入，访问，无序存储。
- LinkedHashMap，HashMap 的子类，保存了记录的插入顺序。一般通过 Iterator 去遍历。
- Hashtable，线程安全的 HashMap，已经不建议使用。可以使用同步性能更高的** juc.ConcurrentHashMap**
- TreeMap，基于红黑树的映射结构， log(n) 时间复杂度的基本操作。提供顺序访问，通过指定的 Comparator 指定，默认升序。其 key 必须实现 Comparable 接口或传入自定义的 Comparator。
（图来自美团点评团队）
常用类分析
对任何集合类的性能分析，具体场景中的适用情况，都不能脱离其底层数据结构的特点。
例如 ArrayList 底层采用动态数组实现，那对于保证有序的，且频繁的插入删除场景其性能是有限的。LinkedList 底层使用双向链表，随机访问的性能就没那么友好了。
HashMap
底层结构
首先要知道的就是构成 HashMap 的内部结构，是 数组（Node<K,V>[] table） + 链表 + 红黑树（1.8 后引入）。
static class Node<K,V> implements Map.Entry<K,V> {}
HashMap 将要存储的键值通过其哈希值确定元素在桶中存储的位置。因为桶的位置有限，而要存储的元素可能无限，所以不同的元素很可能被映射到同一个桶，就是我们常说的哈希冲突。
到这你就要想到为什么重写了 equals 方法，对应的 hashCode 也需要重写。 当一个类提供了自己的相等逻辑时（重写了 equals 方法），这时如果没有重写 hashCode 方法，就无法保证两个 equals 返回 true 的实例的 哈希值相同。
举一个更新的例子，那么当使用该类作为哈希表的键值时就会出现预期外的行为。例如：
User userA = new User(24,"crayon"); // id，昵称
Map<User,String> userMap = new HashMap<>();
userMap.put(userA,"用户A");
//在下一次我们构建一个和 userA “逻辑相同”的对象去取值
User userB = new User(24,"crayon");
userMap.get(userB);
在我们调用 userMap 的 get 方法时，我们预期中返回的正确结果应该是 “crayon”，但很可能取出来的是一个 null。
关键在于，我们自己提供了对象“逻辑相等”的概念，但二者调用 hashCode 时返回的 hash 值却不同。当去 get 的时候，根据 userB 的 hash 值找桶中的位置，而 Object 中默认的 hashCode 计算方法是随着对象的内存地址在改变的，导致最终结果是定位不到 userA 存储的桶位置。
重写 hashCode 方法保证了 equals 相等时，调用 hashCode 返回的 int 值也相同
源码分析
// The default initial capacity - MUST be a power of two.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 结点树化的阈值
static final int TREEIFY_THRESHOLD = 8;
// 退化为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// The smallest table capacity for which bins may be treeified.
// 就是说当桶的数目大于这个值是拉出来的链表才会树化，不然就直接 resize。
static final int MIN_TREEIFY_CAPACITY = 64;
DEFFAULT_LOAD_FACTOR 一般叫负载因子，他是触发哈希扩容的重要条件。
再看一个成员变量，size（哈希表实际存储的元素个数）超过 threshold 就触发扩容。
//The next size value at which to resize (capacity * load factor).
int threshold;
插入方法
看来秘密都在 putVal 中
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
建议自己去源码再实际分析一遍
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 空表的话，再去 resize() 进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. (n - 1) & hash 就是哈希寻桶位置的实现
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 3. 发生哈希冲突
else {
Node<K,V> e; K k;
// p - 已存储元素，hash - 待存储元素的哈希值
// 4. 判断是不是相同的元素，是的话跳到 10.
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 5. 不同元素，是红黑树结构，调红黑树的插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 6.
else {
for (int binCount = 0; ; ++binCount) {
// 一直没有重复元素，到末尾直接newNode 放进去就行
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 在遍历链表的过程中，看有没有重复元素,有的话跳出来
// 去 10. 处更新旧value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// p = p.next
p = e;
}
}
// 10.
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 只有插入新的值才会改变 modCount
++modCount;
// size 有没有超过 阈值
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
从 p = tab[i = (n - 1) & hash] 我们知道是通过 (n - 1) & hash 去把哈希值映射到数组下标中。n 是桶数组长度。
这里就解释了为什么 HashMap 的桶长度 must be power of two.
当长度为 2 的幂时，其二进制表示中只有一位为 1，例如 16 表示为
0001 0000，32 表示为 0010 0000。那么对应为 n - 1时，其表示为
0000 1111。我们假设某个要存储的哈希值的二进制表示为 1101 1001，是完全没有规律的。那么当这两个数做 与 操作（同 1 才为 1，否则为 0）时，
0000 1111
1101 1001
0000 1001
有没有发现，高几位的值不管哈希值是什么，都算出是 0，也就保证 & 出来的结果一定在桶长度内。（优化思路就是把简单的取余操作换成位运算）
桶长度 must be power of two 还有一个好处，往下看你就知道了。
扩容方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
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
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 初始化操作
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 计算哈希值的高一位是 0 还是 1
if ((e.hash & oldCap) == 0) { // 为 0
...
}
else { // 高一位为 1
...
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// 高一位为 0 时，元素的存储位置数组下标没有变化
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 为 1，元素存储位置为 旧数组下标 + 原容量 。
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
大家可以先自己思考一下为什么通过判断(e.hash & oldCap) == 0 就能判断扩容后元素的存储位置。
有没有看出来点什么？扩容前和扩容后的 & 计算值差别就只是元素 hash 值中和原容量 16 二进制表示中的那个 1 的位置是 0 还是 1 有关。
如果旧元素的二进制表示为 1100 1001，那么计算结果就是 0000 1001。
看到这说明你是一个一直在提高自己的人，给自己点个赞！
如果你觉得对你有帮助的话，也可以点赞支持一下。😃
转载：https://blog.csdn.net/FangHX25/article/details/105271787