HashMap源码解析

2021/10/13 14:14:49

编程Tag： node 数组源码 hash 解析 value key hashmap

本文主要是介绍HashMap源码解析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Java源码解析之HashMap

一、HashMap源码解析

1、HashMap的数据结构

jdk7以前：数组+链表
jdk8以后：数组+链表+红黑树

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
        ...
    }
    
    transient Node<K,V>[] table;
    
}

以上代码是jdk中HashMap中的部分代码

HashMap类中定义了一个名为Node的静态内部类，它实现了Map.Entry接口，这个内部类实例化后就是一个Entry的实现类对象，每个

Entry对象中有指向下一个元素的Node<K,V> next属性，这就是所谓的链表的实现方式（通过地址指引）

HashMap类中还定义了一个Node<K,V>[] table的数组，用于存储一个个的Node对象

从这里可以看出HashMap中存储的起始是一个个的Entry对象

小知识点

序列化：一个类实现了Serializable，就相当于告诉JVM这个类是可以被序列化的，就是可以把对象通过流写出

transient关键字：在一个可序列化的类中，transient关键字修饰的成员表示该成员不参与序列化，也就是不能写出保存，相当于是一个临时数据

反序列化：就是把序列化写出的对象读到程序内存中

下面是Node内部类的具体源代码

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

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

2、HashMap的构造方法

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    transient int modCount; //记录这个HashMap结构被修改的次数
    
    transient int size;	//这个HashMap中包含键值对的数量
    
    int threshold;	//下一次扩容的条件数值，当数组内容达到这个值时进行扩容
}

HashMap类存在这三种常量属性，和哈希表的性能有关，分别是

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4：定义了Node<K,V>[] table数组的默认大小

static final int MAXIMUM_CAPACITY = 1 << 30：定义了Node<K,V>[] table数组的最大长度

static final float DEFAULT_LOAD_FACTOR = 0.75f：定义了哈希表的加载因子

1 << 4 << 是移位操作，是基于二进制的操作

1的二进制 0000 0001 就是十进制的1

1 << 4 后 0001 0000 就是十进制的16

加载因子：加载因子就是判断数组什么时候进行扩容，当数组内元素个数满足原数组长度*加载因子个时进行扩容

空构造public HashMap()
```
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
```
调用空构造函数时，生成对象的字段属性使用的都是默认值

数组默认长度16bit、加载因子0.75
包含数组长度和加载因子的构造函数public HashMap(int initialCapacity, float loadFactor)
```
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;
    this.threshold = tableSizeFor(initialCapacity);
}
```
这个构造方法中，传了一个数组的长度和加载因子的数组作为参数，函数内就是判断这两个值是否符合条件，符合的话就为对象的loadFactor属性赋值，并使用 this.threshold = tableSizeFor(initialCapacity);为threshold 赋值；否则报错

tableSizeFor这个函数返回一个大于指定值得最小2次幂

使用 this.threshold = tableSizeFor(initialCapacity)为threshold 赋值？？？

threshold的值不应该是 this.threshold = tableSizeFor(initialCapacity)*loadFactor吗？

在HashMap的构造函数，并没有为Node<K,V>[] table进行初始化，而是把初始化的过程放在了put方法里
包含数组长度的构造函数public HashMap(int initialCapacity)
```
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
```
这个就是调用public HashMap(int initialCapacity, float loadFactor)构造，把加载因子为默认值

3、HashMap的存值(put方法)

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

调用put方法时，put方法会把key的hash值计算出来，然后调用putVal方法，返回值为Value的值

1.putVal方法会先判断数组是否需要扩容

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

如果数组为空或者长度为零，则调用resize方法扩容数组，这里才对数组进行初始化操作

2.然后计算出元素的索引，判断数组上该位置是否已经存过元素
```
	if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
```
如果该位置为空，则直接存入该位置

(n-1) & hash 是求该hash值在数组中的索引的操作

n ---> 数组长度

例如：数组长度为16 hash值为一个随机值

n 0001 0000 16

n-1 0000 1111 15

hash 1011 0011 随机

& 0000 0011 &后的结果 3

(n-1) & hash相当于拿出一个随机值的后几位

3.如果数组当前索引处已经存有元素了,把数组当前索引存的对象称为 p

判断这个元素的key值是否和p的key值相同

    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

如果相同则取出p对象,否则

判断p是否为一个树节点

	else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

如果p是一个树节点，调用putTreeVal方法

遍历数组这个索引下的节点

如果存在和要存元素key值相同的元素

如果存在，则把这个元素记录到e上，用于后续判断
如果不存在，则把新元素插入到链表的尾部

 	else {
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }

如果执行完上面的代码取出的元素不为空，则说明存在和要存对象key值相同的元素

	if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }

用新的value值替换旧的value值，返回旧的value值

最后说明插入成功，将数组的元素数量加一，判断是否需要扩容

    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

这就是put方法的全过程，此外，put方法结尾还提供了一个afterNodeAccess(e)方法，这是一个空方法，没有任何实现，它允许我们插入元素后进行一些操作

4、HashMap的取值(get方法)

get方法返回一个value值，源码如下

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

get方法通过调用getNode方法来找到相应的键值对对象，下面是getNode方法的源码

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

5、HashMaps数组扩容(resize方法)

因为在HashMap的构造方法里，并没有对数组进行初始化，而是在put方法里调用resize方法进行对数组的统一处理

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

先在resize方法里定义了一些变量来表示数组的一些信息

如果数组已经初始化过，分为两种情况
- 数组长度已经大于设定的最大容量了
  
  这时，把扩容条件阈值设为整数的最大值，这样在put方法插入元素后的判断if (++size > threshold)就始终为false（因为size是int类型，不会大于Integer.MAX_VALUE），这样数组就不会再进行扩容
- 数组长度介于默认值和最大值之间
  
  这时，数组将进行正常的扩容操作，数组长度和扩容条件阈值都变为原来的两倍
```
if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
}
```
如果数组未初始化，且条件阈值大于零

什么时候才会发生这种情况呢？

当我们调用HashMap的非空构造方法时，在构造方法里并没有对数组进行初始化，而是计算出来扩容阈值threshold的值，这样就会出现数组长度为零，扩容条件阈值存在的情况
```
else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
```
这种情况下，直接把扩容阈值作为数组的长度进行初始化
如果数组未初始化且条件阈值不存在

不存在的意思是没有赋过值，这时threshold的值是默认值0

这种情况最常见，一般是调用了HashMap的空构造
```
else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
```
这种情况下，数组长度和条件阈值都用默认值即可、
if (newThr == 0)？为什么还要有这个判断？

在执行else if (oldThr > 0) newCap = oldThr;这句后，也就是当调用HashMap的有参构造时，这里并没有为newThr赋值，因此newThr为默认值0
```
if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
}
```
这个判断就是为newThr赋值

然后把扩容后的信息更新到对象中

    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

扩容完毕，将原来的数据转移到新数组中

对这段代码先不做解释，谅解

二、HashMap线程不安全的原因

HashMap在java7以前，存在的线程安全问题有死循环、数据丢失、数据覆盖；在java8以后，HashMap存在的线程安全问题是数据覆盖

多线程问题1-->数据覆盖

前提：多个线程进行put存值时，多个线程的要存的索引位置相同，并且满足存储条件（不存在key值相同）

线程一判断完满足存储条件后挂起 -----> 线程二启动，并在在线程一要存的位置存值 ---> 线程一继续运行，在相应位置存值

这时就把线程二所存的值覆盖掉了

此外，在if (++size > threshold)这句代码里，++size明显是一个线程不安全的操作

多线程问题2-->死循环

以下是jdk7以前的HashMap数组扩容后数据迁移的源码

//数据迁移的方法，头插法添加元素
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用		//而已）
    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);
            //将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链				//表头部插入。
            //以下三行是线程不安全的关键
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

会发生线程安全问题的代码主要是e.next = newTable[i]; newTable[i] = e;这两行

多线程问题2-->数据丢失

后面会更新，敬请见谅！

这篇关于HashMap源码解析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！