Java源码之HashMap

x33g5p2x  于2021-03-13 发布在 Java  
字(9.4k)|赞(0)|评价(0)|浏览(176)

一、HashMap概述

HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

值得注意的是HashMap不是线程安全的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

Map map = Collections.synchronizedMap(new HashMap());

二、HashMap中的数据结构

1.jdk1.8之前

在jdk1.8之前的HashMap是基于数组+链表来实现,即严蔚敏版《数据结构》中**哈希表(散列表)**链地址法,哈希表的优点是查询速度快。

HashMap中主要是通过key的hashCode来计算hash值,只要hashCode相同,计算出来的hash值就一样。如果存储的对象多了,就有可能不同的对象映射到相同的hash值,这就是所谓的hash冲突。HashMap中所用解决hash冲突的方法是链地址法。

可参考严蔚敏版《数据结构》哈希表解决hash冲突的链地址法

图中,黄色部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。

2.jdk1.8中HashMap的实现方式

jdk1.8中对HashMap做的很大的改进,采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,大大减少了hash冲突时查找时间(从原来的O(n)->O(logn))。由于红黑树的结点空间是链表空间的2倍,为了节省空间,当链表长度减少(如删除操作)到阈值(6)时,又会转换为链表形式。

链表中的结点对应HashMap中的Node类(jdk1.8之前用的是Entry类,原理差不多),具体如下:

// Node是单向链表,实现了Map.Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // hash值
    final K key; // 键
    V value; // 值
    Node<K,V> next; // 指向下一个结点

    /*
     * 构造函数
     * 利用(hash值、键、值、下一个结点)来构造结点
     */
    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 V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final String toString() { return key + "=" + value; }

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

    // 判断两个结点是否相等
    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;
    }
}

HashMap其实就是一个Node数组,Node对象中包含了键和值,其中next也是一个Node对象,它用来处理hash冲突,

使具有相同hash值的结点连在一个链表或树中。

下面是红黑树结点:

它继承自LinkedListMap.Entry,这是一种双链表结点(具体可参考【Java源码之LinkedHashMap】)。

/**
 * 红黑树结点,继承自LinkedHashMap.Entry
 */
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 指向父结点
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red; // 结点颜色(红或黑)
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    /**
     * 返回当前节点所在树的树结点
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
}

三、HashMap源码

1.头文件

package java.util;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;

2.继承情况

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

3.属性

/**
 * 默认初始容量 - 必须是2的幂次方
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

/**
 * 最大容量
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 当构造函数不指定时,默认(Hash表)装载因子。
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 链表->红黑树的阈值
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 红黑树->链表的阈值
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64;
/**
 * 存放元素的Node数组
 */
transient Node<K,V>[] table;

/**
 * 装Map用Set集合(可用于迭代Map)
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * map中的包含的元素个数
 */
transient int size;

/**
 * HashMap的修改次数
 */
transient int modCount; // fail-fast机制,下面有解释

/**
 * 阈值 - 当实际大小超过临界值时,会进行扩容。threshold = capacity * loadFactor(注意这里的capacity与size的区别)
 */
int threshold; // 默认情况下是12

/**
 * 装载因子,表示Hsah表中元素的填满的程度
 */
final float loadFactor;

fail-fast机制:即快速失败机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。

例如:当某一个线程A通过iterator去遍历某集合的过程中,若该集合的内容被其他线程所改变了;

那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生fail-fast事件。

4.构造函数(4个)

/**
 * 构造函数一:指定初始容量和装载因子
 */
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); // tableSizeFor方法会将initialCapacity转化成2的幂次方,详见tableSizeFor方法
}

/**
 * 构造函数二:指定初始容量并使用默认装载因子(0.75)
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 构造函数三:使用默认初始容量(16)和默认装载因子(0.75)
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * 构造函数四:使用另一个Map来构造
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

5.常用方法

(1)hash方法

严版《数据结构》中提到的哈希函数的构造方法有:

  • 直接定址法
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 除留取余法

Hashtable中用的是 除留取余法, 即便于计算,又能减少冲突。

index = (hash & 0x7FFFFFFF) % tab.length;

但是取模中的除法运算效率很低,HashMap则通过h & (length - 1)替代取模,得到所在数组位置,这样效率会高很多。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

代码中,首先由key值通过hashCode()方法获取h值,再通过h & (length - 1)来得到所在数组的位置。

在HashMap实现中还可以看到如下代码取代了jdk1.8以前用while循环来保证哈希表的容量一直是2的整数倍数,用移位操作取代了循环移位。

/**
 * 根据给定的容量cap来构造符合2的次幂的值
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1; // ">>>"为右移填0操作,即不管符号位是什么都用0填充
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

可以从源码看出,在HashMap的构造函数中,都直接或间接的调用了tableSizeFor函数。
下面分析原因:length为2的整数幂保证了length-1最后一位(当然是二进制表示)为1,从而保证了取索引操作 h & (length - 1)的最后一位同时有为0和为1的可能性,保证了散列的均匀性。反过来,如果length为奇数时,length-1最后一位为0,这样与h按位“与”的最后一位肯定为0,即索引位置肯定是偶数,这样数组的奇数位置全部没有放置元素,浪费了大量空间。

(2)数据读取:get和getNode方法

/**
 * 根据key返回对应的value值
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * 实现Map.get和相关方法
 */
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) { // 使用hash & (length-1)得到所在位置
        if (first.hash == hash && // 判断头结点
            ((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;
}

(3)存储数据:put和putValue方法

/**
 * 实现Map.put和相关方法
 * 参数hash:key的hash值
 * 参数key:要设置的key值
 * 参数value:要设置的value值
 * 参数onlyIfAbsent if true, don't change existing value
 * 如果为假,则替换原来的value
 * 参数evict:if false, the table is in creation mode.
 * 返回:替换时返回oldValue,非替换时返回null
 */
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) // 如果tab为空,则调用resize分配内存
        n = (tab = resize()).length;
    // 使用hash & (lengt-1)得到存入位置,得到插入位置中的结点p
    if ((p = tab[i = (n - 1) & hash]) == null) // 结点p为null,直接插入
        tab[i] = newNode(hash, key, value, null);
    else { // 插入位置冲突
        Node<K,V> e; K k;
        // 与第一个结点相同:hash值与key值相同(1)
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 与第一个结点不相同
        else if (p instanceof TreeNode) // 红黑树情况
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { // 链表情况
            for (int binCount = 0; ; ++binCount) {
            	// p从表头依次后移
                if ((e = p.next) == null) { // 到达链尾
                    p.next = newNode(hash, key, value, null); // 接入链尾
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 达到(链->树)阈值
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到"相同"对象:hash值与key值相同(2)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e; // p后移:p=p.next
            }
        }
        // 处理上述两处hash值与key值相同
        if (e != null) { // 已有key值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold) // 如果size>threshold时进行扩容,见后面的reise()函数
        resize();
    afterNodeInsertion(evict);
    return null;
}

(4)扩容策略:resize方法

size > threshold时调用resize()扩容。

/**
 * 初始化或加倍容量大小。
 *
 * 返回新的hash table数组
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    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; // 阈值加倍
    }
    else if (oldThr > 0) // 用阈值初始值新的容量
        newCap = oldThr;
    else {               // 当阈值==0时
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 下面是将旧tab中的Node转移到新tab中,分链表和红黑树两种情况
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) // 红黑树情况
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 链表情况
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

相关文章