HashMap深入探索.md

概述

昨天的写的博客已经到了最后一步,但是突然晴天霹雳,网络异常导致Halo后台重新登陆,日了狗了,今天使用本地Typero重新编辑。

Map是一个很重要的集合接口,而其中的HashMap更是重中之重,下面开始全面的总结。

一.HashMap概述

HashMap以键值对的形式存在,其中实际存储的是Entry对象,在HashMap中,根据hash算法来计算key-value的存储位置,并进行快速存取,特别的,HashMap只允许一条Entry的key为null(多条会覆盖),但是允许多条Entry的值为null。HashMap是Map接口的一个非同步实现,也就是他是线程不安全的。

image

同样,HashSet也是一个重要的集合类,是Set接口的重要实现,二至之间高度类似,HashSet也是采用hash算法来判断元素存储的位置,来进行快速存取,虽然HashMap和HashSet的接口实现规范不同,但是二者底层都是Hash机制存储机制,实际上HashSet的底层就是HashMap,全面学习HashMap,也有助于更好的对HashSet进行理解

这里需要区分的概念是,虽然都说容器里面存储的是Java对象,但是容器实际存储的是对象引用,这些引用指向实际的对象。


HashMap实现了Map接口,并且继承了AbstractMap类,其中Map接口定义了键值对映射规则,AbstractMap抽象类提供了Map接口的骨干实现,以减少HashMap中的工作量。

在HashMap在JDK中的定义为:

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

HashMap的构造函数

1.HashMap()

这个构造函数可以创建一个默认初始容量为16,默认负载因子为0.75的空HashMap

     /**
     * Constructs an empty HashMap with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {

        //负载因子:用于衡量的是一个散列表的空间的使用程度
        this.loadFactor = DEFAULT_LOAD_FACTOR; 

        //HashMap进行扩容的阈值,它的值等于 HashMap 的容量乘以负载因子
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

        // HashMap的底层实现仍是数组,只是数组的每一项都是一条链
        table = new Entry[DEFAULT_INITIAL_CAPACITY];

        init();
    }

2.HashMap(int initialCapacity, float loadFactor)

这个构造函数可以创建一个指定初始容量,指定负载因子的空HashMap

    /**
     * Constructs an empty HashMap with the specified initial capacity and load factor.
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //初始容量不能小于 0
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

        //初始容量不能超过 2^30
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

        //负载因子不能小于 0            
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // HashMap 的容量必须是2的幂次方,超过 initialCapacity 的最小 2^n 
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;   

        //负载因子
        this.loadFactor = loadFactor;

        //设置HashMap的容量极限,当HashMap的容量达到该极限时就会进行自动扩容操作
        threshold = (int)(capacity * loadFactor);

        // HashMap的底层实现仍是数组,只是数组的每一项都是一条链
        table = new Entry[capacity];
        init();
    }

3.HahsMap(int initialCapacity)

可以创建一个指定初始容量,默认负载因子为0.75的空HashMap

    // Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75)
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);  // 直接调用上述构造函数
    }

4.HashMap(Map<? extends K,? extends V> m)

这个构造函数可以构造一个和指定Map具有相同映射的HashMap

    // Constructs a new HashMap with the same mappings as the specified Map. 
    // The HashMap is created with default load factor (0.75) and an initial capacity
    // sufficient to hold the mappings in the specified Map.
    public HashMap(Map<? extends K, ? extends V> m) {

        // 初始容量不小于 16 
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }

有构造函数源码可知,新构造的HashMap可以保证最小初始容量为16,默认负载因子为0.75

初始容量和负载因子是影响HashMap性能的两个重要参数,其中初始容量表示HashMap中桶的数量,我们可以发现,上面每一个构造方法均有: table = new Entry[capacity];初始容量表示的就是这个table数组的大小,另外一个参数负载因子可以表示哈希表的空间利用率,负载因子越大,空间利用率越高,但是太大也不好,这样会使查找效率低下,所以源码中采用一个折衷的0.75,这是在时间上和空间上的折衷,一般情况下我们使用这个就可以了,不必修改。

这里插播一段哈希表和HashMap的区别

哈希表是一种数据结构,不仅Java中有,C语言里面也有,而HashMap是基于哈希表实现的一个Java集合类

二.HashMap 的数据结构

哈希:

Hash就是把任意长度的输入,根据哈希算法,变成固定长度的输出,这个输出值就是哈希值,这是一种带有压缩性质的映射。


哈希的应用:哈希表

我们都知道,数组的特点是查找容易,增删困难,链表的特点是查找困难,增删容易,那么是否存在一种数据结构兼顾二者的优点呢?那就是哈希表。哈希表有很多种实现方法,其中最经典的就是拉链法,如图所示:

image

左边是一个数组,右面是链表,哈希表种存储的每一个元素都存在一个指向下一个元素的指针,用于元素之间的连接,我们根据元素的自身特征将元素分配到不同的数组中去,使用的方法就是哈希算法。

使用哈希表有两个关键点:

  1. 哈希算法 的选择
  2. 碰撞处理,一种是拉链法,就是上面使用的,另一种是开放地址法,当出现元素冲突时,根据相关的函数来判断要存储的数组下标,这里只是做一个简单的介绍,不详细展开

创建数组的操作:table = new Entry[capacity];

Entry是哈希表的基石,是存储元素的具体形式

源码如下:

static class Entry<K,V> implements Map.Entry<K,V> {

    final K key;     // 键值对的键
    V value;        // 键值对的值
    Entry<K,V> next;    // 下一个节点
    final int hash;     // hash(key.hashCode())方法的返回值

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {     // Entry 的构造函数
        value = v;
        next = n;
        key = k;
        hash = h;
    }

    ......

}

三.HashMap的快速存取

1.HashMap 的存储实现

在HashMap中,键值对的存储是通过put(Key,Value)方法实现的,源码如下:

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with key, or null if there was no mapping for key.
     *  Note that a null return can also indicate that the map previously associated null with key.
     */
    public V put(K key, V value) {

        //当key为null时,调用putForNullKey方法,并将该键值对保存到table的第一个位置 
        if (key == null)
            return putForNullKey(value); 

        //根据key的hashCode计算hash值
        int hash = hash(key.hashCode());             //  ------- (1)

        //计算该键值对在数组中的存储位置(哪个桶)
        int i = indexFor(hash, table.length);              // ------- (2)

        //在table的第i个桶上进行迭代,寻找 key 保存的位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {      // ------- (3)
            Object k;
            //判断该条链上是否存在hash值相同且key值相等的映射,若存在,则直接覆盖 value,并返回旧value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;    // 返回旧值
            }
        }

        modCount++; //修改次数增加1,快速失败机制

        //原HashMap中无该映射,将该添加至该链的链头
        addEntry(hash, key, value, i);            
        return null;
    }

首先判断key是否为null,如果是,调用putForNullkey方法进行特殊的处理,否则根据key的哈希值,通过哈希算法,判断元素在table数组中的存储下标,如果table数组在当前下标中有元素,那么比较key是否相同,如果相同,使用使用新的value取代旧的value,否则将该元素保存在链表头部(使用头插法),此外,若table在该下标出没有元素,那么直接保存,这个过程还有几个值得继续探究之处:

1). 对NULL键的特别处理:putForNullKey()

我们直接看其源码:

    /**
     * Offloaded version of put for null keys
     */
    private V putForNullKey(V value) {
        // 若key==null,则将其放入table的第一个桶,即 table[0]
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {   
            if (e.key == null) {   // 若已经存在key为null的键,则替换其值,并返回旧值
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;        // 快速失败
        addEntry(0, null, value, 0);       // 否则,将其添加到 table[0] 的桶中
        return null;
    }

通过上述源码我们可以清楚知到,HashMap 中可以保存键为NULL的键值对,且该键值对是唯一的。若再次向其中添加键为NULL的键值对,将覆盖其原值。此外,如果HashMap中存在键为NULL的键值对,那么一定在第一个桶中。

2). HashMap 中的哈希策略(算法)

在上述的 put(key,vlaue) 方法的源码中,我们标出了 HashMap 中的哈希策略(即(1)、(2)两处),hash() 方法用于对Key的hashCode进行重新计算,而 indexFor() 方法用于生成这个Entry对象的插入位置。当计算出来的hash值与hashMap的(length-1)做了&运算后,会得到位于区间[0,length-1]的一个值。特别地,这个值分布的越均匀, HashMap 的空间利用率也就越高,存取效率也就越好。

下面是hash()方法源码,都是纯数学计算,啥也看不懂:

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. 
     * 
     * Note: Null keys always map to hash 0, thus index 0.
     */
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

这个方法用于对key.hashCode进行重新计算hash值,为什么要重新来一次呢?为了防止质量低下的hashCode()函数实现,在自定义对象的时候,我么需要重写hashCode()方法,由于我们能力一般,水平有限,很可能使要存储到HashMap中的元素都聚集在一个桶中,造成效率的下降。

下面是indexFor()方法的源码:

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);  // 作用等价于取模运算,但这种方式效率更高
    }

得到哈希值之后,通过这个方法可以判断出要存储到数组中的哪个下标中,为了能够使元素平均分布,最常用的方法就是取模,但是由于取模的效率比较低,JDK中进行优化的地方就是使用位运算来代替取模运算。

总是上面两个方法的作用只有一个:让元素均匀的分配到数组中,以便充分利用空间。

3). HashMap 中键值对的添加:addEntry()

直接上源码:

    /**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     * 
     * 永远都是在链表的表头添加新元素
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {

        //获取bucketIndex处的链表
        Entry<K,V> e = table[bucketIndex];

        //将新创建的 Entry 链入 bucketIndex处的链表的表头 
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

        //若HashMap中元素的个数超过极限值 threshold,则容量扩大两倍
        if (size++ >= threshold)
            resize(2 * table.length);
    }

由此可以分许出,增加新的Entry对象的时候,采用的是头插法。此外,若HashMap中的元素超过了threshold(阙值),那么自动进行扩容,一般为二倍。

4). HashMap 的扩容:resize()和重哈希transfer()


2.HashMap的读取实现

读取操作比较简单,只需要key的哈希值就可以定位到具体的桶,返回这个key对应的value即可,源码如下:

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        // 若为null,调用getForNullKey方法返回相对应的value
        if (key == null)
            // 从table的第一个桶中寻找 key 为 null 的映射;若不存在,直接返回null
            return getForNullKey();  

        // 根据该 key 的 hashCode 值计算它的 hash 码 
        int hash = hash(key.hashCode());
        // 找出 table 数组中对应的桶
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //若搜索的key与查找的key相同,则返回相对应的value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

其中,针对键为NULL的键值对,HashMap 提供了专门的处理:getForNullKey(),其源码如下:

 /**
     * Offloaded version of get() to look up null keys.  Null keys map
     * to index 0.  This null case is split out into separate methods
     * for the sake of performance in the two most commonly used
     * operations (get and put), but incorporated with conditionals in
     * others.
     */
    private V getForNullKey() {
        // 键为NULL的键值对若存在,则必定在第一个桶中
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        // 键为NULL的键值对若不存在,则直接返回 null
        return null;
    }

因此,调用HashMap的get(Object key)方法后,如果返回的值是null,那么就存在两种可能:

  1. 这个key对应的值的就是null
  2. HashMap中不存在key为null的键值对,上面源码的最后一行直接返回null

四.HashMap 的底层数组长度为何总是2的n次方?

直接上结论:

  1. 不同的哈希值发生碰撞的概率比较小,这样数据在table数组中分配更加均匀,空间利用率高,也有利于查找
  2. h&(length - 1) 就相当于对length取模,而且在速度、效率上比直接取模要快得多,即二者是等价不等效的,这是HashMap在速度和效率上的一个优化。

对于取余运算,我们首先想到的是:哈希值%length = bucketIndex。但当底层数组的length为2的n次方时, h&(length - 1) 就相当于对length取模,而且速度比直接取模快得多,这是HashMap在速度上的一个优化。除此之外,HashMap 的底层数组长度总是2的n次方的主要原因是什么呢?
现在假设length的长度分别为16和15,h分别为5,6,7:

image

在上面的位运算中我们可以看到,当length=15,h为6,7,时,运算的结果6,7居然分配在同一个桶中,通过更多的数据我们来得出结论:

image

 从上面的图表中我们可以看到,当 length 为15时总共发生了8次碰撞,同时发现空间浪费非常大,因为在 1、3、5、7、9、11、13、15 这八处没有存放数据。这是因为hash值在与14(即 1110)进行&运算时,得到的结果最后一位永远都是0,即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。这样,空间的减少会导致碰撞几率的进一步增加,从而就会导致查询速度慢。
 而当length为16时,length – 1 = 15, 即 1111,那么,在进行低位&运算时,值总是与原来hash值相同,而进行高位运算时,其值等于其低位值。所以,当 length=2^n 时,不同的hash值发生碰撞的概率比较小,这样就会使得数据在table数组中分布较均匀,查询速度也较快。

五.后记

HashMap 的直接子类LinkedHashMap继承了HashMap的所用特性,并且还通过额外维护一个双向链表保持了有序性, 通过对比LinkedHashMap和HashMap的实现有助于更好的理解HashMap。下一篇博客里面再深入探讨LinkedHashMap。

最后涉及到知识产权的问题。本文参考自博客https://blog.csdn.net/justloveyou_/article/details/62893086,感谢优秀的原博主!