Java基础（8）HashMap

你的名字 2024-05-06 23:23 61阅读 0赞

`HashMap` 在 Java 中是一种广泛使用的基于散列的 Map 实现，它存储键值对，并且允许使用 `null` 值和 `null` 键。`HashMap` 的性能主要依赖于两个参数：初始容量和负载因子。为了更好地理解 `HashMap`，我们需要深入其实现细节，包括它如何存储数据、处理冲突、扩容以及迭代。

#### 基本结构 ####

`HashMap` 内部基于一个动态数组（Node 类型的数组）实现，每个数组位置也被称为“桶”。每个 Node 包含四个基本组成部分：`int hash`，`K key`，`V value` 和 `Node<K,V> next`。当发生哈希冲突时，节点会以链表的形式存储在同一个桶中，Java 8 引入了当链表长度大于某个阈值（默认为 8）时，链表转换为红黑树的优化。

#### 哈希函数 ####

`HashMap` 通过 `key.hashCode()` 计算键的哈希码，然后通过额外的哈希函数来减少冲突。Java 8 中对键的 `hashCode()` 返回值的高位也参与运算，增加了随机性，减少了冲突的可能。

#### 存储与检索 ####

*  **put(K key, V value)**: 添加元素时，首先计算 key 的哈希值，以确定其在数组中的位置。如果该位置无任何元素，直接存储；如果有元素（存在冲突），则以链表（或红黑树）的形式存储新的节点。
 *  **get(Object key)**: 获取元素时，也是通过计算哈希值找到对应的桶，然后遍历链表（或红黑树）来查找键匹配的节点。

#### 扩容 ####

当实际大小超过了容量与负载因子乘积的时候（`size > capacity * loadFactor`），`HashMap` 会进行扩容，即创建一个新的节点数组，大小是原数组的两倍，并重新计算每个元素在数组中的位置。

#### 源码片段与分析 ####

由于篇幅限制，以下仅展示 `HashMap` 的关键方法的逻辑概述，不是直接的源码：

public V put(K key, V value) {
        
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果数组为空或者长度为0，进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果计算出的位置为空，直接新建节点存储
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        
            // 发生哈希冲突，处理冲突
            Node<K,V> e; K k;
            // 检查第一个元素是否就是要放入的key
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果是红黑树节点，调用红黑树的插入方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        
                // 遍历链表
                for (int binCount = 0; ; ++binCount) {
        
                    if ((e = p.next) == null) {
        
                        p.next = newNode(hash, key, value, null);
                        // 链表长度达到阈值，转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果找到了相同的key，跳出循环进行值的替换
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 如果存在相同的key，替换旧值
            if (e != null) {
        
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 超过最大容量，扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

#### 总结 ####

`HashMap` 是 Java 集合框架中的重要组成部分，基于散列的机制提供了快速的查找、插入和删除操作。通过理解其内部结构和源码实现，可以更好地在实际应用中使用它，以及避免一些常见的陷阱，例如忽略哈希冲突处理和扩容对性能的影响。