【JDK源码】HashSet、HashMap（一）

HashSet

HashSet实现原理

由于set是基于map实现的 这里主要介绍map

• 是基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

HashSet 中数据是如何保证不重复的

• HashSet 源码分析
  通过上面的 HashSet 源码我们可以看到，在 HashSet 的构造函数中，它创建了 HashMap
  在 HashSet 的 add() 方法中是调用了 HashMap 的 put() 方法的，要 put 的 key 是要添加到 HashSet 中的元素，而value 则是一个静态常量值 PRESENT
• 当向 HashSet 中添加元素时，如果此时添加一个 HashSet 已存在的元素时
  此时肯定会发生 Hash 冲突的
  那么接下来，会进行该元素的 equals() 方法或 == 的比较，如果它们的 equals() 方法或 == 比较的结果为 true 即相等，则 HashMap 会使用新 value 值覆盖旧 value 值
  而到此时，HashMap 的 put() 方法的返回值为一个 oldValue，故而 HashSet 的 add 方法的返回值为 false，即添加一个已存在的元素时会失败

 public boolean add(E e) {
    return map.put(e, PRESENT)==null;}

HashMap

• 先看成员变量

//HashMap初始容量大小(16) 并且是2次幂 在我们第一次put值得时候才会给到初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子 当容量被占满0.75时就需要reSize扩容 
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表长度到8，就转为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 树大小为6，就转回链表
static final int UNTREEIFY_THRESHOLD = 6;
//链表转变成树之前，还会有一次判断，只有数组长度大于 64 才会发生转换
static final int MIN_TREEIFY_CAPACITY = 64;

• 为什么是2次幂？

(n-1)&hash等效于hash % n ,在计算元素该存放的位置的时候，用到的算法是将元素的hash与当前map长度-1进行与运算，

n-1是为了让低位都等于1，低位都为1与哈希值相与， 高位都为0与哈希值高位相与自然也等于0， 所以与出来的范围在 0-（n-1）

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

• 什么是加载因子？为什么是0.75

加载因子也叫扩容因子或负载因子，用来判断什么时候进行扩容的，假如加载因子是 0.5，HashMap 的初始化容量是 16，那么当 HashMap 中有 16*0.5=8 个元素时，HashMap 就会进行扩容。

那加载因子为什么是 0.75 而不是 0.5 或者 1.0 呢？

这其实是出于容量和性能之间平衡的结果：

当加载因子设置比较大的时候，扩容的门槛就被提高了，扩容发生的频率比较低，占用的空间会比较小，但此时发生 Hash 冲突的几率就会提升，因此需要更复杂的数据结构来存储元素，这样对元素的操作时间就会增加，运行效率也会因此降低；
而当加载因子值比较小的时候，扩容的门槛会比较低，因此会占用更多的空间，此时元素的存储就比较稀疏，发生哈希冲突的可能性就比较小，因此操作性能会比较高。
所以综合了以上情况就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。

put方法

• put方法是map中核心方法之一，所以一步一步分析

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//......
static final int hash(Object key) {
    //根据参数，产生一个哈希值int h;//这里为什么不直接返回key.hashCode() 还要与 h>>>16来异或呢？return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//......
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; //临时变量，存储"哈希表"——由此可见，哈希表是一个Node[]数组Node<K,V> p;//临时变量，用于存储从"哈希表"中获取的Nodeint n, i;//n存储哈希表长度；i存储哈希表索引if ((tab = table) == null || (n = tab.length) == 0)//判断当前是否还没有生成哈希表//这里就是默认初始化容量为16n = (tab = resize()).length;//resize()方法用于生成一个哈希表，默认长度：16，赋给nif ((p = tab[i = (n - 1) & hash]) == null)//(n-1)&hash等效于hash % n，转换为数组索引tab[i] = newNode(hash, key, value, null);//此位置没有元素，new一个node节点直接存储else {
    //否则此位置已经有元素了Node<K,V> e; K k;if (p.hash == hash &&   // 如果有元素并且哈希值一样 key值也一样就会覆盖//特殊 BB 和 Aa的哈希值一样 所以不能之比较hash值，为什么一样这里要取决于String重写hashCode的算法((k = p.key) == key || (key != null && key.equals(k))))//判断哈希值和equalse = p;//将哈希表中的元素存储为eelse if (p instanceof TreeNode)//判断是否为"树"结构//将节点变为树节点e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {
    //排除以上两种情况，将其存为新的Node节点for (int binCount = 0; ; ++binCount) {
    //遍历链表if ((e = p.next) == null) {
    //找到最后一个节点p.next = newNode(hash, key, value, null);//产生一个新节点，赋值到链表if (binCount >= TREEIFY_THRESHOLD - 1) //判断链表长度是否大于了8treeifyBin(tab, hash);//树形化break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))//跟当前变量的元素比较，如果hashCode相同，equals也相同 也就是在链表途中也有相同的key 也会覆盖break;//结束循环p = e;//将p设为当前遍历的Node节点}}if (e != null) {
     // 如果存在此键V oldValue = e.value;//取出valueif (!onlyIfAbsent || oldValue == null)e.value = value;//设置为新valueafterNodeAccess(e);//空方法，什么都不做return oldValue;//返回旧值}}++modCount;if (++size > threshold) // 如果大于数组的0.75算法将会扩容resize();afterNodeInsertion(evict);return null;
}

• 分析完put方法后发现许多值得思考的问题

  • 获取hash值为什么要与h>>>16来异或呢？
  • Node[]数组是怎样的一个数组呢？
  • 树化底层是怎么样的呢？
  • 扩容底层又是怎么样的呢？

获取hash值为什么要与h>>>16来异或呢？

• h >>> 16是什么，有什么用?
  h是hashcode。h >>> 16是用来取出h的高16(也就是将二进制的h整体向右移16位，高位用0代替)，(>>>是无符号右移) 如下展示：

0000 0100 1011 0011  1101 1111 1110 0001>>> 16 0000 0000 0000 0000  0000 0100 1011 0011

• 为什么 h = key.hashCode()) 与 (h >>> 16) 异或

^异或运算：相同置0，不同置1
0^1 = 1
1^0 = 1
1^1 = 0
0^0 = 0
可以看到0和1的概率都为1/2  & 与运算：两个同时为1，结果为1，否则为0
1&1 = 1,
1&0 = 0,
0&0 = 0,
0&1= 0
可以看到结果偏向0| 或运算： 只要有1 结果就为1
1|1 = 1,
1|0 = 1,
0|0 = 0,
0|1 = 1
可以看到结果偏向1

• • 保证高16位也参与计算， 我们知道int占4字节 32位，16是中位数
  • 因为大部分情况下，都是低16位参与运算，高16位也参与运算可以减少hash冲突
• 为什么用 ^ 而不用 & 和 |
  因为&和|都会使得结果偏向0或者1 ,并不是均匀的概念,所以用^。
• 归根结底是为了让下标更加散列,减少hash碰撞次数

Node[]数组是怎样的一个数组呢？

• 其实就是map内置的一个类 可以看到这个类很常规 就不细说了

树化底层是怎么样的呢？

final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) {
    int n, index; HashMap.Node<K,V> e;//判断数组长度是否小于最小表容量，如果是则不会树化，会通过扩容来增加散列，减小链表长度if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {
    HashMap.TreeNode<K,V> hd = null, tl = null;do {
    HashMap.TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {
    p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}
}

• 从树化底层得知 并不是链表长度大于8就树化

扩容底层有又是怎么样的呢？

 final Node<K,V>[] resize() {
    // 申明对象Node<K,V>[] oldTab = table;// 记录当前node数组的长度int oldCap = (oldTab == null) ? 0 : oldTab.length;// 记录负载值int oldThr = threshold;int newCap, newThr = 0;// 如果当前map有值if (oldCap > 0) {
    // 如果这个存放的数据已经接近int最大值，那么就放弃了，不扩容了if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;return oldTab;}// 正常扩容 进行原始长度*2扩容else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 新容量 = oldCap << 1newThr = oldThr << 1; // double threshold}// 初始化else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 初始化else {
                   // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {
    float ft = (float)newCap * loadFactor;// 新的阈值 = 0.75 * newCapnewThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 新的最大允许元素数量值threshold = newThr;@SuppressWarnings({
    "rawtypes","unchecked"})// 新的数组 容量是原来的 2 倍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，还是原来的位置if ((e.hash & oldCap) == 0) {
    if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {
    // 如果是1则放到 1 + oldcap的位置if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {
    loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {
    hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}