谈谈我对HashMap扩容机制的理解及底层实现

简介: 谈谈我对HashMap扩容机制的理解及底层实现



一、HashMap的底层实现

HashMap 是 Java 中常用的数据结构之一,用于存储键值对。它的底层实现是基于哈希表(Hash Table)。以下是 HashMap 的底层实现细节:

  1. 数组: HashMap 内部维护一个数组,数组的每个元素称为桶(bucket)。数组的长度通常是2的幂,这是为了便于哈希函数计算索引值。
  2. 链表和红黑树: 在每个桶中,如果发生哈希冲突(即两个不同的键具有相同的哈希值),那么这些键值对会以链表的形式存储在同一个桶中。从Java 8 开始,当链表的长度超过一定阈值时,会将链表转换为红黑树,以提高查询性能。
  3. 哈希函数: HashMap 使用键的哈希码来计算索引值。哈希码是通过调用键的 hashCode() 方法得到的。计算索引值的过程涉及到取模运算,即 index = hashCode % arrayLength
  4. 扩容:HashMap 中的元素个数超过了容量与负载因子的乘积时,就会触发扩容操作。负载因子是一个表示填充程度的浮点数,默认为0.75。扩容时,数组的长度会变为原来的两倍,并且原来的键值对需要重新计算哈希码和索引值,然后放入新的数组中。
  5. 并发性: HashMap 在多线程环境下是不安全的,因为多个线程可能同时修改 HashMap,导致数据不一致。在Java 8及之后的版本中,提供了 ConcurrentHashMap 来解决这个问题,它通过分段锁和 CAS 操作来保证并发安全性。

参考资料

HashMap 源码TreeBin 类(红黑树容器)

二、HashMap扩容机制

概念

HashMap 的扩容是为了保持其在负载因子(load factor)范围内的性能。负载因子是一个表示填充程度的浮点数,默认值为 0.75。当 HashMap 中的元素数量达到容量与负载因子的乘积时,就会触发扩容操作。

详细扩容:

1、初始容量

当创建一个新的 HashMap 时,它会有一个初始容量,通常是16。这个初始容量可以在构造函数中指定,但如果不指定,默认值为16。

2、添加元素

当往 HashMap 中添加键值对时,首先计算键的哈希码,并根据哈希码计算索引值。如果该索引位置没有元素,直接插入;如果有元素,发生哈希冲突,就会以链表的形式添加到相应的桶中。

3、元素数量检查

在每次添加元素后,HashMap 会检查当前元素的数量是否超过了容量与负载因子的乘积,即 size > threshold = capacity * loadFactor

4、触发扩容

如果元素数量超过了阈值,就会触发扩容操作。扩容时,HashMap 将会创建一个新的数组,长度是原数组的两倍(newCapacity = oldCapacity * 2),然后将原数组中的元素重新计算哈希码和索引值,放入新数组中。

5、迁移元素

扩容后,原数组中的每个桶可能包含一个链表或一棵红黑树。HashMap 将遍历原数组中的每个桶,然后将其中的元素迁移到新数组中。在迁移的过程中,由于新数组长度是原数组长度的两倍,因此每个元素的索引值可能会发生变化。

6、更新容量和阈值

扩容后,HashMap 更新自己的容量和阈值。容量变为新数组的长度,阈值变为新容量与负载因子的乘积。

代码:

import java.util.Arrays;
import java.util.LinkedList;
public class MyHashMap<K, V> {
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private Node<K, V>[] table;
    private int size;
    private int threshold;
    @SuppressWarnings("unchecked")
    public MyHashMap() {
        table = new Node[DEFAULT_INITIAL_CAPACITY];
        threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    }
    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null");
        }
        if (size + 1 > threshold) {
            resize();
        }
        int hash = hash(key);
        int index = getIndex(hash, table.length);
        if (table[index] == null) {
            table[index] = new Node<>(hash, key, value);
            size++;
        } else {
            LinkedList<Node<K, V>> bucket = table[index].getBucket();
            for (Node<K, V> node : bucket) {
                if (node.key.equals(key)) {
                    // Key already exists, update the value
                    node.value = value;
                    return;
                }
            }
            // Key does not exist in the bucket, add a new node
            bucket.add(new Node<>(hash, key, value));
            size++;
        }
    }
    private void resize() {
        int oldCapacity = table.length;
        int newCapacity = oldCapacity * 2;
        threshold = (int) (newCapacity * DEFAULT_LOAD_FACTOR);
        Node<K, V>[] newTable = new Node[newCapacity];
        for (Node<K, V> node : table) {
            if (node != null) {
                LinkedList<Node<K, V>> bucket = node.getBucket();
                for (Node<K, V> entry : bucket) {
                    int hash = hash(entry.key);
                    int index = getIndex(hash, newCapacity);
                    if (newTable[index] == null) {
                        newTable[index] = new Node<>(hash, entry.key, entry.value);
                    } else {
                        newTable[index].getBucket().add(new Node<>(hash, entry.key, entry.value));
                    }
                }
            }
        }
        table = newTable;
    }
    private int hash(K key) {
        // Simplified hash function for illustration purposes
        return key.hashCode();
    }
    private int getIndex(int hash, int length) {
        // Simplified index calculation for illustration purposes
        return hash % length;
    }
    private static class Node<K, V> {
        private final int hash;
        private final K key;
        private V value;
        private LinkedList<Node<K, V>> bucket;
        public Node(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.bucket = new LinkedList<>();
            this.bucket.add(this);
        }
        public LinkedList<Node<K, V>> getBucket() {
            return bucket;
        }
    }
    public static void main(String[] args) {
        MyHashMap<String, Integer> myHashMap = new MyHashMap<>();
        myHashMap.put("One", 1);
        myHashMap.put("Two", 2);
        myHashMap.put("Three", 3);
        // ... (additional testing and usage)
    }
}

相关文章
|
27天前
|
存储 Java
HashMap的扩容机制是怎样的
在Java中,HashMap 是一个基于哈希表的键值对集合,它以其高效的存取性能而广泛使用。HashMap 的扩容机制是其性能优化的关键部分,本文将详细介绍这一机制的工作原理和过程。
|
2月前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
69 5
|
2月前
|
存储
让星星⭐月亮告诉你,HashMap的put方法源码解析及其中两种会触发扩容的场景(足够详尽,有问题欢迎指正~)
`HashMap`的`put`方法通过调用`putVal`实现,主要涉及两个场景下的扩容操作:1. 初始化时,链表数组的初始容量设为16,阈值设为12;2. 当存储的元素个数超过阈值时,链表数组的容量和阈值均翻倍。`putVal`方法处理键值对的插入,包括链表和红黑树的转换,确保高效的数据存取。
63 5
|
2月前
|
存储
HashMap扩容机制
【10月更文挑战第11天】 `HashMap`的扩容机制是其重要特性之一。当容量达到负载因子(默认0.75)时,会触发扩容。扩容时,新容量通常是原容量的两倍,元素需重新哈希并迁移到新数组中。此过程涉及大量计算和迁移,可能影响性能。合理设置初始容量和负载因子,可减少不必要的扩容。在多线程环境中,还需注意线程安全问题。
|
2月前
|
算法 索引
让星星⭐月亮告诉你,HashMap的resize()即扩容方法源码解读(已重新完善,如有不足之处,欢迎指正~)
`HashMap`的`resize()`方法主要用于数组扩容,包括初始化或加倍数组容量。该方法首先计算新的数组容量和扩容阈值,然后创建新数组。接着,旧数组中的数据根据`(e.hash & oldCap)`是否等于0被重新分配到新数组中,分为低位区和高位区两个链表,确保数据迁移时的正确性和高效性。
70 3
|
2月前
|
算法 索引
HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导
HashMap在扩容时,会创建一个新数组,并将旧数组中的数据迁移过去。通过(e.hash & oldCap)是否等于0,数据被巧妙地分为两类:一类保持原有索引位置,另一类索引位置增加旧数组长度。此过程确保了数据均匀分布,提高了查询效率。
46 2
|
7月前
|
存储 安全 算法
【JAVA】HashMap扩容性能影响及优化策略
【JAVA】HashMap扩容性能影响及优化策略
|
2月前
|
存储 算法 安全
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
HashMap常见面试题:红黑树、散列表,HashMap实现原理、扩容机制,HashMap的jd1.7与jdk1.8有什么区别,寻址算法、链表何时升级为红黑树、死循环
|
4月前
|
Java 索引
【Java集合类面试九】、介绍一下HashMap的扩容机制
HashMap的扩容机制包括初始容量16,以2的次方进行扩充,使用负载因子0.75判断是否扩容,以及链表长度达到阈值时转换为红黑树,以优化性能。
【Java集合类面试九】、介绍一下HashMap的扩容机制
|
3月前
|
存储 算法 Java
深入剖析HashMap:理解Hash、底层实现与扩容机制
【9月更文挑战第6天】在Java编程中,`HashMap`是一个常用的数据结构,其高效性和可靠性依赖于深入理解哈希、底层实现及扩容机制。哈希通过散列算法将键映射到数组索引,采用链表或红黑树处理冲突;底层实现结合数组与链表,利用2的幂次方长度加快定位;扩容机制在元素数量超过负载因子与数组长度乘积时触发,通过调整初始容量和负载因子可优化性能。
114 3