Hashmap源码阅读

Posted1 by 呼延十 on October 16, 2018 Hot:

HashMap是什么想必大家都是知道的,日常开发中经常使用,而且常驻于笔试题目及面试中,那么今天将从源码的角度来深入理解一下HashMap。

PS:本文以下分析基于jdk1.7,1.8的改动会在文后总结。

1.什么是HashMap?

HashMap是基于哈希表的Map接口实现,是一个key-value型的数据结构。他在性能良好的情况下,存取的时间复杂度皆为O(1).

要知道数组的获取时间复杂度为O(1),但是他的插入时间复杂度为O(n).

那么HashMap是怎么做到的呢?

看一下HashMap的属性:


//内部数组的默认初始容量,作为hashmap的初始容量,是2的4次方,2的n次方的作用是减少hash冲突
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

 //默认的最大容量
 static final int MAXIMUM_CAPACITY = 1 << 30;

 //默认负载因子,当容器使用率达到这个75%的时候就扩容
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

 /**
  *当数组表还没扩容的时候,一个共享的空表对象
  */
 static final Entry<?,?>[] EMPTY_TABLE = {};

 //内部数组表,用来装entry,大小只能是2的n次方。
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

 //存储的键值对的个数
 transient int size;

 /**
  * 扩容的临界点,如果当前容量达到该值,则需要扩容了。
  * 如果当前数组容量为0时(空数组),则该值作为初始化内部数组的初始容量
  */
 int threshold;

 //由构造函数传入的指定负载因子
 final float loadFactor;

 //Hash的修改次数
 transient int modCount;

 //threshold的最大值
 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

 //计算hash值时候用,初始是0
 transient int hashSeed = 0;

 //含有所有entry节点的一个set集合
 private transient Set<Map.Entry<K,V>> entrySet = null;

 private static final long serialVersionUID = 362498820763181265L;

注释已经比较完备,便不再做过多的说明。

由里面的

可以看出,HashMap的主体其实是个数组,是Entry这个内部类的数组。

Entry内部类是啥呢?

这是Entry内部类的属性,可以看出这是个单链表的节点,因为它内部有指向下一个节点的next。

那么就相当明了了,HashMap内部是一个数组,数组的每一个节点是一个链表的头结点,也就是拉链式。

2.HashMap具体是怎么做到的

对于HashMap来说,日常使用的就是两个方法,get(),put().

我们首先看put.

 public V put(K key, V value) {

     //判断当前HashMap是否为空,为空则初始化
     if (table == EMPTY_TABLE) {
         inflateTable(threshold);
     }
     //判断传入的key是否为null,为null则放到table[0]的位置或者其链表上
     if (key == null)
         return putForNullKey(value);

      //计算key的hash值      
     int hash = hash(key);
     //计算key存放在数组中的下标
     int i = indexFor(hash, table.length);
     //遍历该位置上的链表,如果存在key值和传入的key值相等,则替换掉旧值
     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
         Object k;
         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
             V oldValue = e.value;
             e.value = value;
             e.recordAccess(this);
             return oldValue;
         }
     }

     modCount++;
     //如果没有这个值,则添加一个Entry
     addEntry(hash, key, value, i);
     return null;
 }
 /**
  * Offloaded version of put for null keys
  */
 private V putForNullKey(V value) {
     for (Entry<K,V> e = table[0]; e != null; e = e.next) {
         if (e.key == null) {
             V oldValue = e.value;
             e.value = value;
             e.recordAccess(this);
             return oldValue;
         }
     }
     modCount++;
     addEntry(0, null, value, 0);
     return null;
 }

 void addEntry(int hash, K key, V value, int bucketIndex) {
      //判断是否需要扩容,是的话进行扩容
     if ((size >= threshold) && (null != table[bucketIndex])) {
         resize(2 * table.length);
         hash = (null != key) ? hash(key) : 0;
         bucketIndex = indexFor(hash, table.length);
     }
     //新建一个Entry
     createEntry(hash, key, value, bucketIndex);
 }

void createEntry(int hash, K key, V value, int bucketIndex) {
     //将传入的key-value放在链表的头部,并且指向原链表的头。
     Entry<K,V> e = table[bucketIndex];
     table[bucketIndex] = new Entry<>(hash, key, value, e);
     size++;
 }

代码中添加了一些注释,大概是可以看懂的,那么这里总结一下流程。

  1. 判断当前hashMap是否为空,为空则初始化。
  2. 判断传入的key是否为null,为null的话直接放到数组的0位置或者0位置的链表上。
  3. key不为空,计算key的hash值。
  4. 计算key在数组中应该存储的下标
  5. 遍历数组在该下标的链表,如果找到已经存在的key和传入的key相等,则用新的value替换旧的value。
  6. 没找到,则在数组的i位置添加一个Entry。
  7. 添加Entry时,先判断是否需要扩容,需要的话扩容,不需要的话下一步。
  8. 创建一个Entry,创建的方法是将新传入的key-value放在数组i位置的链表头结点,并且指向原链表头结点。

接下来是get()方法。


public V get(Object key) {
    //key为null,则在数组0位置寻找值
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

final Entry<K,V> getEntry(Object key) {
    //如果hashMap中存的值数量为0,则返回null
    if (size == 0) {
        return null;
    }
    //计算key的hash值
    int hash = (key == null) ? 0 : hash(key);

    //用indexof函数算出数组下标
    //在该下标位置上的链表中遍历,寻找与传入key相等的key,否则返回null
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

同样这里总结一下流程:

  1. 判断key==null,如果为null,在数组0位置寻找。
  2. key!=null,判断hashMap中存的值数量是否为0,如果为0直接返回null。
  3. 计算key的hash值。
  4. 计算key应该在数组中的下标。
  5. 遍历Entry数组在该位置的链表,寻找与传入key相等的key,并返回值,如果遍历结束找不到,则返回null。

hash()方法和indexOf()方法

大家可能注意到了,在get()put()方法的实现中,都使用到了这两个方法,那么这里看一下源码:

//通过一系列复杂的计算拿到一个int类型的hash值
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // 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);
}

/**
* Returns index for hash code h.
*/
//将hash值和数组长度与,结果等同于hash%length,拿到数组下标
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

这里重点是:indexOf()方法,将hash值和数组长度,结果等同于hash%length,拿到数组下标。

结果等同于取模法,但是运算过程更加快速。这里有一个重要的知识点,后续会说噢。

resize()方法

put()方法及其调用的方法中,当在数组上新添加一个节点时,会判断当前是否需要扩容,怎么判断的呢?

 void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

可以看到,当当前已经存储值得size大于阀值,则将数组扩容为原来的两倍。

阀值threshold怎么计算呢?容量 * 负载因子。即 capacity * loadFactory

扩容的方法为:

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

新建一个容量为原来两倍的数组,然后将旧数组中的值,rehash之后重新放入新数组,以保证散列均匀。

rehash这个操作是比较费时间的,总的来说扩容操作就比较费时间,因为需要将旧的值移动到新的数组中,因此如果在使用前能预估数量,尽量使用带有参数的构造方法,指定初始容量,尽量避免过多的扩容操作

remove()方法

差点忘记remove()方法了。。

    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    /**
     * Removes and returns the entry associated with the specified key
     * in the HashMap.  Returns null if the HashMap contains no mapping
     * for this key.
     */
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        //计算hash
        int hash = (key == null) ? 0 : hash(key);
        //计算下标
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

具体的实现思路也是一样的:首先计算hash继而计算下标,然后遍历数组在该位置的链表,找到该key-value然后将其移除掉。

3.HashMap的一些为什么?

3.1.为什么扩容的阀值在capacity * loadFactory?

首先了解一下

  1. capacity是指容量,数组最大的容量
  2. loadfactory是指负载因子,是形容当前数组装的有多满的一个值。默认为0.75.也就是如果初始capacity为16,那么当不发生hash碰撞,也就是没有用到链表结构时,写入12个元素即会扩容了。
  3. 数组在性能上是比链表优秀的(在HashMap中,数组可以存null,不用进行值的移位)。
  4. HashMap的数据结构,导致即使容量只有16,也可以存储32(还可以更多)个值,只需要每个位置上的链表多链几个节点就好了。

因此可以发现,HashMap的性能问题又来到了时间和空间的取舍上,当你不扩容,仍然可以存储,只是由于链表的变长,性能下降。当你进行太多的扩容,hash碰撞减少,链表长度统一减少,性能提高了但是浪费的空间又多了。0.75这个值是开发者定义的一个对时间空间的折中值。

3.2.性能极限的情况

当存入的值越来越多,却不扩容,HashMap性能就会下降,那么我们极限一点。

HashMap的容量只有1,存入了100个值。由上面的分析可知,这时候HashMap退化成了单链表,存取得时间复杂度都是O(n)。

HashMap的容量为16,存入一个值,在存入第二个值,立即扩容,这样可以尽量的避免hash碰撞,避免产生链表,存取时间复杂度都为O(1).

因此,当你对存取速度要求很高,可以适当调低loadfactory,当你当前对速度无所谓,但是内存很小,可是调大loadfactory,当然大部分时候默认值0.75都是一个不错的选择。

loadfactory的值为:0.75,2,4等数字都是合法值

3.3.为什么HashMap的容量永远是2的次幂?

看过上面的代码我们可以发现,HashMap的初始容量为16,扩容为原容量乘以2。

也就是说,HashMap的容量永远是2的次幂,这是为什么呢?

想一想哪里使用到了容量这个参数呢?

在拿到key的hash值,计算当前key在数组中的下标的时候,运用了如下的方法进行计算:

真实的length为16,我们假设一个假的lengthWrong = 15;

同时我们有两个key,hash之后拿到的hash=8,和hash=9;

length - 1 二进制 8 & length - 1 9 & length- 1
15 1111 1000 & 1111 = 1000 = 8 1001 & 1111 = 1001 = 9
14 1110 1000 & 1110 = 1000 = 8 1001 & 1110 = 1000 = 8

可以看到当长度为15时,当h = 8,h =9 h & length - 1 拿到的结果一样都为8,也就是这两个key都存在数组中下标为8的链表上。这是为什么呢?

当length为偶数时,length- 1位奇数,奇数的二进制最后一位必然为1,而当length = 奇数时,length - 1位偶数,偶数的二进制最后一位为0.

二进制与运算有如下规则:

1 & 任意 = 任意;
0 & 任意 = 0;

也就是说,当length = 16时,计算的下标可以为1-16任意数字,而当length=15时,计算的下标只能为2,4,6,8 等等偶数,这样就浪费了一般的存储空间,同时还增大了hash碰撞的概率,使得HashMap的性能变差。

因此length必须为偶数,而length为2的次幂不仅能保证为偶数,还可以实现h & length - 1 = h % length,可谓是一举两得了。666啊。

扩展(Java8 的hashMap有哪些改进?)

在3.2中提到,当极限情况下HashMap会退化成链表,存取时间复杂度变为O(n),这显然是不能接受的,因此在java8中对这一点做了优化。

在java7中,存储在数组上的是一个链表的头结点,当哈希碰撞之后,不断的增长链表的长度,这会导致性能下降。在java8中,引入了红黑树数据结构,当链表长度小于8时,仍然使用链表存储,而当长度大于8时,会将链表转化为红黑树。同时,当树的节点数小于6时,会从红黑树变成链表。

这样改进之后,即使在性能最差的情况下,hashMap的存取时间复杂仍为O(logn).

而红黑树的具体实现,这里不再详细叙述,这属于数据结构的范围了,在HashMap中展开不合适。

小bug

今天在编码过程中,对Map<Integer, String> 用long作为key去取值,结果自然是取不到的,但是代码并不报错.

        Map<Integer, Integer> testMap = new HashMap<>();
        testMap.put(1, 1);
        Integer i = testMap.get((long)1);
        System.out.println(i);

在装箱过后,会变成Long,实际取值时候的HashCode是不一样的,下面是Integer和Long的HashCode方法.

    // Integer
    public static int hashCode(int value) {
        return value;
    }

    //Long
    public static int hashCode(long value) {
        return (int)(value ^ (value >>> 32));
    }

所以不要忽略代码中的警告哦~并不是只有error才会导致错误.

完.





ChangeLog

2018-10-17 完成 2019-06-28 补充bug

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十