HashMap 底层原理

原创

BNTang

发布于 2023-09-30 19:51:41

1730

发布于 2023-09-30 19:51:41

文章被收录于专栏：『学习与分享之旅』

Hash 与 Hash表与 HashCode

什么是 Hash

哈希 (hash) 简单的理解就是将任意长度的输入通过散列算法转换成固定长度的输出，这个输出一般称之为 散列码 或 哈希值 通过输出的结果来访问地址的数据结构

Hash 表

hash 表也称散列表（Hash table）哈希表是一种根据关键码去寻找值的数据映射结构也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度

HashCode

HashCode 通过 hash 函数计算得到，HashCode 就是在 hash 表中有对应的位置 HashCode 的存在主要是为了查找的快捷性，HashCode 是用来在散列存储结构中确定对象的存储地址的 Java 语言中，Object 对象有个特殊的方法：hashcode() hashcode() 表示的是 JVM 虚拟机为这个 Object 对象分配的一个 int 类型的数值

HashMap 数据结构

HashMap 的数据结构主要分为以下两个版本的改动。

JDK 1.7

采用的是 数组 + 链表

JDK 1.8

采用的是 数组 + 链表 + 红黑树

HashMap 的容量

指的是数组的大小如果不指定初始容量，默认大小是 1<<4，也就是 2 的 4 次方，也就是 16 的大小 DEFAULT_INITIAL_CAPACITY = 1 << 4;，Hash 表默认的初始容量

HashTable 数据结构

在 JDK1.7 当中 HashTable 数据结构为 数组 + 链表，假定现在有一个 HashMap 内容如下。

/**
 * @author BNTang
 **/
public class HashTest {
    public static void main(String[] args) {
        Map<String, Object> peopleMap = new HashMap<>(16);

        peopleMap.put("张三", "zs");
        peopleMap.put("李四", "ls");
        peopleMap.put("王五", "ww");
        peopleMap.put("赵六", "zl");
        peopleMap.put("周七", "zq");
        peopleMap.put("郑八", "zb");
    }
}

上面的代码我们先画一个简略的示意图，进行分析如下。

为什么不直接把 key 和 value 放到数组当中，我们想要把数据放到数组当中，如果按角标的顺序进行存放，可以这样存放如下图。

但是这样放在取数据的时候，我们取的时候就比较麻烦了，因为我们取的时候是根据 key 值来进行取的，如果直接这样放，要先通过遍历的方式来查找，找到对应的位置，才能取到对应的数据。

🐤那么这个时候数据该如何存到数组当中呢？其实还是有方式的，在 MashMap 中的 key 必须是引用数据类型，引用数据类型都会有一个 HashCode 值，这个值是 JVM 虚拟机为这个 Object 对象分配的一个 int 类型的数值，把 HashCode 的值放到数组当中去，但是 HashCode 的值是不确定的有可能比 16 要大很多，可以采用 key.hashcode % 16，取模之后，得到的结果就是 1-15 之间，在 HashMap 中并不是直接使用取模的方式控制在 1-15 之间，是采用位运算的方式，位运算的效率要高于取模，位运算效率最高，取模效率最差。

🐱‍💻源码分析

通过 异常 和 与运算，让得到的 hash 值更加散列，减少 hash 的 碰撞，如下的方法我只是给出来进行参考用，就是解释一下为什么它这样就可以保证计算的 hash 值在指定的范围之间。

static int indexFor(int h, int length) {
    return h & (length - 1);
}

取模之后得到一个结果，这个结果正好对应 1-15 之间的位置，假设 key 为张三 HashCode 取模的结果为 2，就把张三对应的 key, value 放到数组中角标为 2 的位置存储。

存取操作的时间复杂度为 O(1)。

Hash 碰撞问题

什么是 Hash 碰撞

通过 hash 方法操作后，得到了两个相同的结果在我们这里，我们对 HashCode 值进行 %16，有可能两个对象取模的结果是一样的因为有 Hash碰撞，数组的利用率很难达到 100%

解决 Hash 碰撞

为了解决 Hash 碰撞，在里面引入了链表，采用了 头 插入链表的方式。

链表的时间复杂度为 O(n)。

手写 HashMap

定义接口与实现

基础接口

创建 MyMap 接口内容如下

/**
 * @author BNTang
 **/
public interface MyMap<K, V> {
    /**
     * 添加元素
     *
     * @param k k
     * @param v v
     * @return {@link V}
     */
    V put(K k, V v);

    /**
     * 获取元素
     *
     * @param k k
     * @return {@link V}
     */
    V get(K k);

    interface Entry<K, V> {
        /**
         * 获取Key
         *
         * @return {@link K}
         */
        K getKey();

        /**
         * 获取Value
         *
         * @return {@link V}
         */
        V getValue();
    }
}

创建所对应的 MyHashMap 实现类内容如下

/**
 * @author BNTang
 **/
public class MyHashMap<K, V> implements MyMap<K, V> {
    @Override
    public V put(K k, V v) {
        return null;
    }

    @Override
    public V get(K k) {
        return null;
    }

    /**
     * @author BNTang
     */
    class Entry<K, V> implements MyMap.Entry {

        @Override
        public K getKey() {
            return null;
        }

        @Override
        public V getValue() {
            return null;
        }
    }
}

PUT 方法实现

/**
 * @author BNTang
 **/
public class MyHashMap<K, V> implements MyMap<K, V> {

    /**
     * 定义存储元素数组
     */
    private Entry<K, V>[] table = null;

    public MyHashMap() {
        this.table = new Entry[16];
    }

    private int size = 0;

    public int size() {
        return size;
    }

    @Override
    public V put(K k, V v) {
        // 1.获取k的hashcode%16 = hash值 对应数组当中的位置
        int hashValue = hash(k);

        // 2.判断数组当中对应位置有没有元素
        Entry<K, V> entry = table[hashValue];
        if (null == entry) {
            // 没有元素,直接存储 Entry<K,V>
            table[hashValue] = new Entry<>(k, v, hashValue, null);
            size++;
        } else {
            // 更新
            if (table[hashValue].k.equals(k)) {
                table[hashValue].v = v;
            } else {
                // 如果有元素,有hash碰撞,就要把数据使用头插法 插入到链表的头部,记录原来的值
                table[hashValue] = new Entry<>(k, v, hashValue, entry);
                size++;
            }
        }
        return table[hashValue].getValue();
    }

    /**
     * 哈希
     *
     * @param k k
     * @return int
     */
    private int hash(K k) {
        int index = k.hashCode() % 16;
        return index > 0 ? index : -index;
    }

    @Override
    public V get(K k) {
        return null;
    }

    /**
     * @author BNTang
     */
    class Entry<K, V> implements MyMap.Entry {

        /**
         * k
         */
        K k;
        /**
         * v
         */
        V v;
        /**
         * 哈希
         */
        int hash;
        /**
         * 下一个节点元素
         */
        Entry<K, V> next;

        /**
         * HashMap元素
         *
         * @param k    k
         * @param v    v
         * @param hash 哈希值
         * @param next 下一个节点元素
         */
        public Entry(K k, V v, int hash, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return this.k;
        }

        @Override
        public V getValue() {
            return this.v;
        }
    }
}

如上 Entry 内部类的 getKey、getValue 就直接返回对应的属性值即可，接下来就是获取元素 getValue 的实现

GET 方法实现

/**
 * @author BNTang
 **/
public class MyHashMap<K, V> implements MyMap<K, V> {

    /**
     * 定义存储元素数组
     */
    private Entry<K, V>[] table = null;

    public MyHashMap() {
        this.table = new Entry[16];
    }

    private int size = 0;

    public int size() {
        return size;
    }

    @Override
    public V put(K k, V v) {
        // 1.获取k的hashcode%16 = hash值 对应数组当中的位置
        int hashValue = hash(k);

        // 2.判断数组当中对应位置有没有元素
        Entry<K, V> entry = table[hashValue];
        if (null == entry) {
            // 没有元素,直接存储 Entry<K,V>
            table[hashValue] = new Entry<>(k, v, hashValue, null);
            size++;
        } else {
            // 更新
            if (table[hashValue].k.equals(k)) {
                table[hashValue].v = v;
            } else {
                // 如果有元素,有hash碰撞,就要把数据使用头插法 插入到链表的头部,记录原来的值
                table[hashValue] = new Entry<>(k, v, hashValue, entry);
                size++;
            }
        }
        return table[hashValue].getValue();
    }

    /**
     * 哈希
     *
     * @param k k
     * @return int
     */
    private int hash(K k) {
        int index = k.hashCode() % 16;
        return index > 0 ? index : -index;
    }

    @Override
    public V get(K k) {
        // 1.判断当前集合中有没有元素,如果没有就直接返加null
        if (size == 0) {
            return null;
        }

        // 2.根据k获取的entry
        Entry<K, V> entry = getEntry(k);

        // 3.返回entry当中的value
        return entry != null ? entry.getValue() : null;
    }

    private Entry<K, V> getEntry(K k) {
        // 1.把k进行hash
        int hashValue = hash(k);

        for (Entry<K, V> e = table[hashValue]; e != null; e = e.next) {
            if (hashValue == e.hash && e.getKey() == k || k.equals(e.getKey())) {
                return e;
            }
        }
        return null;
    }

    /**
     * @author BNTang
     */
    class Entry<K, V> implements MyMap.Entry {

        /**
         * k
         */
        K k;
        /**
         * v
         */
        V v;
        /**
         * 哈希
         */
        int hash;
        /**
         * 下一个节点元素
         */
        Entry<K, V> next;

        /**
         * HashMap元素
         *
         * @param k    k
         * @param v    v
         * @param hash 哈希值
         * @param next 下一个节点元素
         */
        public Entry(K k, V v, int hash, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return this.k;
        }

        @Override
        public V getValue() {
            return this.v;
        }
    }
}

测试并使用

/**
 * @author BNTang
 **/
public class HashTest {
    public static void main(String[] args) {
        MyMap<String, Object> personMap = new MyHashMap<>();

        personMap.put("张三", "zs");
        personMap.put("李四", "ls");
        personMap.put("王五", "ww");
        personMap.put("赵六", "zl");
        personMap.put("周七", "zq");
        personMap.put("郑八", "zb");

        System.out.println(personMap.get("张三"));
    }
}

HashMap 源码分析

PUT 方法源码分析

public V put(K key, V value) {
    // 判断数组为不为空
    if (table == EMPTY_TABLE) {
        
        // 如果数组为空,开始初始化数组
        inflateTable(threshold);
    }
    // 如果key为空,
    if (key == null)
        // 判断之前有没有过null的key, 如果有就平板, 没有就添加
        return putForNullKey(value);
    
    // 获取hash值
    int hash = hash(key);
    
    // 使用位运算,得出在数组当中的位置
    int i = indexFor(hash, table.length);
    
    // 添加或更新元素
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == 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;
}

初始容量问题

默认初始容量必须是 2 的指数次幂，如果不是 2 的指数次幂，会强行转化成 2 的指数次幂，采用向上接近的转换方式，假设初始容量为 14，不是 2 的指数次幂，向上比较接近的是 2 的 4 次方，所以初始容量会转化成 16。

为什么要保证 capacity 是 2 的次幂呢？在上面我们看出，计算角标的方式为按位与的形式，因为 length 永远是 2 的次幂，所以 length-1 通过二进制表示，永远都是尾端以连续 1 的形式表示，这样做的好处，& 运算速度快，至少比 % 取模运算块，能保证索引值肯定在 capacity 中，不会超出数组的长度，(n - 1) & hash，当 n 为 2 次幂时，会满足一个公式：(n - 1) & hash = hash % n。在源码中，计算数组位置。

取出 key 的 HashCode，进行一些异常和与操作，目的让得到的值更加 hash，减少 hash 碰撞。

在源码采用按位与的形式计算得出在数组当中的位置，在 HashMap 中并不是直接使用取模的方式控制在 1-15 之间，是采用位运算的方式，位运算的效率要高于取模，位运算效率最高，取模效率最差，

HashMap 扩容

HashMap 中扩容是根据阈值 threshold 来进行的，threshold 是根据当前 HashMap 中存了多少 element，threshold 的值等于容量 capacity * 扩容阈值比率0.75，DEFAULT_LOAD_FACTOR = 0.75，假设当前容量是 16，当容量到 16 * 0.75 = 12 时，扩容。

扩容过程

会创建一个新的数组，大小为原来的 2 倍，创建完毕后，开始转移数据。

void transfer(Entry[] newTable, boolean rehash) {
    // 新数组的长度
    int newCapacity = newTable.length;
    
    // 遍历原来的数组,取出每一个元素
    for (Entry<K, V> e : table) {
        
        // 每取一个元素时, 判断为不为空
        while (null != e) {
            
            // 如果不为空, 再取出下一个节点位置,next记录
            Entry<K, V> next = e.next;
            
            if (rehash) {// 原key是否重新散列
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            
            // 计算出新的数组角标位置
            int i = indexFor(e.hash, newCapacity);
            
            // 把当前元素的下一个位置指向新数组的位置
            e.next = newTable[i];
            
            // 把当前元素设置到新数组当中
            newTable[i] = e;
            
            // 继续下一个节点操作
            e = next;
        }
    }
}

遍历原来的数组当中的每一个元素，链表当中同样也会遍历，采用的是一个嵌套循环，遍历出的数据再一次进行 hash，算出对应的 HashCode，存储到新数组指定的位置当中。

单线程转移示列图

🐤原数据

🐤转移过程

假定原数据为如下图的内容。

执行到第 9 行时。

执行到第 14 行，假设结果为 3，执行到第 16 行时，取出 3 位置存储的值，由于是第一次，里面的值为 null，把 null 设置为当前 e 的 next

执行到第 18 行时，把当前 e 元素设置到新数组当中。

执行到第 19 行时，切换元素。

开始新一轮循环。

开始下一轮，直到循环结束。

最后一轮。

多线程扩容问题

两个线程 t1 和 t2，假设 t2 先执行，t2 执行到 Entry<K, V> next = e.next; 发生阻塞，t1 执行结束后，t2 才继续执行，阻塞前。

等 t1 线程执行结束后。

t2 线程继续 Entry<K, V> next = e.next; 代码之后执行。

造成就两个节点互样指向，变成了双向链表，在 put 元素时，循环会一直结束不了。

代码存在问题

在 1.7 当中采用的是 数组+链表 的形式进行数据的存储如果链表当中的数据比较的时候，查询的效率就行降低在 1.8 里面引入了红黑树

1.8 说明

在 1.8 当中引入了一些属性

TREEIFY_THRESHOLD = 8：树化的阈值，当某个桶节点数量大于 8 时，会转换为红黑树，查询效率提高
UNTREEIFY_THRESHOLD = 6：当某个桶节点数量小于 6 时，会转换为链表，前提是它当前是红黑树结构

1.8 之后采用的是尾插法，因为每一次插入元素，要判断是否达到树化阈值，如果达到下一次就要转成红黑树，每一次都要遍历，所以直接遍历完的，把新的元素插入到遍历的最后一个之后，并不是到达 8 个之后，就会立即进行树化，要先判断当前的数组是否小于 64，如果小于的话，不会进行树化，而是进行扩容，当大于 64 的时候才会决定要树化。

1.8 源码

我正在参与2023腾讯技术创作特训营第二期有奖征文，瓜分万元奖池和键盘手表

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

2023腾讯·技术创作特训营第二期

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

2023腾讯·技术创作特训营第二期

登录后参与评论

0 条评论

热度