原创|你真的了解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数据碰撞的解决

因为哈希值有哈希冲突的存在，所以不同的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的简单使用

搞定~

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