基于jdk1.8的HashMap(1)

ゝ一世哀愁。 2022-01-30 10:43 149阅读 0赞

参考博客：https://www.jianshu.com/p/8324a34577a0?utm\_source=oschina-app

***jdk1.8的HashMap底层是基于数组+链表+红黑树实现的。***  
类的定义如下：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

1.  HashMap中的数组采用Node类实现；该类的源码如下：

static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
            //1，重写了hashcode()方法
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    		//2，重写了equals方法；判断2个Entry是否相等，必须key和value都相等，才返回true 
            public final boolean equals(Object o) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

1.  红黑树节点类，HashMap中的红黑树节点采用TreeNode类实现

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
     		// 属性 = 父节点、左子树、右子树、删除辅助节点 + 颜色
            TreeNode<K,V> parent;  // red-black tree links
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;    // needed to unlink next upon deletion
            boolean red;
            TreeNode(int hash, K key, V val, Node<K,V> next) {
                super(hash, key, val, next);
            }
    		// 返回当前节点的根节点
            final TreeNode<K,V> root() {
                for (TreeNode<K,V> r = this, p;;) {
                    if ((p = r.parent) == null)
                        return r;
                    r = p;
                }
            }

1.  HashMap中的重要参数：

/** 
     3. 主要参数 同  JDK 1.7 
     4. 即：容量、加载因子、扩容阈值（要求、范围均相同）
       */
      // 1. 容量（capacity）： 必须是2的幂 & <最大容量（2的30次方）
      static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
      static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 =  2的30次方（若传入的容量过大，将被最大值替换）
    
      // 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度 
      final float loadFactor; // 实际加载因子
      static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子 = 0.75
    
      // 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量） 
      // a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
      // b. 扩容阈值 = 容量 x 加载因子
      int threshold;
    
      // 4. 其他
      transient Node<K,V>[] table;  // 存储数据的Node类型 数组，长度 = 2的幂；数组的每个元素 = 1个单链表
      transient int size;// HashMap的大小，即 HashMap中存储的键值对的数量
    
      /** 
     5. 与红黑树相关的参数
       */
       // 1. 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
       static final int TREEIFY_THRESHOLD = 8; 
       // 2. 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表
       static final int UNTREEIFY_THRESHOLD = 6;
       // 3. 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
       // 否则，若桶内元素太多时，则直接扩容，而不是树形化
       // 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
       static final int MIN_TREEIFY_CAPACITY = 64;

总结：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70]

1.  HashMap的4个构造函数：

/**
     7. 函数使用原型
      */
      Map<String,Integer> map = new HashMap<String,Integer>();
     /**
     8. 源码分析：主要是HashMap的构造函数 = 4个
     9. 仅贴出关于HashMap构造函数的源码
       */
    public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable{
        // 省略上节阐述的参数
      /**
         * 构造函数1：默认构造函数（无参）
         * 加载因子 & 容量 = 默认 = 0.75、16
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
        }
        /**
         * 构造函数2：指定“容量大小”的构造函数
         * 加载因子 = 默认 = 0.75 、容量 = 指定大小
         */
        public HashMap(int initialCapacity) {
            // 实际上是调用指定“容量大小”和“加载因子”的构造函数
            // 只是在传入的加载因子参数 = 默认加载因子
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
        /**
         * 构造函数3：指定“容量大小”和“加载因子”的构造函数
         * 加载因子 & 容量 = 自己指定
         */
        public HashMap(int initialCapacity, float loadFactor) {
            // 指定初始容量必须非负，否则报错  
             if (initialCapacity < 0)  
               throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity); 
            // HashMap的最大容量只能是MAXIMUM_CAPACITY，哪怕传入的 > 最大容量
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            // 填充比必须为正  
            if (loadFactor <= 0 || Float.isNaN(loadFactor))  
                throw new IllegalArgumentException("Illegal load factor: " +  loadFactor);  
            // 设置 加载因子
            this.loadFactor = loadFactor;
            // 设置 扩容阈值
            // 注：此处不是真正的阈值，仅仅只是将传入的容量大小转化为：>传入容量大小的最小的2的幂，该阈值后面会重新计算
            // 下面会详细讲解 ->> 分析1
            this.threshold = tableSizeFor(initialCapacity); 
        }
        /**
         * 构造函数4：包含“子Map”的构造函数
         * 即 构造出来的HashMap包含传入Map的映射关系
         * 加载因子 & 容量 = 默认
         */
        public HashMap(Map<? extends K, ? extends V> m) {
            // 设置容量大小 & 加载因子 = 默认
            this.loadFactor = DEFAULT_LOAD_FACTOR; 
            // 将传入的子Map中的全部元素逐个添加到HashMap中
            putMapEntries(m, false); 
        }
    }
       /**
         * 分析1：tableSizeFor(initialCapacity)
         * 作用：将传入的容量大小转化为：>传入容量大小的最小的2的幂
         * 与JDK 1.7对比：类似于JDK 1.7 中 inflateTable()里的 roundUpToPowerOf2(toSize)
         */
        static final int tableSizeFor(int cap) {
         int n = cap - 1;
         n |= n >>> 1;
         n |= n >>> 2;
         n |= n >>> 4;
         n |= n >>> 8;
         n |= n >>> 16;
         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

注：1，此处仅用于接受初始容量大小，加载因子，但仍无真正初始化哈希表，即初始化存储数组table；  
2，真正初始化哈希表是在第1次添加键值对时，即第一次调用put()时。

1.  向HashMap中添加数据：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 1]  
    添加数据的流程如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 2]

/**
         * 源码分析：主要分析HashMap的put函数
         */
        public V put(K key, V value) {
            // 1. 对传入数组的键Key计算Hash值 ->>分析1
            // 2. 再调用putVal（）添加数据进去 ->>分析2
            return putVal(hash(key), key, value, false, true);
        }

hash(key)操作：

/**
         * 分析1：hash(key)
         * 作用：计算传入数据的哈希码（哈希值、Hash值）
         * 该函数在JDK 1.7 和 1.8 中的实现不同，但原理一样 = 扰动函数 = 使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）
         * JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
         * JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算
         */
          // JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作  = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
          static final int hash(int h) {
            h ^= k.hashCode(); 
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
         }
          // JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
          // 1. 取hashCode值： h = key.hashCode() 
          // 2. 高位参与低位的运算：h ^ (h >>> 16)  
          static final int hash(Object key) {
               int h;
                return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
                // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
                // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
                // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
         }
       /**
         * 计算存储位置的函数分析：indexFor(hash, table.length)
         * 注：该函数仅存在于JDK 1.7 ，JDK 1.8中实际上无该函数（直接用1条语句判断写出），但原理相同
         * 为了方便讲解，故提前到此讲解
         */
         static int indexFor(int h, int length) {  
              return h & (length-1); 
              // 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）
              }

总结计算存放在数组table中的位置（即数组下标，索引）的过程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 3]  
计算示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 4]  
提问？  
1，为什么不直接采用经过hashcode()处理的哈希码作为存储数组table的下标位置？  
2，为什么采用哈希码与运算（&）（数组长度-1）计算数组下标？  
3，为什么在计算数组下标前，需对哈希码进行二次处理：扰动处理？  
***在回答这三个问题前，我们要记住一个核心思想：  
所有处理的根本目的都是为了提高存储key-value的数组下标位置的随机性&分布均匀性，尽量避免出现hash值冲突。即：对于不同key，存放的数组下标位置要尽可能不一样。***  
问题1：容易出现哈希码与数组大小范围不匹配的情况，即计算出来的哈希码可能不在数组大小范围内，从而导致无法匹配存储位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 5]  
问题2：计算出来的哈希码已经是比较均匀的了，但是长度太长不适合作为table的下标，数组长度为2的次幂，数组长度-1得到的二进制地位全为1，和哈希码做&运算得到的是哈希码的地位二进制值，作为存储的数组下标位置，从而解决了“哈希码与数组大小范围不匹配”的问题。  
具体解决方案描述如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 6]  
问题3：  
加大哈希码地位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突。  
具体描述：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70]: /images/20220130/5d1407bbe7cc462b9237a6cc7cbea3ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 1]: /images/20220130/2c1862995a0144469573b9b82ae170a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 2]: /images/20220130/6b4ba7ae90cd4aa38d2f309d6f79c9b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 3]: /images/20220130/4ddf07c5eb004792a266e25c881d9bb3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 4]: /images/20220130/43709219c2c546b6a755dedc7736cd2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 5]: /images/20220130/9282c61e9f744d7ea4486e6b8fa6e45b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 6]: /images/20220130/c437fd0e69e84bfb9179bcfb89d9c22a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 7]: /images/20220130/2981bffd4aa14a85b683cd771befc25d.png