Java HashMap 核心源码解读

本篇对HashMap实现的源码进行简单的分析。
所使用的HashMap源码的版本信息如下:

转载自:

/*
* @(#)HashMap.java 1.73 07/03/13
*
* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*/

哈希表(hash table)也叫散列表,是一种非常重要的数据结构

一.概述

在Java中每一个对象都有一个哈希码,这个值可以通过hashCode()方法获得。hashCode()的值和对象的equals方法息息相关,是两个对象的值是否相等的依据,所以当我们覆盖一个类的equals方法的时候也必须覆盖hashCode方法。

例如String的hashCode方法为:

public int hashCode() {
int h = hash;
if (h == 0) {
int off = offset;
char val[] = value;
int len = count;

for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}

可以看得出,一个字符串的哈希值为s[0]31n-1 + s[1]31n-2 + … +
s[n-1],是一个整数。也就是说所有的字符串可以通过hashCode()将其映射到整数的区间中,由于在java中整数的个数是有限的(四个字节有正负,第一位为符号位-231 ~
231 -1),当s[0]31n-1 + s[1]31n-2 + … +
s[n-1]足够大的时候可能会溢出,导致其变成负值。从上面的情况我们可以看出两个不同的字符串可能会被映射到同一个整数,发生冲突。因此java的开发人员选择了31这个乘数因子,尽量使得各个字符串映射的结果在整个java的整数域内均匀分布。

谈完java对象的哈希码,我们来看看今天的主角HashMap,HashMap可以看作是Java实现的哈希表。HashMap中存放的是key-value对,对应的类型为java.util.HashMap.Entry,所以在HashMap中数据都存放在一个Entry引用类型的数组table中。这里key是一个对象,为了把对象映射到table中的一个位置,我们可以通过求余法来,所以我们可以使用
[key的hashCode %
table的长度]来计算位置(当然在实际操作的时候由于需要考虑table上的key的均匀分布可能需要对key的hashCode做一些处理)。

一、什么是哈希表

二.源码解析

相关属性 首先肯定是需要一个数组table,作为数据结构的骨干。

transient Entry[] table;

这边定义了一个Entry数组的引用。 继续介绍几个概念把

capacity容量 是指数组table的长度
loadFactor 装载因子,是实际存放量/capacity容量
的一个比值,在代码中这个属性是描述了装载因子的最大值,默认大小为0.75
threshold(阈值)代表hashmap存放内容数量的一个临界点,当存放量大于这个值的时候,就需要将table进行夸张,也就是新建一个两倍大的数组,并将老的元素转移过去。threshold
= (int)(capacity * loadFactor);

put方法详解

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        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++;
        addEntry(hash, key, value, i);
        return null;
    }

在HashMap中我们的key可以为null,所以第一步就处理了key为null的情况。
当key为非null的时候,你也许会认为:恩,直接和table长度相除取模吧,但是这里没有,而是又好像做了一次哈希,这是为什么呢?这个还得先看indexFor(hash,
table.length)方法,这个方法是决定存放位置的

static int indexFor(int h, int length) {
        return h & (length-1);
    }

明眼的都可以发现,因为在HashMap中table的长度为2n (我们把运算都换成二进制进行考虑),所以h
&
(length-1)就等价于h%length,这也就是说,如果对原本的hashCode不做变换的话,其除去低length-1位后的部分不会对key在table中的位置产生任何影响,这样只要保持低length-1位不变,不管高位如何都会冲突,所以就想办法使得高位对其结果也产生影响,于是就对hashCode又做了一次哈希

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所对应的位置的时候,对对应位置的Entry的链表进行遍历,如果以及存在key的话,就更新对应的value,并返回老的value。如果是新的key的话,就将其增加进去。modCount是用来记录hashmap结构变化的次数的,这个在hashmap的fail-fast机制中需要使用(当某一个线程获取了map的游标之后,另一个线程对map做了结构修改的操作,那么原先准备遍历的线程会抛出异常)。addEntry的方法如下

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

get方法

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        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.equals(k)))
                return e.value;
        }
        return null;
    }

get方法其实就是将key以put时相同的方法算出在table的所在位置,然后对所在位置的链表进行遍历,找到hash值和key都相等的Entry并将value返回。

二、HashMap实现原理

三、为何HashMap的数组长度一定是2的次幂?

四、重写equals方法需同时重写hashCode方法

 

一、什么是哈希表

在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能

数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)。

******注解O(logn)******

像二分查找,它每次都是排除一半(即每次都是以2倍速跑向目标),时间复杂度在这就是从
n 到 1 的时间x,反过来想就等于从 1 到 n的时间x,即 1*=n,则
x=n,记为O(logn)

**************************

线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)。

二叉树:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。

哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

我们知道,数据结构的物理存储结构只有两种:顺序存储结构链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组

*********怎么和数组一样利用下标(即存储地址)**********

Entry是HashMap的基本组成单元,

每个Entry中有4个值:key、value、hash(存储位置即key的映射)、next(指针)。

我们都知道有 键(key)值(value)对这么一说,其中键就是值的关键字;

哈希函数,就是把键映射到存储地址的函数,存储位置 =
f(关键字),注意,这个哈希函数可能不是一个函数,key可能经过f1(),f2(),f3()多个函数最终得到这个存储位置(这个值命名为hash)也会存到hashmap的结构单元中;

*************************************************************

举个例子,比如我们要在哈希表中执行插入操作:

 

查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

哈希冲突

  然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式,

 

二、HashMap实现原理

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。

//HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂,至于为什么这么做,后面会有详细分析。

transient Entry<K,V>[] table = (Entry<K,V>[])
EMPTY_TABLE;

Entry是HashMap中的一个静态内部类。代码如下:

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

        final K key;

        V value;

        Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构

        int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算

        /**

         * Creates new entry.

         */

        Entry(int h, K k, V v, Entry<K,V> n) {

            value = v;

            next = n;

            key = k;

            hash = h;

        } 

 所以,HashMap的整体结构如下:

 

简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度依然为O(1),因为最新的Entry会插入链表头部,急需要简单改变引用链即可,而对于查找操作来讲,此时就需要遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

//实际存储的key-value键值对的个数

transient int size;

//阈值,当table == {}时,该值为初始容量(初始容量默认为16);当table被填充了,也就是为table分配内存空间后,threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold,后面会详细谈到

int threshold;

//负载因子,代表了table的填充度有多少,默认是0.75

final float loadFactor;

//用于快速失败,由于HashMap非线程安全,在对HashMap进行迭代时,如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作),需要抛出异常ConcurrentModificationException

transient int modCount;

//(注:transient, java语言的关键字,变量修饰符,如果用transient声明一个实例变量,当对象存储时,它的值不需要维持。换句话来说就是,用transient

//关键字标记的成员变量不参与序列化过程。)

HashMap有4个构造器,其他构造器如果用户没有传入initialCapacity
和loadFactor这两个参数,会使用默认值

initialCapacity默认为16,loadFactory默认为0.75

我们看下其中一个:

public HashMap(int initialCapacity, float loadFactor) {
     //此处对传入的初始容量进行校验,最大不能超过MAXIMUM_CAPACITY
= 1<<30(230)

        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();//init方法在HashMap中没有实际实现,不过在其子类如
linkedHashMap中就会有对应实现

    }

  
从上面这段代码我们可以看出,在常规构造器中,没有为数组table分配内存空间(有一个入参为指定Map的构造器例外),而是在执行put操作的时候才真正构建table数组。

public V put(K key, V value) {

       
//如果table数组为空数组{},进行数组填充(为table分配实际内存空间),入参为threshold,此时threshold为initialCapacity
默认是1<<4(24=16)

        if (table == EMPTY_TABLE) {

            inflateTable(threshold);

        }

       //如果key为null,存储位置为table[0]或table[澳门新葡亰手机版,0]的冲突链上

        if (key == null)

            return putForNullKey(value);

        int hash = hash(key);//对key的hashcode进一步计算,确保散列均匀

        int i = indexFor(hash, table.length);//获取在table中的实际位置

        for (Entry<K,V> e = table[i]; e != null; e = e.next) {

       
//如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value

            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++;//保证并发访问时,若HashMap内部结构发生变化,快速响应失败

        addEntry(hash, key, value, i);//新增一个entry

        return null;

    }   

 先来看看inflateTable这个方法:

private void inflateTable(int toSize) {

        int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂

        threshold = (int) Math.min(capacity * loadFactor,
MAXIMUM_CAPACITY +
1);//此处为threshold赋值,取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值,capaticy一定不会超过MAXIMUM_CAPACITY,除非loadFactor大于1

        table = new Entry[capacity];

        initHashSeedAsNeeded(capacity);

    }

 inflateTable这个方法用于为主干数组table在内存中分配存储空间,通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂,比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

private static int roundUpToPowerOf2(int number) {

        // assert number >= 0 : “number must be non-negative”;

        return number >= MAXIMUM_CAPACITY

                ? MAXIMUM_CAPACITY

                : (number > 1) ? Integer.highestOneBit((number – 1)
<< 1) : 1;

    }

roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂,Integer.highestOneBit是用来获取最左边的bit(其他bit位为0)所代表的数值.

//这是一个神奇的函数,用了很多的异或,移位等运算,对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀

final int hash(Object k) {

        int h = hashSeed;

        if (0 != h && k instanceof String) {

            return sun.misc.Hashing.stringHash32((String) k);