解释一下HashMap 的 get 方法逻辑

参考回答

HashMapget(Object key) 方法用于根据键(key)获取对应的值(value)。其核心逻辑是:

  1. 根据键的 hashCode() 计算哈希值,确定该键所在的桶(bucket)。
  2. 遍历该桶中的链表(或红黑树)来查找目标键。
  3. 如果找到对应的键,返回其对应的值;否则返回 null

详细讲解与拓展

1. HashMap 的底层数据结构

  • HashMap 的底层是一个数组,每个数组元素是一个链表或红黑树(在冲突元素多时)。
  • 通过键的哈希值确定数据存储在哪个数组索引位置(即“桶”)。

2. get 方法的核心逻辑

get(Object key) 的执行过程如下:

(1) 计算哈希值
  • 首先,HashMap 使用键的 hashCode() 方法计算哈希值,并通过位运算进一步压缩哈希值,以确定该键对应的桶(数组索引位置)。

  • 源码中,计算哈希值的方法:

    static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    • key.hashCode():计算键的哈希值。
    • h ^ (h >>> 16):高位和低位混合,减少哈希冲突。
(2) 定位桶
  • 根据计算得到的哈希值,找到该键所在的桶(bucket)。

  • 数组索引通过以下公式计算:index = (n – 1) & hash其中,n是数组的长度,hash

    是上一步计算的哈希值。

    • 位与运算 (&) 是一种高效的取模方式,用来确保索引值在数组范围内。
(3) 遍历桶中的节点
  • 如果桶中没有元素(即链表为空),直接返回 null
  • 如果桶中有元素,则通过以下步骤查找目标键:
    1. 遍历桶中的链表或红黑树。
    2. 比较每个节点的哈希值是否等于目标键的哈希值。
    3. 如果哈希值相等,再通过 equals() 方法进一步比较键是否相等。
    4. 如果找到了目标键,返回对应的值;否则继续查找。
(4) 找不到键时
  • 如果遍历完链表或红黑树仍未找到目标键,返回 null

3. get 方法源码分析

以下是 Java 8 中 HashMapget 方法的核心源码:

public V get(Object key) {
    Node<K,V> e;  // 定义节点
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;   // 哈希表
    Node<K,V> first, e; // 当前桶的第一个节点
    int n;
    K k;

    // 判断哈希表是否为空,并根据哈希值找到桶
    if ((tab = table) != null && (n = tab.length) > 0 && 
        (first = tab[(n - 1) & hash]) != null) {

        // 检查第一个节点是否是目标节点
        if (first.hash == hash && // 比较哈希值
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;

        // 遍历链表或树查找目标节点
        if ((e = first.next) != null) {
            if (first instanceof TreeNode) // 如果是红黑树,则在树中查找
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);

            do { // 如果是链表,则遍历链表
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null; // 没找到返回 null
}

4. 关键点详解

(1) 哈希值计算

  • hash(key) 方法会对键的哈希值进行高低位混合(h ^ (h >>> 16)),减少冲突。
  • 计算索引时使用 (n - 1) & hash,通过位运算代替取模操作,效率更高。

(2) 桶内查找

  • 链表查找:
    • 如果冲突较少,桶中的节点以链表形式存储,按顺序遍历链表查找目标节点。
  • 红黑树查找:
    • 如果桶中的元素数量超过阈值(默认 8),链表会转换为红黑树,红黑树的查找时间复杂度为 O(log n)

(3) 键的相等性比较

  • 首先比较键的哈希值(hash)。
  • 如果哈希值相同,再通过 equals() 方法比较键的内容。

5. 示例代码

示例:模拟 get 方法的逻辑

import java.util.HashMap;

public class HashMapGetExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        // 添加元素
        map.put("A", 1);
        map.put("B", 2);
        map.put("C", 3);

        // 使用 get 方法
        System.out.println("Value for key 'A': " + map.get("A")); // 输出:1
        System.out.println("Value for key 'D': " + map.get("D")); // 输出:null
    }
}

6. get 方法的时间复杂度

  1. 最优情况
    • 如果键的分布均匀,且桶内没有冲突(每个桶只存一个元素),get 操作的时间复杂度为 O(1)
  2. 最差情况
    • 如果发生大量哈希冲突,所有元素都存储在同一个桶内,链表查找的时间复杂度为 O(n)
    • 在 Java 8 中,引入红黑树后,最差情况下的时间复杂度降为 O(log n)

7. 总结

  1. 执行步骤
    • 计算哈希值。
    • 定位桶的位置。
    • 遍历桶内的链表或红黑树。
    • 比较哈希值和键的内容,找到匹配的键值对。
  2. 时间复杂度
    • 在理想情况下为 O(1),在最差情况下(冲突严重时)为 O(log n)
  3. 性能优化
    • Java 8 通过红黑树优化了冲突场景下的性能,避免了链表退化为线性查找。
  4. 注意事项
    • 键的 hashCode()equals() 方法的正确性至关重要,直接影响 get 方法的准确性和效率。

发表评论

后才能评论