某某茶叶有限公司欢迎您!
金沙棋牌在线 > 金沙棋牌在线 > Java HashMap源码分析

Java HashMap源码分析

时间:2019-12-29 06:39

引言

HashMap在键值对存储中被经常使用,那么它到底是如何实现键值存储的呢?

1、HashMap底层实现

transient Node<K,V>[] table;(数组+链表)。数组的长度总是2的n次方

HashMap 内部数据结构为数组+链表,HashMap源码(基于JDK1.7)如下:

HashMap使用一个的数组来保存不同散列值的key以及相应的value。在jkd1.8中,对于相同hashcode形成的bucket,不再按照唯一的链表存储,而是根据bucket的大小,超过一定限制之后将链表转换为红黑树来存储Map.Entry<k,v>。这样,HashMap的内部数据结构就是数组+链表+红黑树。

一 Entry

Entry是Map接口中的一个内部接口,它是实现键值对存储关键。在HashMap中,有Entry的实现类,叫做Entry。Entry类很简单,里面包含key,value,由外部引入的hash,还有指向下一个Entry对象的引用,和数据结构中学的链表中的note节点很类似。

Entry类的属性和构造函数:

final K key;
V value;
Entry<K,V> next;
int hash;
/**
 * Creates new entry.
 */
Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

2、基本属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量16,必须是2的N次方(原因见#3)

static final int MAXIMUM_CAPACITY = 1 << 30;    // 最大容量,必须是2的N次方

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

static final int TREEIFY_THRESHOLD = 8; // 链表节点转换红黑树节点的阈值
public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{

    /**
     * 默认大小为16,且必须为2的N次方
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * 最大容量为2的30次方.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * // 默认加载因子
     */
    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;

    /**
     * HashMap保存的键值对的数量.
     */
    transient int size;

    /**
     * HashMap的阈值, threshold = capacity*loadFactor
     */
    int threshold;

    /**
     * 加载因子实际大小
     */
    final float loadFactor;

    /**
     * HashMap被修改的次数
     */
    transient int modCount;

    /**
     * 
     */
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

    /**
     * holds values which can't be initialized until after VM is booted.
     */
    private static class Holder {

        /**
         * Table capacity above which to switch to use alternative hashing.
         */
        static final int ALTERNATIVE_HASHING_THRESHOLD;

        static {
            String altThreshold = java.security.AccessController.doPrivileged(
                new sun.security.action.GetPropertyAction(
                    "jdk.map.althashing.threshold"));

            int threshold;
            try {
                threshold = (null != altThreshold)
                        ? Integer.parseInt(altThreshold)
                        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;

                // disable alternative hashing if -1
                if (threshold == -1) {
                    threshold = Integer.MAX_VALUE;
                }

                if (threshold < 0) {
                    throw new IllegalArgumentException("value must be positive integer.");
                }
            } catch(IllegalArgumentException failed) {
                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
            }

            ALTERNATIVE_HASHING_THRESHOLD = threshold;
        }
    }

    /**
     * 
     */
    transient int hashSeed = 0;

    /**
     * 指定"容量大小"和"加载因子"的构造函数
     */
    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;
        threshold = initialCapacity;
        init();
    }

    /**
     * 指定"容量大小"的构造函数
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 默认构造函数.
     */
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 包含“子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);
        inflateTable(threshold);

        putAllForCreate(m);
    }

}

*jkd源码的版本为1.8.0_05

二 HashMap的初始化

//HashMap构造方法
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;
    threshold = initialCapacity;
    init();
}

这是HashMap的构造函数之一,其他构造函数都引用这个构造函数进行初始化。参数InitialCapacity指的是HashMap中table数组最初的大小,参数loadFactory指的是HashMap可容纳键值对与数组长度的比值(举个例子:数组长度默认值为16,loadFactory默认值为0.75,如果HashMap中存储的键值对即Entry多于12,则会进行扩容,扩容后大小为当前数组长度的2倍)。在构造函数中不会对数组进行初始化,只有在put等操作方法内会进行判断是否要初始化或扩容。

3、定位数组索引位置

1、重新计算hash

// 减少碰撞
static final int hash(Object key) {
    int h;

    // 将hashCode的高16位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2、计算索引位置

int n = tab.length;

// &运算:0011 & 0101 = 0001。每一位上有0得0,都是1得1。
int index = (n - 1) & hash;

为什么再次处理hashCode()

因为当数组长度比较小时只有低16位参与运算,碰撞几率大。将原hash值右移16位,再与原hash值^运算产生的新hash高1

基于算法:

// 2^n为数组长度
x % 2^n = x & (2^n - 1)

这种计算方式在数组长度是2的n次方时得出的结果是均匀分布的(减少碰撞)。位运算有更高的效率,&运算占2个机器周期(一次逻辑运算和一次写)。

HashMap的put方法如下:

类的结构:

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

一个不明白的地方:AbstractMap已经实现了Map接口,为什么HashMap还要继承AvstractMap之后实现Map。