HashMap解析

linxinzhe

发布于 2018-07-25 10:36:31

6250

发布于 2018-07-25 10:36:31

文章被收录于专栏：林欣哲林欣哲

数据结构之哈希表

在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)
数据结构的物理存储结构只有两种
- 顺序存储结构
- 链式存储结构
哈希表的主干就是数组。对于数组通过指定下标的查找，时间复杂度为O(1)
查找的本质：存储位置 = f(关键字)，f是一个哈希函数

哈希冲突：但是，键是可能存在冲突的，相当于不同的键得出了相同的哈希值。HashMap即是采用了链地址法，也就是数组+链表的方式。

HashMap的结构

HashMap的主干是一个Entry数组。

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Entry是HashMap中的一个静态内部类，它实现了一个链表结构。链表则是主要为了解决哈希冲突而存在的。

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
...
}

整体结构如下

解决的问题：哈希冲突
如果定位到的数组位置不含链表，即当前entry的next指向null，则一次查询即可。
如果定位到的数组包含链表
- 添加：O(1)，直接插入链表头部
- 查找：O(n)，遍历链表，key对象的equals方法逐一比对查找

HashMap的源码分析：插入

public V put(K key, V value) {
        //其允许存放null的key和null的value，放在table[0]
        if (key == null)
            return putForNullKey(value);

        int hash = hash(key);
        //得到键的哈希值，用来获取数组中的索引
        int i = indexFor(hash, table.length);
        //如果i处的Entry不为null，则需要在链表中添加，但是添加前需要看是否已存在，存在返回旧值，不存在则最终addEntry。
        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;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
        //添加前看是否需要扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
        // 获取指定 bucketIndex 索引处的 Entry
        Entry<K,V> e = table[bucketIndex];
        // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entr
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
}

HashMap的源码分析：读取

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
    final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        //通过哈希得到的index的e不为空则继续搜索链表
        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 != null && key.equals(k))))
                return e;
        }
        return null;
    }

HashMap的性能参数

initialCapacity初始容量
transientintsize; 实际存储的key-value键值对的个数
intthreshold; 最大容量，threshold一般为 capacity*loadFactory，HashMap在进行扩容时需要参考threshold。初始容量默认为16
finalfloatloadFactor; 负载因子，代表了table的填充度有多少，默认是0.75，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。
transientintmodCount; 用于防止多线程问题的快速失败。由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，则需要抛出异常ConcurrentModificationException

HashMap的扩容

HashMap数组的大小需要扩容时，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
loadFactor的默认值为0.75。默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置。
这是一个非常消耗性能的操作，可以预设一个大小。

参考

Java集合学习1：HashMap的实现原理，李大辉，http://tracylihui.github.io/2015/07/01/Java%E9%9B%86%E5%90%88%E5%AD%A6%E4%B9%A01%EF%BC%9AHashMap%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86/
HashMap实现原理及源码分析，dreamcatcher-cx，http://www.cnblogs.com/chengxiao/p/6059914.html