JDK源码分析－－HashMap深入理解

野性酷女 2022-03-25 01:58 361阅读 0赞

### **一、实现原理** ###

以**JDK1.7**源码为例进行分析

**（一）Hashing的概念**

将字符串转换成固定长度（一般是更短的长度）的数值或索引值的方法，也称为散列法或哈希法。常用于数据库中建索引，或是用于各种加解密算法中。

完成转换功能的函数一般称为哈希函数，哈希函数设计的好坏将直接影响到哈希表的优劣。

**（二）哈希表**

可高效进行增加、删除、查找等操作的数据结构，不考虑哈希冲突的情况下，仅需要一次定位即可完成，时间复杂度为O(1)。

哈希表的主干是数组，在数组中根据下标查找某个元素，一次定位即可达到，正是利用这种特性，达到高效的操作。

**（三）哈希冲突**

两个不同元素，通过hashing后，有极小的概率得到相同的数值（实际的存储地址），对这个存储地址进行插入操作时，发现已经被其他元素占用，这就是所谓的哈希冲突，也叫哈希碰撞。

好的哈希函数会尽量保证计算简单和散列地址分布均匀，但也不能保证得到的存储地址绝对没有冲突。

HashMap解决哈希冲突采用的是链地址法，即数组+链表的方式。

**（四）原理分析**

1、HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。数组是主体，链表是为了解决哈希冲突。如果定位到的数组位置不含链表（Entry的指针指向null），此时操作仅需一次寻址即可；如果定位到的位置包含链表，则遍历链表，通过key对象的equals方法逐一对比查找，此时时间复杂度为O(n)。因此HashMap中出现链表越少，其性能越好。

**结构图如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAxODgxNzg_size_16_color_FFFFFF_t_70][]

**Entry代码片断及解析：**

static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;//final
            V value;
            Entry<K,V> next;//指针（也可以叫引用）
            int hash;//key对应的hash值
    Entry(int h, K k, V v, Entry<K,V> n) {
    	……//略，构造方法体
    }
    public final K getKey() {
    return key;
    }
    public final V getValue() {
        return value;
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
           if (!(o instanceof Map.Entry))
              return false;
           Map.Entry e = (Map.Entry)o;
           Object k1 = getKey();
           Object k2 = e.getKey();
           if (k1 == k2 || (k1 != null && k1.equals(k2))) {
              Object v1 = getValue();
              Object v2 = e.getValue();
              if (v1 == v2 || (v1 != null && v1.equals(v2)))
                 return true;
            }
            return false;
         }
    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }
    public final String toString() {
        return getKey() + "=" + getValue();
    }
    
    }

上面equals方法中， if 判断k1 == k2、v1 == v2这2处，旨在说明“null==null”返回true，在此进行说明，并且我们在平时编码中也应该注意这一点。

**（五）几个重要属性（字段）**

1、static final int DEFAULT\_INITIAL\_CAPACITY = 1 << 4; // aka 16

默认初始容量，必须是2的次方

2、static final float DEFAULT\_LOAD\_FACTOR = 0.75f;

默认装载因子，大小为0.75。

3、static final Entry<?,?>\[\] EMPTY\_TABLE = \{\};

默认初始化的空表Entry

4、transient Entry<K,V>\[\] table = (Entry<K,V>\[\]) EMPTY\_TABLE;

HashMap实际存储数据的表，长度必须总是2的幂，默认为空表

5、transient int size;

实际的键值对数量

6、int threshold;

扩容临界值：下一个要调整大小的值(总容量\*装载因子)，当键值对数量size达到此值时（size >= threshold），对容量进行扩容操作（resize(2 \* table.length)）

**特此说明：**

上述对“临界值”的描述看似正确，而实际上并非如此。假设当前容量为8，装载因子0.75，则threshold＝6，当size为6时会对HashMap进行扩容吗？经实验证明，不一定会。

查看源码，在put操作时扩容的条件为“(size >= threshold) && (null != table\[bucketIndex\])”，也就是说还需要同时满足后面条件，那么bucketIndex又是什么呢？直译为“桶的下标”，即下一个存放Entry的桶的位置，这个位置的获取来自方法“indexFor”，如下：

static int indexFor(int h, int length) {//hash值，table的总容量
        return h & (length-1);
    }

length-1的二进值低位都是1，h & (length-1)的与运算，实质就是h% (length-1)，只要hash不相等，理想情况下，需要容量被全部占用时才会扩容。

简而言之，仅当size >= threshold且发生Hash值%(length-1)冲突（或修改已存在的值或）时，才会进行扩容。

关于扩容的验证，请参见文章：[https://blog.csdn.net/u010188178/article/details/86527792][https_blog.csdn.net_u010188178_article_details_86527792]

7、final float loadFactor;

装载因子，当使用容量达到总容量\*装载因子容量时，可能会对集合进行扩容操作；如果实例化时不指定装载因子的大小，其初始化为默认大小0.75。

**（六）构造方法**

**1、直接构造（指定容量+装载因子）**

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
        initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
               loadFactor);
        this.loadFactor = loadFactor;//装载因子赋值
        threshold = initialCapacity;//扩容临界值赋值
         init();                               
    }

此处threshold赋值为传入的初始值，比如传入5，初始化时，threshold＝5，而在第一次put操作时，通过5计算HashMap的初始容量应该为8（2的冥且>=5），再通过装载因子（默认0.75）计算出扩容临界值threshold＝6。

并且实例化时并没有为数组table分配内存空间，而是在put第一个元素时才构建table数组。

**2、直接构造（指定容量）**

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

**3、无参构造**

public HashMap() {
         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

**4、通过实现Map接口的对象构造**

public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                   DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        inflateTable(threshold);
        putAllForCreate(m);
     }

### **二、JDK1.8的主要改动** ###

**1、数据结构**

JDK1.7使用数组+链表的数据结构，而1.8使用数组+链表+红黑树。

如果插入key的hashcode相同，使用链表方式解决冲突，当链表长度达到8个（默认设置的阈值）时，调用treeifyBin函数，将链表转换为红黑树。红黑树的时间复杂度为O(log n)，即put/get最坏时间复杂度为O(log n)。

**2、数据存储机制**

发生hash冲突时，JDK1.7采用链地址法+头插法，而1.8采用链地址法+尾插法+红黑树。

头插入法插入效率较高，但容易出现逆序且环形链表死循环问题，尾插法可避免此问题。

### **三、HashMap使用误区** ###

1、如果使用的HashMap容量可能会很大，实例化时设置初始容量，比如new HashMap(2048)。

这样建议的理由无非就是说，当容器持续增长时，可能会导致其频繁扩容，影响性能。而实际生产中是否有这样的必要呢？先做个实验。

JDK1.7环境下，插入元素数量**16777216**，其对应默认临界值为**12582912**

（1）设置初始值的情况

public static void testHashMap(){
        //插入元素数量16777216，其对应默认临界值为12582912
    	int size = 16777216;
    	long start = System.currentTimeMillis();
    	Map<Integer, Integer> map2 = new HashMap<>(12582912);
    	for(int i=0; i<size; i++){
    		map2.put(i, i);
    	}
    	long end = System.currentTimeMillis();
    	System.out.println("设置初始值耗时："+(end-start));
    }

以上情况需要扩容一次，运行时长：**18270**（多次运行，时长18000ms左右）

（2）不设置初始值的情况

public static void testHashMap1(){
        //插入元素数量16777216，其对应默认临界值为12582912
        int size = 16777216;
        long start = System.currentTimeMillis();
    	Map<Integer, Integer> map = new HashMap<>();
    	for(int i=0; i<size; i++){
    		map.put(i, i);
    	}
    	long end = System.currentTimeMillis();
    	System.out.println("不设置初始值耗时："+(end-start));
    }

以上情况需要扩容很多次，运行时长：**14057**（多次运行，时长在此值左右）

现在将JDK环境修改为1.8，再次测试，2次运行结果分别如下：

设置初始值耗时：**20866**

不设置初始值耗时：**17707**

**因此**：

**        在JDK1.7、1.8环境下，对较大容量HashMap设置初始值（实质上为扩容临界值），并不会对实际效率有所提高。**

2、我在查看同事的源码时经常看到**new HashMap(4)**,**new HashMap(6)**之类的写法。

我肯定他们的初衷是在知道容器存放总量的情况下，设置初始容量以减少内存消耗。但这里需要注意的是：

**  入参并不是容器的初始容量，而是扩容临界值。在实例化HashMap时，并不会初始化其容量，此时默认容量为0；在执行第一次put操作时，默认装载因子为0.75的情况下，其初始容量由传入的参数除以0.75，得到的值为N，再计算2的冥得到Y，保证Y>=N且Y最接近N，此时的Y才是HashMap的初始容量；用Y乘以0.75得到真实扩容临界值。**

### **四、细枝末节** ###

1、HashMap可以接受null键值和值，而Hashtable则不能

2、HashMap是非synchronized

3、String、Integer这样的包装类适合作为key。它们由final修饰，具有不可变性；内部重写了equals()、hashCode()方法  ，具有计算准确性，有效减少了发生Hash碰撞的机率。

## **以上内容为个人分析，如有不足之处，希望大家能批评指正！** ##

# #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAxODgxNzg_size_16_color_FFFFFF_t_70]: /images/20220325/5ea2fe61aace42afa2ec21f7da16297d.png
[https_blog.csdn.net_u010188178_article_details_86527792]: https://blog.csdn.net/u010188178/article/details/86527792