共计 4736 个字符，预计需要花费 12 分钟才能阅读完成。
1.HashMap 结构
HashMap 是存键值对 (key-value) 映射的数据结构，由数组 + 链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前 entry 的 next 指向 null）, 那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为 O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过 key 对象的 equals 方法逐一比对查找。通过下图可以对 HashMap 有一个直观的认识。
2.put 和 get 操作过程
- put 操作（JDK1.8 版）
1）计算 key 的 hash 值（计算过程下面会详细介绍）。
2）如果数组 table 是否为 null 或长度是否等于 0，条件为 true 时进行数据 table 扩容（实际执行 resize 方法）。
3）根据 hash 值计算 Value 将要存放的位置，即计算数组 table 索引（计算过程下面会详细讲）。
4）判断 table[i]是否是 null，如果是 null 直接进行 Value 插入。
5）如果 table[i]不是 null，接着判断 key 是否重复，如果重复直接进行覆盖插入。
6）如果 key 不重复，判断 table[i]是否是 TreeNode 类型，如果是红黑树，直接插入。
7）如果不是 TreeNode 就遍历链表，遍历时预判断插入新的 Value 后，链表长度是否大于等于 8。条件为 True 时执行链表转红黑树，然后插入 Value。
8）如果上面链表长度小于 8 执行链表插入。
9）最后检查数组是否需要扩容。
详细代码：
public V put(K key, V value) {
// 调用 putVal 方法
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; // 插入数组的桶 i 处的键值对节点
int n; // 底层数组的长度
int i; // 插入数组的桶的下标
// 刚开始 table 是 null 或空的时候，初始化个默认的 table；为 tab 和 n 赋值，tab 指向底层数组，n 为底层数组的长度
if ((tab = table) == null || (n = tab.length) == 0){n = (tab = resize()).length;
}
//(n - 1) & hash：根据 hash 值算出插入点在底层数组的桶的位置，即下标值；为 p 赋值，也为 i 赋值（不管碰撞与否，都已经赋值了）// 如果在数组上，没有发生碰撞，即当前要插入的位置上之前没有插入过值，则直接在此位置插入要插入的键值对
if ((p = tab[i = (n - 1) & hash]) == null){tab[i] = newNode(hash, key, value, null);// 插入的节点的 next 属性是 null
} else { // 发生碰撞，即当前位置已经插入了值
Node<K,V> e; // 中间变量吧，跟冒泡排序里面的那个中间变量似的，起到个值交换的作用
K k; // 同上
//hash 值相同，key 也相同，那么就是更新这个键值对的值。同 jdk 1.7
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){ // 注意在这个 if 内【e != null】e = p;// 这地方，e = p 他们两个都是指向数组下标为 i 的地方，在这 if else if else 结束之后，再把节点的值 value 给更新了
} else if (p instanceof TreeNode){ // 这个树方法可能会返回 null。//jdk 1.8 引入了红黑树来处理碰撞，上面判断 p 的类型已经是树结构了，e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 如果是，则走添加树的方法。} else { // 注意在这个 else 内，当为添加新节点时，【e ==】；更新某个节点时，就不是 null
for (int binCount = 0; ; ++binCount) {// 还未形成树结构，还是 jdk 1.7 的链表结构
// 差别就是 1.7: 是头插法，后来的留在数组上，先来的链在尾上；1.8: 是先来的就留在数组上，后来的链在尾上
// 判断 p.next 是否为空，同时为 e 赋值，若为空，则 p.next 指向新添加的节点，这是在链表长度小于 7 的时候
if ((e = p.next) == null) {
// 这个地方有个不好理解的地方：在判断条件里面，把 e 指向 p.next，也就是说现在 e =null 而不是下下一行错误的理解。// 这也就解释了更新的时候，返回 oldValue，新建的时候，是不在那地方返回的。p.next = newNode(hash, key, value, null);//e = p.next,p.next 指向新生成的节点，也就是说 e 指向新节点（错误）// 对于临界值的分析：// 假设此次是第六次，binCount == 6, 不会进行树变，当前链表长度是 7；下次循环。//binCount == 7，条件成立，进行树变，以后再 put 到这个桶的位置的时候，这个 else 就不走了，走中间的那个数结构的分叉语句啦
// 这个时候，长度为 8 的链表就变成了红黑树啦
if (binCount >= TREEIFY_THRESHOLD - 1){// -1 for 1st //TREEIFY_THRESHOLD == 8
treeifyBin(tab, hash);
}
break;// 插入新值或进行树变后，跳出 for 循环。此时 e 未重定向，还是指向 null，虽然后面 p.next 指向了新节点。// 但是，跟 e 没关系。}
// 如果在循环链表的时候，找到 key 相同的节点，那么就跳出循环，就走不到链表的尾上了。// e 已经在上一步已经赋值了，且不为 null, 也会跳出 for 循环，会在下面更新 value 的值
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){break;}
// 这个就是 p.next 也就是 e 不为空，然后，还没有 key 相同的情况出现，那就继续循环链表，// p 指向 p.next 也就是 e，继续循环，继续，e=p.next
p = e;
// 直到 p.next 为空，添加新的节点；或者出现 key 相等，更新旧值的情况才跳出循环。}
}
// 经过上面 if else if else 之后，e 在新建节点的时候，为 null；更新的时候，则被赋值。在树里面处理 putTreeVal（）同样如此，if (e != null) { // existing mapping for key// 老外说的对，就是只有更新的时候，才走这，才会直接 return oldValue
V oldValue = e.value;
//onlyIfAbsent 这个在调用 hashMap 的 put()的时候，一直是 false，那么下面更新 value 是肯定执行的
if (!onlyIfAbsent || oldValue == null){e.value = value;}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold){resize();
}
afterNodeInsertion(evict);
return null;3. 寻址过程（怎么由 key 值转换成数组下标）
借用网上的图，比较直观的看下这个转换过程：
第一步：key 值 —>32 位的哈希值
这个就是 key 值调用 hashCode() 函数，生成一个 32 位的哈希值。
第二步：32 位哈希值 —> 混合哈希值
这一步将 32 位哈希值的高 16 位与低 16 位做异或操作。为什么要这样做呢，因为下面还要进行一次 indexFoe() 操作截取低位信息（高 16 位信息将会丢失），这样做之后，低 16 位也能掺杂高 16 位的信息，高位的信息变相被保存下来了，可以增加随机性，减小冲突的可能性。
1,2 两步的操作在 put 函数源码中合并成了一行代码，如下：
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 第三步：混合哈希值 —> 数组下标
链表数组的初始长度是 16。显然这个 32 位的混合哈希值不能直接和链表数组直接对应起来，会照成大量冲突。这里采用了一次取模运算。HashMap 通过 hash 值与 length-1 (容器长度 -1)进行取模（%）运算。可能有人会问：明明源码中 indexFor() 方法进行的 按位与（&）运算，而非取模运算。实际上，HashMap 中的 indexFor() 方法就是在进行取模运算。利用位运算代替取模运算，可以大大提高程序的计算效率。位运算可以直接对内存数据进行操作，不需要转换成十进制，因此效率要高得多。需要注意的是，只有在特定情况下，位运算才可以转换成取模运算（当 b = 2^n 时，a % b = a & (b – 1)）。也是因此，HashMap 才将初始长度设置为 16，且扩容只能是以 2 的倍数（2^n）扩容。
4.HashMap 的安全性
在扩容操作时可能形成环形链表。
原因：
在 HashMap 扩容时，会改变链表中的元素的顺序，将元素从链表头部插入。（为了避免尾部遍历）。而环形链表就在这一时刻发生。添加元素时，如果超过阈值，就要进行扩容，如果两个元素同时添加，线程 A 和线程 B 可能同时扩容。线程 A 准备扩容时，线程 B 开始执行，扩容完毕，产生新的 hashMap. 此时 A—>Bnull 变成 B—>A null，先将 A 复制到新的 hash 表中，然后接着复制 B 到链头（A 的前边：B.next=A），本来 B.next=null，到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将 B.next=A，所以，这里继续复制 A，让 A.next=B，由此，环形链表出现：B.next=A; A.next=B。本来应该通过 A.next= B 来让 A 指向 null 的，但是线程 A 已经把 A.next 变成 B 的位置了。所有行成回环。
5.HashSet
简介：
HashSet 是一个没有重复元素的集合。
它是由 HashMap 实现的，不保证元素的顺序，而且 HashSet 允许使用 null 元素。
HashSet 是非同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装”set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：Set s = Collections.synchronizedSet(new HashSet(…));
伪代码实现：
public class MyHashSet<E> {
private HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public MyHashSet(){map = new HashMap<E,Object>();
}
public int size(){return map.size();
}
public void add(E e){map.put(e,PRESENT);
}
public void remove(E e){map.remove(e);
}
}