Hash Map

Definition / 定义

hash map（哈希表/散列表）：一种常用的数据结构，用哈希函数把“键（key）”映射到数组中的位置，从而实现对“键-值（key-value）”对的快速查找、插入与删除（平均时间复杂度常为 *O(1)*）。在发生“哈希冲突”时，通常通过链表/桶（chaining）或开放定址（open addressing）等方法处理。

Pronunciation / 发音

/ˈhæʃ mæp/

Examples / 例句

I stored the user IDs in a hash map for fast lookup.
我把用户 ID 存在哈希表里，方便快速查找。

To reduce collisions, the program resizes the hash map when the load factor gets too high.
为减少哈希冲突，当负载因子过高时，程序会对哈希表进行扩容。

Etymology / 词源

hash 原意有“切碎、搅拌成杂乱状”的意思，在计算机语境中引申为“把数据通过算法打散成一个固定范围的值（哈希值）”。map 在这里指“映射/对应关系”。合起来 hash map 就是“通过哈希值实现映射关系的表”，中文常译作哈希表或散列表。

Related Words / 相关词

• Dictionary
• Hashtable
• Hashing
• Collision
• Bucket
• Key
• Value
• Lookup
• Load Factor

Literary Works / 文学作品

• Introduction to Algorithms（《算法导论》，Cormen / Leiserson / Rivest / Stein）：在哈希与散列表章节系统讨论哈希表及冲突处理。
• The Art of Computer Programming, Volume 3: Sorting and Searching（《计算机程序设计艺术》第 3 卷：排序与查找，Donald E. Knuth）：包含散列（hashing）与相关查找结构的经典论述。
• Programming Pearls（《编程珠玑》，Jon Bentley）：以工程视角讨论高效数据结构与查找问题，常涉及哈希思路与实践。