当前位置：首页 > news >正文

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

news 2025/10/16 15:30:16

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

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

map（映射）
set（集合）

1. map（映射）

2. set（集合）

3. map使用示例

3.1 golang使用示例

package mainimport ("fmt""sync"
)func main() {// 创建并操作 mapuser := 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.WaitGroupvar mu sync.Mutexcounter := 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 * 2mu.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) {// 创建并操作 MapMap<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) + quantityadd_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 unitsFinal 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`