java HashMap源码解析

时间:2021-08-12 17:19:42

一、什么是Map

    根据Map源码上的注释可以得到:

    1.Map是一个接口,他是key-value的键值对,一个map不能包含重复的key,并且每一个key只能映射一个value;

    2.Map接口提供了三个集合视图:key的集合,value的集合,key-value的集合;

    3.Map内元素的顺序取决于Iterator的具体实现逻辑,获取集合内的元素实际上是获取一个迭代器,实现对其中元素的遍历;

    4.Map接口的具体实现中存在三种Map结构,其中HashMap和TreeMap都允许存在null值,而HashTable的key不允许为空,但是HashMap不能保证遍历元素的顺序,TreeMap能够保证遍历元素的顺序。

二、HashMap的概念

1.什么是哈希表 

    哈希表(HashTable,散列表)是根据key-value进行访问的数据结构,他是通过把key映射到表中的一个位置来访问记录,加快查找的速度,其中映射的函数叫做散列函数,存放记录的数组叫做散列表,哈希表的主干是数组。

java HashMap源码解析

    上面的图中就是一个值插入哈希表中的过程,那么存在的问题就是不同的值在经过hash函数之后可能会映射到相同的位置上,当插入一个元素时,发现该位置已经被占用,这时候就会产生冲突,也就是所谓的哈希冲突,因此哈希函数的设计就至关重要,一个好的哈希函数希望尽可能的保证计算方法简单,但是元素能够均匀的分布在数组中,但是数组是一块连续的且是固定长度的内存空间,不管一个哈希函数设计的多好,都无法避免得到的地址不会发生冲突,因此就需要对哈希冲突进行解决。

    (1)开放定址法:当插入一个元素时,发生冲突,继续检查散列表的其他项,直到找到一个位置来放置这个元素,至于检查的顺序可以自定义;

    (2)再散列法:使用多个hash函数,如果一个发生冲突,使用下一个hash函数,直到找到一个位置,这种方法增加了计算的时间;

    (3)链地址法:在数组的位置使用链表,将同一个hashCode的元素放在链表中,HashMap就是使用的这种方法,数组+链表的结构。

2.什么是HashMap

    HashMap是基于哈希表的Map接口的实现,提供所有可选的映射操作,允许使用null值和null键,存储的对象时一个键值对对象Entry<K,V>;

    是基于数组+链表的结构实现,在内部维护这一个数组table,数组的每个位置保存着每个链表的表头结点,查找元素时,先通过hash函数得到key值对应的hash值,再根据hash值得到在数组中的索引位置,拿到对应的链表的表头,最后去遍历这个链表,得到对应的value值。

    java HashMap源码解析

三、HashMap类中的主要方法

1.HashMap中的几个重要的变量

//默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 16;

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

//负载因子,默认为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//数组表,大小可以改变,且大小必须为2的幂
transient Entry[] table;

//当前Map中key-value映射的个数
transient int size;

//下次扩容阈值,当size > capacity * load factor时,开始扩容
int threshold;

//负载因子
final float loadFactor;

//Hash表结构性修改次数,用于实现迭代器快速失败行为
transient volatile int modCount;

2.HashMap的Entry实体

    HashMap存储的对象是一个Entry实体,Entry是HashMap中的一个静态内部类,在HashMap类中的源码为:

static class Entry<K,V> implements Map.Entry<K,V> {
	final K key;
	V value;
	Entry<K,V> next;
	final int hash;

	//构建一个新的实体
	Entry(int h, K k, V v, Entry<K,V> n) {
		value = v;
		next = n;
		key = k;
		hash = h;
	}

	public final K getKey() {
		return key;
	}

	public final V getValue() {
		return value;
	}

	.........
}

    其中key值定义的为final,因此在定义之后就无法进行修改,key和value就是在调用map时对应的键值对,next存储的是链表中的下一个节点,他是一个单链表,hash是对key的hashcode再次进行哈希运算之后得到的值,存储起来是为了避免重复计算。

3.HashMap的初始化

    初始化构造一个hashMap有四种方法,这四种方法都比较好理解,我们主要看一下第一种方法:

    在指定了初始化容量和负载因子时,首先会对参数进行检查,符合条件后,会根据初始化容量进行调整,使其必须是2的次幂,因此即使用户在使用时指定了容量,实际初始化的容量不一定等于指定的容量,至于为什么必须得是2的次幂,在后面的过程中在讲,在设置好容量之后,根据当前容量和负载因子计算出下一次扩容时的阈值threshold,也就是map中的元素个数达到这个值之后就要进行扩容。

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

	//根据初始化的容量对实际的容量进行调整,必须为2的次幂
	int capacity = 1;
	while (capacity < initialCapacity)
	       capacity <<= 1;

	this.loadFactor = loadFactor;
	//根据容量和负载因子计算出当前的阈值
	threshold = (int)(capacity * loadFactor);
	table = new Entry[capacity];
	init();
}

//2.仅指定容量,使用默认的负载因子,内部实现实际上还是依赖的第一种方法
public HashMap(int initialCapacity) {
	this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//3.使用默认容量和负载因子
public HashMap() {
	this.loadFactor = DEFAULT_LOAD_FACTOR;
	threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
	table = new Entry[DEFAULT_INITIAL_CAPACITY];
	init();
}

//4.根据指定的map初始化,根据指定的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);
	putAllForCreate(m);
}

4.HashMap的put操作

    由于HashMap中允许存在null的key,因此在插入元素的时候,需要对key值进行判断,其主要步骤为:

    (1)如果key为null值,单独进行处理,putForNullKey(value);

    (2)如果key不是null值,根据key的hashCode再次计算hash值 hash(key.hashCode());

    (3)根据hash值和table数组的长度得到该元素在数组中的索引位置i=indexFor(hash,table.length);

    (4)取得该位置的链表,如果链表不为空,对链表进行遍历,判断key值在链表中是否存在,已存在用新的value值替代旧值,同时返回旧值;

    (5)否则,向该位置的链表的表头插入新的元素addEntry(hash,key,value,i)

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

    在put操作中,我们也看到了其中包含好几个方法,接下来对这几个方法进行说明:

    当key值为null时,默认是将该元素插入到table[0]的位置,首先也是取到table[0]位置的链表,如果链表不为空,对链表进行遍历,判断是否存在key为null的值,如果存在,将新的value替换旧的值,同时返回旧值,如果不存在,就在链表的表头插入一个新的Entry

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

    在put操作中,最终决定元素存放的位置还需要以下两个方法,第一个可以看出来是对一个值使用hash方法,使用了各种异或、移位的操作,他是对key的hashCode再一次进行计算以及二进制位操作的过程,目的是为了使最终在数组中存储的位置尽可能的分布均匀,具体移位操作的过程就不讲了

static int hash(int h) {
	h ^= (h >>> 20) ^ (h >>> 12);
	return h ^ (h >>> 7) ^ (h >>> 4);
}

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

    indexFor方法是根据得到的hash值和数组的长度得到最终元素在数组中存放的索引位置,主要使用的是与(&)操作,这种方法也是保证获取的index一定是在数组的范围内,例如,如果数组的默认容量时16,h=25,转换为二进制计算得到的是:index=9,也就是该元素在table[9]的位置。

java HashMap源码解析

    HashMap的的数组长度一定是2的次幂,在这里也可以看出来,比如长度为16的数组,那么length-1=15,他的二进制是01111,长度为32的数组,length-1=31,二进制为011111,可以看出length-1的低位全部都是1,这样在进行hash&(length-1)操作的时候,只要hash对应的最左边的差异位为0,能够保证所有的位置都可能被用到,例如如果长度是15,那么length-1=14,二进制为01110,与任何值进行&的时候,尾数永远都是0,就会导致0001,1001,1101等尾数为1的位置永远不可能有元素放置进去,所以设置长度为2的次幂的原因也是为了尽可能的保证所有的位置都可以被存储元素。

        在put操作中,如果一个key值在数组中不存在的时候,需要往map中加入一个节点,其主要的方法是addEntry,他的主要步骤是:首先根据在table数组中的索引值拿到该位置上的链表e,新建一个Entry,使其的key和value是新加入的元素,next是e,也就是将新加入的值作为链表的表头放到table对应的位置上。

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

      在HashMap中每插入一个新的元素之后,这里新的是指key在map中之前是不存在的,都需要对table数组的容量进行检查,判断是否需要扩容,当当前map中的元素的个数超过设置的阈值时threshold时,调用resize方法,其中传递的参数是当前数组的长度的2倍。

     在使用resize的过程中,首先要判断当前数组的容量是否已经是最大值,如果是最大值,直接将阈值设置为Integer的最大值,然后返回,也就是不对数组进行扩容了。

    否则,创建一个新的数组newTable,他的容量时当前数组容量的2倍,然后调用transfer方法,将旧数组中的元素复制到新的数组中,返回新的数组,每次的扩容操作都是将数组翻倍,然后对每一个元素重新计算位置,因此扩容操作是一个耗费时间和资源的操作。

 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];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

    接下来看一下transfer方法,他是对老的数组进行遍历,取出table中每一个索引位置上的链表,然后对链表进行遍历,取出链表中的每一个Entry,根据其中的hash值和新的数组的length重新计算新的索引位置,然后将元素插入新的链表中,这一步会使得原有数组中的所有元素的位置被重新计算。

   //复制老的键值对到新的数组中
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

5.HashMap的get操作

    HashMap的get操作相比put操作就简单很多,首先是判断key值是否为null,如果是null,则直接调用getForNummKey()方法去table[0]的位置查找元素,拿到table[0]处的链表进行遍历,这里只需要判断链表中的key值是否是null,返回对应的value值。

    如果key值不是null,则需要对key.hashCode再次计算hash值,调用indexFor方法拿到在table中的索引位置,获取到对应的链表。拿到链表后,需要对链表进行遍历,判断hashCode值是否相等以及key值是否相等,共同判断key值是否在HashMap中存在,从而拿到对应的value值。在这里也就说明了为什么把一个对象放入到HashMap的时候,最好是重写hashCode()方法和equals方法,hashCode()可以确定元素在数组中的位置,而equals方法在链表比较的时候会用到。

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

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

四、HashMap的多线程不安全的体现

1.resize扩容时死循环

在扩容操作是,是对链表进行循环操作,如果同时有两个线程在对同一个链表进行transfer操作,线程A在transfer的时候会修改为value2.next=value1, 线程B操作时,根据原始链表拿到的是value1.next=value2,而由于线程A已经修改为value2.next=value1,那么就会存在死循环的问题。

java HashMap源码解析

2.数据不一致

当一个线程在对HashMap进行resize操作,而另一个线程在进行get操作时,比如原始数组长度时16,扩容之后是32,在进行get操作根据扩容之前的length拿到index1,而这个时候另一个线程正好对index1的链表做好扩容操作,那么从index1的位置取出来的元素肯定是null,这时候可以使用ConcurrentHashMap(ConcurrentHashMap在之后再讲)

五、HashMap总结

1.HashMap是由数组和链表组成的,数组是HashMap的主体,链表是为了解决哈希冲突的问题,对于HashMap的插入问题,如果插入位置不含有链表,那么直接插入到链表的表头即可,如果包含链表,需要先遍历链表,判断key是否已经在链表中存在,存在则替换value值,不存在则插入到链表的表头。

2.HashMap中是根据hashCode和equals方法来决定存放的位置,因此不允许一个map将自己作为key值,但是可以将自己作为value值。

3.HashMap是线程不安全的,对于多线程环境下,无法保证数据的正确性,使用的时候需要注意。

4.如果在使用时能评估到HashMap中元素的个数,建议指定初始化容量的大小,在HashMap中默认容量时16,在插入元素的时候,会对元素进行检查是否需要扩容,每次扩容就是新建一个原来2倍容量的数组,对原有的元素全部重新哈希,因此如果不断插入元素,那么会需要不断的扩容,不断的哈希,这时候产生的内存开销和cpu开销在某些情况下可能是致命的。