转载

HashMap实现原理学习

HashMap源码来自:android-25/java/util/HashMap

一、构造方法

static final int MAXIMUM_CAPACITY = 1 << 30;
static final int DEFAULT_INITIAL_CAPACITY = 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 参数默认为 4,0.75f
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 4 < MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        // 4 = DEFAULT_INITIAL_CAPACITY
        else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
            initialCapacity = DEFAULT_INITIAL_CAPACITY;
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        threshold = initialCapacity;
        init();
}

ps:

init()为空方法;构造方法中只是做了HashMap数组容量字段的一个简单限制,最大为MAXIMUM_CAPACITY,最小为DEFAULT_INITIAL_CAPACITY

二、添加元素 put(K key, V value)

添加数据时,若出现冲突。

Java是通过 数组+链表 的形式解决冲突。效果如下图所示:

HashMap实现原理学习

  • HashMap中有一个默认长度为16的table数组,当数组的容量达到默认长度的0.75倍时,则扩容两倍;
  • 其中table数组的每一项数据结构如下:
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
    final K key; // key
    V value;     // value
    HashMapEntry<K,V> next; // 链表的下一项
    int hash;    // key 的hash值
}

下面通过跟中源码查看:

table数组初始化

介绍put(K key, V value)方法前,先简单介绍table数组初始化

// 添加key value
public V put(K key, V value) {
    // 如果table列表为null,则用过inflateTable方法初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    ...
    return null;
}
// 初始化table数组
private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        // 这里计算一个2的n次方的数组容量,默认为2的4次方,为16
        int capacity = roundUpToPowerOf2(toSize);
        // 计算数组容量的0.75倍,超过数组容量0.75倍时,数组需要扩容
        float thresholdFloat = capacity * loadFactor;
        if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
            thresholdFloat = MAXIMUM_CAPACITY + 1;
        }
        // 数组容量的0.75倍
        threshold = (int) thresholdFloat;
        // 初始化数组,默认容量capacity为16
        table = new HashMapEntry[capacity];
}

ps:

这里默认初始化了一个数组容量为16的table数组,其中关于roundUpToPowerOf2(toSize)为什么为2的n次方的问题,在下边进行介绍

put(K key, V value)

// 添加key value
public V put(K key, V value) {
        // 如果table列表为null,则用过inflateTable方法初始化
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        // key 为null,则添加key为null的value
        if (key == null)
            return putForNullKey(value);
        // 根据key获取hash值
        // Jenkins hash算法,可参考以下链接:
        // https://en.wikipedia.org/wiki/Jenkins_hash_function
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        //  h & (length-1) 取余太消耗性能,这里通过位运算达到同样的效果
        // 获取该key在table 数组的index
        int i = indexFor(hash, table.length);
        // 循环table[i]对应的链表
        // 如果 hash值相同 && key相同,则替换对应value,并返回老的value值
        // 注:这里只是循环table[i]位置的链表,对于table数组未做循环
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 如果 hash值相同 && key相同,则替换对应value,并返回老的value值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        // 以下两种情况,则需要通过createEntry方法来看了
        // hash相同 && key不同
        // hash不同 && key不同 
        addEntry(hash, key, value, i);
        return null;
}

ps:

以上介绍了添加数据时,“如果 hash值相同 && key相同,则替换对应value,并返回老的value值”,但对于“hash相同 && key不同”与“hash不同 && key不同”情况,则需要在createEntry中进行说明

void addEntry(int hash, K key, V value, int bucketIndex) {
        // 当数组的占用量,达到数组长度的0.75倍时,则需要扩容,扩展后的容量为原容量的2倍
        // 数组扩容首先创建一个长度为原数组两倍的数组,然后将老的数组数据赋值给新数组的对应项项目
        // 数组扩容的代码,这里不再说明
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        // hash相同 && key不同
        // hash不同 && key不同 
        createEntry(hash, key, value, bucketIndex);
}
// hash相同 && key不同
// hash不同 && key不同 
void createEntry(int hash, K key, V value, int bucketIndex) {
        // 取出table[bucketIndex]数组的原有值,可能为null,可能为HashMapEntry
        // 若为null,则直接将value放在table[bucketIndex]位置就ok了
        // 若不为null,则将新数组放到table[bucketIndex]位置,老数组放到新数据链表的next字段
        // hash冲突就是这样解决了,可以看到确实与上图一致,为数组+链表的方式解决冲突
        HashMapEntry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
        size++;
}

ps:

通过createEntry方法,我们看到HashMap中通过数组+链表方式解决了Hash冲突,呼应了上图

roundUpToPowerOf2(toSize)为什么为2的n次方

打个比方:

  • 当数组长度为15时,添加数组时 h & (length-1) 计算成为 hash&14(0x1110) ,那么最后一位永远是0,从而造成table数组中 1(0x0001),3(0x0011),5(0x0101),7(0x0111),9(0x1001),11(0x1011)等位置永远不可以存放数据,从而造成空间浪费;
  • 更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率。

ps:

关于 roundUpToPowerOf2(toSize)为什么为2的n次方问题,详细可查看

http://blog.csdn.net/yyh35209...

========== THE END ==========

原文  https://segmentfault.com/a/1190000021126417
正文到此结束
Loading...