可视化图解算法64：哈希表基础

原创

用户11589437

修改于 2025-10-16 15:40:42

1040

文章被收录于专栏：数据结构与算法精讲数据结构与算法精讲

哈希表（Hash table），也被称为散列表，是一种基于哈希函数的数据结构，它通过把关键值（Key value）映射到表中一个位置来访问记录，从而加快查找的速度。

当我们想使用哈希法来解决问题的时候，我们一般会选择如下2种数据结构：

map（映射）
set（集合）

1. map（映射）

2. set（集合）

3. map使用示例

3.1 golang使用示例

package main

import (
    "fmt"
    "sync"
)

func main() {
    // 创建并操作 map
    user := map[string]interface{}{
        "name":   "Bob",
        "age":    25,
        "skills": []string{"Go", "Python"},
    }

    // 类型断言获取值
    if age, ok := user["age"].(int); ok {
        user["age"] = age + 1
    }

    // 删除字段
    delete(user, "skills")

    // 并发安全操作
    var wg sync.WaitGroup
    var mu sync.Mutex
    counter := make(map[int]int)

    for i := 0; i < 10; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            mu.Lock()
            counter[i] = i * 2
            mu.Unlock()
        }(i)
    }

    wg.Wait()
    fmt.Println(user)    // 输出: map[age:26 name:Bob]
    fmt.Println(counter) // 输出类似: map[0:0 1:2 ... 9:18]
}

注意事项：

Map 的键必须是可比较类型（不能是 slice、map、function）
每次遍历顺序随机（Go 故意设计的特性）
大数据量时优先预分配空间：make(map[string]int, 1000)
值可以是任意类型，包括另一个 map
查询不存在的键不会报错，返回零值

3.2 Java使用示例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建并操作 Map
        Map<String, Object> user = new HashMap<>();
        user.put("name", "Bob");
        user.put("age", 25);
        user.put("skills", new String[]{"Java", "Python"});

        // 类型安全访问
        if (user.get("age") instanceof Integer age) {
            user.put("age", age + 1);
        }

        // 删除元素
        user.remove("skills");

        // 并发安全示例
        Map<Integer, Integer> counter = new ConcurrentHashMap<>();
        List<Thread> threads = new ArrayList<>();

        for (int i = 0; i < 10; i++) {
            final int num = i;
            threads.add(new Thread(() -> {
                counter.put(num, num * 2);
            }));
        }

        threads.forEach(Thread::start);
        threads.forEach(t -> {
            try { t.join(); } catch (InterruptedException e) {}
        });

        System.out.println(user);    // 输出: {name=Bob, age=26}
        System.out.println(counter); // 输出: {0=0, 1=2, ..., 9=18}
    }
}

注意事项：

键的类型：必须正确实现 equals() 和 hashCode() 方法
空值处理：HashMap 允许 null 键和 null 值，Hashtable 不允许
有序性选择：
- HashMap：无序
- LinkedHashMap：按插入顺序
- TreeMap：按键的自然顺序排序
线程安全：
- 非并发场景用 HashMap
- 高并发场景用 ConcurrentHashMap

3.3 Python使用示例

# 创建并操作字典
inventory = {
    "apples": 50,
    "bananas": 25,
    "oranges": 30
}

# 更新库存
def add_stock(item, quantity):
    inventory[item] = inventory.get(item, 0) + quantity

add_stock("apples", 20)
add_stock("pears", 40)

# 生成报告
print("Current Inventory:")
for item, qty in inventory.items():
    print(f"- {item.capitalize():<8}: {qty:03d} units")

# 删除低库存项
low_stock = [item for item, qty in inventory.items() if qty < 30]
for item in low_stock:
    del inventory[item]

print("\nFinal Inventory:", inventory)

输出结果：

Current Inventory:
- Apples  : 070 units
- Bananas : 025 units
- Oranges : 030 units
- Pears   : 040 units

Final Inventory: {'apples': 70, 'oranges': 30, 'pears': 40}

注意事项：

键的类型要求：
- 必须是可哈希类型（不可变类型：str/int/tuple 等）
- 值可以是任意类型
有序性：
- Python 3.7+ 中字典保持插入顺序
- 使用 collections.OrderedDict 获取更严格的有序保证
性能特性：
- 查找时间复杂度 O(1)
- 不要用 dict 替代类（应使用 dataclass 或自定义类）
内存优化：
- 使用 sys.getsizeof() 查看字典内存占用
- 对大量数据考虑使用 __slots__ 或第三方库（如 numpy）
常见陷阱：
- 避免在遍历时修改字典结构
- 不要用可变对象（如 list）作为键
- None 可以作为键值

3.4 对比

特性	Python	Go	Java
初始化语法	{k: v} 或 dict()	make(map[K]V)	new HashMap<>()
空值处理	get(key, default)	返回零值	getOrDefault
有序性	Python 3.7+ 保持插入顺序	无序	可选有序实现
并发安全	需手动加锁	sync.Map	ConcurrentHashMap
默认值处理	setdefault/defaultdict	需手动判断	computeIfAbsent