# 前言

关于这些集合的讲解，作者默认读者都知道该如何使用，所以不会从最基础的开始讲起，会直接跳过什么是映射关系，哈希值等概念的讲解。对于源码的解析也是最主要使用的那些方法。

# 一些概念

负载因子：集合容量都有上限，如果加入集合的数量超过一定允许值，集合就会扩容。负载因子就是衡量当前情况是否需要进行扩容的标准。

	// 如果数据占用率达到 75%，就会扩容，扩容会重新计算哈希值
	static final float DEFAULT_LOAD_FACTOR = 0.75f;

红黑树：一种数据结构，在 HashMap 里面查询效率是 logN，整棵树在插入数据时始终保持近似平衡（不是真的平衡）。JDK1.8 后就用红黑树代替 HashMap 里面的长度超过 8 的冲突链表了。

	static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
	// ....
	}

TreeNode 就是为了实现红黑树而设计的内部类。

HashMap 的初始容量是否应该设的比较大，在 JDK1.7 以前，HashMap 用的是冲突链表，HashMap 在迭代时，需要遍历整个数组和冲突链表。如果迭代频繁的话，就不宜将初始大小设的过大。

modCount ：集合只要可以使用迭代器，都需要 modCount 来记录修改次数。
实现 Map 接口：允许 key 和 value 都是 null 。

# 核心方法

有时会将 Java7 的方法拿出来和 Java8 作比较。

在 Java7 使用 Entry 代表数据节点，Java8 使用 Node，基本没有区别，都是 key ， value ， hash ， next 四个属性。 Node 只能适用于链表， TreeNode 用于红黑树。

# put()

put 方法重点也是在于得到哈希值，然后就是处理一下扩容，哈希冲突，链表转化红黑树等问题。

Java7 是先扩容再插入值，Java8 是先插入值再扩容。第一次 put 需要初始化一下 table 数组（从 null 初始化到默认容量 16 或者自定义容量），才能加入数据。

需要注意的是，如果两次使用 put 时，加入的 key 都是相同的，那么第二次的 value 应该覆盖第一次的，所以在 put 时也应该考虑到这一点，发生哈希冲突应该首先检查 Key 是不是相同的再进行下一步操作。

重点讲一下扩容操作：扩容时需要重新 hash ，并不是说要重新调用 hash 这个函数， Node(TreeNode) 节点之前就保存了 hash 值的。

如果 hash 值超过了容量 cap ，需要取余操作，因为 cap 都是 2 的指数，所以 cap-1 （最大下标）的低位就全是 1，取余操作就可以为： hash & (cap - 1) 。

所以一条冲突链表上的数据节点的哈希值并不一定都是相同的，可能是取余后才导致下标相同。所以在重新哈希的过程中，就需要对冲突链表拆分为两条链表，一条链表是哈希值本来就是当前下标，另一个是哈希值被取余了的（这条链表上也并不是哈希值都相同，只是取余后值都相同，5 和 7 被 2 取余值也相同嘛）。

因为每次扩容都是容量乘 2，所以后一条链表的新下标就是 i+cap 。

i<cap，(i+cap) % 2cap = i+cap 。

# get()

get 方法内部最重要的就是 hash() 得到其哈希值，然后再通过 equals() 找到对应的值。

理解了 put 的机制和哈希值取余原理后， get 分析就比较简单了。

计算 key 的 hash 值，根据 hash 值找到对应数组下标: hash & (length-1)。
判断数组该位置处的元素是否刚好就是我们要找的，如果不是，走第三步。
判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据，如果不是，走第四步。
遍历链表，直到找到相等 (== 或 equals) 的 key。

# HashSet

HashSet 使用了适配器模式，对 HashMap 进行了简单的包装，对 HashSet 的函数调用都会转换成合适的 HashMap 方法。这里提一下，不需要过多赘述。

	//HashSet 是对 HashMap 的简单包装
	public class HashSet<E>
	{
	......
	private transient HashMap<E,Object> map;//HashSet 里面有一个 HashMap
	// Dummy value to associate with an Object in the backing Map
	private static final Object PRESENT = new Object();
	public HashSet() {
	map = new HashMap<>();
	}
	......
	public boolean add(E e) {// 简单的方法转换
	return map.put(e, PRESENT)==null;
	}
	......
	}

# 参考

https://pdai.tech/md/java/collection/java-map-HashMap&HashSet.html
https://www.yuque.com/qingkongxiaguang/javase/syy4rz#b2b51e41
https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/6-HashSet and HashMap.md#get

Java基础