架构师带你深入解读HashMap("深入解析HashMap：架构师带你探秘原理与实践")

原创

ithorizon 7个月前 (10-20) 阅读数 16 #后端开发

深入解析HashMap：架构师带你探秘原理与实践

一、HashMap简介

HashMap是Java中常用的数据结构之一，用于存储键值对（Key-Value Pair）。它基于哈希表实现，具有高效的查询和插入性能。本文将深入解析HashMap的原理与实践，帮助大家更好地懂得和运用这一数据结构。

二、HashMap的工作原理

HashMap底层采用数组加链表（或红黑树）的做法实现。以下是HashMap的工作原理：

当我们向HashMap中插入一个键值对时，首先会计算键的哈希值，然后采取哈希值找到数组中的位置。

如果该位置为空，则直接在该位置插入键值对；如果该位置不为空，则需要判断链表（或红黑树）中是否存在相同的键。

如果链表中存在相同的键，则替换旧的值；如果不存在相同的键，则将新的键值对插入链表（或红黑树）的末尾。

三、HashMap的数据结构

HashMap首要由以下几个部分组成：

数组：HashMap底层采用数组存储键值对，数组的长度为2的幂次方，这样可以缩减哈希冲突的概率。

链表：当数组中的某个位置出现哈希冲突时，会采用链表的做法存储冲突的键值对。

红黑树：当链表的长度超过一定阈值时，链表会转换成红黑树，以节约查询效能。

四、HashMap的核心方法

HashMap的核心方法包括put、get、remove等。以下是这些方法的简要介绍：

1. put方法

put方法用于向HashMap中插入一个键值对。以下是put方法的伪代码：


public V put(K key, V value) {
    // 计算哈希值
    int hash = hash(key);
    // 找到数组中的位置
    int index = indexFor(hash, table.length);
    // 遍历链表，查找是否存在相同的键
    for (Entry e = table[index]; e != null; e = e.next) {
        if (e.hash == hash && e.key.equals(key)) {
            // 替换旧的值
            e.value = value;
            return e.value;
        }
    }
    // 插入新的键值对
    addEntry(hash, key, value, index);
    return null;
}

2. get方法

get方法用于从HashMap中获取一个键对应的值。以下是get方法的伪代码：


public V get(K key) {
    // 计算哈希值
    int hash = hash(key);
    // 找到数组中的位置
    int index = indexFor(hash, table.length);
    // 遍历链表，查找是否存在相同的键
    for (Entry e = table[index]; e != null; e = e.next) {
        if (e.hash == hash && e.key.equals(key)) {
            return e.value;
        }
    }
    return null;
}

3. remove方法

remove方法用于从HashMap中删除一个键值对。以下是remove方法的伪代码：


public V remove(K key) {
    // 计算哈希值
    int hash = hash(key);
    // 找到数组中的位置
    int index = indexFor(hash, table.length);
    // 遍历链表，查找并删除指定的键值对
    Entry e = table[index];
    Entry prev = null;
    while (e != null) {
        if (e.hash == hash && e.key.equals(key)) {
            if (prev == null) {
                table[index] = e.next;
            } else {
                prev.next = e.next;
            }
            return e.value;
        }
        prev = e;
        e = e.next;
    }
    return null;
}