Java容器--HashMap源码解析

前言

最近突然对Java中的容器产生了兴趣，比如：HashMap是使用什么结构存储数据的？当hash值相同时，会采用什么样的策略？Set是怎么实现的，为何能保证数据的唯一性？当这样的问题想要弄个明白时，我知道，是时候通过查看源码来解惑了，所以打算写关于Java容器的系列文章。

源码解析

存储原理

以哈希函数为对16取余数的哈希表来举例，那么需要有16个槽，槽1、槽2、槽3...槽16形成一个数组，而每个槽中都可能存储多个键值对，所以每个槽中使用链表来存储。
当要存储一个键值对(key,value)时

1. 首先对key求hash值，往往是一个非常大的数字
2. 对hash求余数，得到槽的下标index
3. 将这个键值对插入到链表的首部

接下来，我们通过源码来查看实现的细节。

重要成员变量的说明

    //创建HashMap时，最小容量，即最少要创建四个空间
    private static final int MINIMUM_CAPACITY = 4;
    
    //HashMap最多能够存储的键值对个数
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    //即上文中所说的，槽1、槽２......槽16形成的数组，每个位置都存储一个链表的头结点
    transient HashMapEntry<K, V>[] table;

源码解析

首先我们来看一下put函数

public V put(K key, V value) {
        if (key == null) {
            return putValueForNullKey(value);
        }

        int hash = Collections.secondaryHash(key);  //获取key的hash值
        HashMapEntry<K, V>[] tab = table;
        int index = hash & (tab.length - 1);  //相当于对hash取余数，获得数组的下标
        for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {  //tab[index]存储了一个链表,这个循环用来遍历链表
            if (e.hash == hash && key.equals(e.key)) {  //如果以前存储过相同key的键值对
                preModify(e);
                V oldValue = e.value; 
                e.value = value; //将旧value存储为新value
                return oldValue; //返回旧value
            }
        }

        // No entry for (non-null) key is present; create one
        modCount++;
        if (size++ > threshold) {  //存储的键值对个数比较多了，需要扩容
            tab = doubleCapacity();  //将容量扩大为2倍
            index = hash & (tab.length - 1);  //在扩容后的数组中，对应新的index
        }
        addNewEntry(key, value, hash, index);  //将键值对添加到tab[index]存储的链表中
        return null;
    }

注释已经写的非常详细了，不再赘述，下面看一下addNewEntry函数

    void addNewEntry(K key, V value, int hash, int index) {
        table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
    }

    HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }

HashMapEntry是链表的一个节点，它内部的next变量用来指向下一个节点，所以addNewEntry函数的作用就是：把要put的键值对添加到对应链表的首部。

下面我们来看一下get函数：

    public V get(Object key) {
        if (key == null) {
            HashMapEntry<K, V> e = entryForNullKey;
            return e == null ? null : e.value;
        }

        int hash = Collections.secondaryHash(key);  //获取key的hash值
        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {  //遍历链表
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {   //如果key为同一个引用，或者hash、key都相等
                return e.value;
            }
        }
        return null;
    }

线程安全性

通过查看源码，发现HashMap并没有处理线程同步问题，所以大家在多个线程操作HashMap时，一定要使用同步来确保数据的准确性。

如果有疑问或者发现本文的错误之处，欢迎评论～