原创|你真的了解HashMap吗?(HashMap源码分析)

前言

讲讲hashMap,简单的东西你还真不一定理解,真心的觉得需要有一篇文章把它给讲明白,这样就再也不怕面试被问到了。

**HashMap介绍
HashMap初始化
HashMap扩容机制
HashMap数据结构
HashMap哈希冲突的解决
HashMap使用**

一、HashMap介绍

他是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。另外,HashMap是非线程安全的,而Hashtable是线程安全的。

HashMap是继承了AbstractMap类,实现了 Map,Cloneable, Serializable 接口.
public class HashMap<K,V>
    extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

二、HashMap初始化

重要参数说明

//初始化的容量大小
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //最大容量大小
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap初始化的时候就做两件事,初始化了容量(比作一个桶)的大小为16和负载因子为0.75

public HashMap() {
     //初始化桶大小DEFAULT_INITIAL_CAPACITY=16  
     //负载因子DEFAULT_LOAD_FACTOR=0.75
     this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
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);
        //初始化负载因子0.75
        this.loadFactor = loadFactor;
        //初始化桶大小16
        threshold = initialCapacity;
        init();
    }

三、HashMap扩容机制

负载因子可以理解为饱满度,负载因子越大,占用的的空间越小,但是查询的效率越低。负载因子越小,占用空间越大,但是会提高查询效率。这是由数据结构决定的,下面讲。

HashMap 的实际容量就是因子*容量,其默认值是 16×0.75=12;这个很重要,对效率有一定影响!当存入HashMap的对象超过这个容量时,HashMap 就会就需要 resize(扩容2倍后重排)。

private void inflateTable(int toSize) {
        //最接近且大于toSize的2的冪数
        int capacity = roundUpToPowerOf2(toSize);
        //定义最大的实际容量,超过这个值就需要扩容
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //定义Entry数组,放put数据
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
  }
  //最接近且大于number的2的冪数,例如number为3返回结果是4,number为4返回结果为4
   private static int roundUpToPowerOf2(int number) {
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }
//添加元素,并判断是否需要扩容
void addEntry(int hash, K key, V value, int bucketIndex) {
      //size为当前数组大小,threshold为实际最大容量,如果大于就扩容
        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 resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //判断老的数组是否等于最大容量,如果等于不允许扩容
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        //定义新的数据
        Entry[] newTable = new Entry[newCapacity];
        //重新再新的数组中定义老的数据
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    //需要重新在新的数组中计算保存位置,并保存
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        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);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

因为重新创建新的数据,重新计算元素的存储位置非常的影响性能,所以最好预估元素的多少,在创建HashMap的时候定义它的大小,最好为2的冪数,这样可以更好的利用空降。

四、HashMap数据结构

HashMap是一个散列桶(数组和链表),它存储的内容是键值对key-value映射,数组和链表的数据结构,能在查询和修改方面继承了数组的线性查询和链表的寻址修改。(横排表示数组,纵排表示链表)

原创|你真的了解HashMap吗?(HashMap源码分析)

五、HashMap数据碰撞的解决

因为哈希值有哈希冲突的存在,所以不同的key可能有相同的哈希值。这个是后就需要通过链表结构来解决问题了。

正常情况,当我们put存储一个key-value数据的时候,HashMap会计根据key的哈希值计算应该在桶中保存的位置,判断该位置是否有数据,如果有数据,需要判断hash和key时候相等,如果相等,新的值替换老的值,并返回老的值。(这个不是“碰撞”,这中情况key是一样的)
public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        //计算哈希
        int hash = hash(key);
        //计算桶中的位置
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
          //判断哈希和key是否一样
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {        //一样
              //哈希一样,key也一样
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //i位置数据为空;或者数据不为空,hash不一样;或者哈希一样,key不一样
        modCount++;
        //添加
        addEntry(hash, key, value, i);
        return null;
    }

i位置数据为空;或者数据不为空,hash不一样;或者哈希一样(哈希碰撞),key不一样,走下面流程:

下面源码中,bucketIndex为新的数据在数组中的位置,如果这个位置没有数据,会保存新数据,并且它在链表中的下一数据是null(e为null),如果这个位置已经有数据,会在这个位置保存新的数据,它在链表中的下一个数据是老的数据(e)。

void createEntry(int hash, K key, V value, int bucketIndex) {
        //获取当前位置的数据e,有可能是null
        Entry<K,V> e = table[bucketIndex];
        //当前位置保存新的数据,历史数据e为新数据的链表相联的数据
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
}

假如哈希值不一样,会产生碰撞吗?答案是肯定的.

首先我们看一下,hashMap中数据在桶中位置计算方式

static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

“与”运算扩展:

参加运算的两个数据,按二进制位进行“与”运算。

运算规则:0&0=0;0&1=0;1&0=0;1&1=1;

即:两位同时为“1”,结果才为“1”,否则为0

**举例说明:
1&(16-1)=1
17&(16-1)=1**

所以我们可以理解,当桶的容量是固定的时候,负载因子越大,最大实际容量就会越大,需要保存的数据就越多。“碰撞”的情况出现的情况就会更多,增加了HashMap中链表结构中的数据,降低查询的效率。增加了空间利用率。

相反,当负载因子越小的时候,桶的实际容量就会越小,可以存的数据越少,碰撞情况减少,减少链表数据,增加查询效率。降低了空间利用率。

六、HashMap的简单使用

原创|你真的了解HashMap吗?(HashMap源码分析)

搞定~

喜欢的小伙伴记得关注一下~可以免费领取学习资料~

原创|你真的了解HashMap吗?(HashMap源码分析)

相关推荐