hash table - hash map - 哈希表 - 散列表

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.
在计算中，hash table (hash map) 是一种实现关联数组抽象数据类型的数据结构，该结构可以将键映射到值。哈希表使用哈希函数来计算存储桶或插槽数组的索引 (哈希码)，从中可以找到所需的值。在查找期间，将对键进行哈希处理，并且所得到的哈希值会指示相应值的存储位置。

顺序存储结构需要逐个地按顺序访问元素，当总数量很大且我们所要访问的元素相对靠后时，性能很低。散列表是一种空间换时间的存储结构，是提升效率的一种比较常用的方式，通常需要在时间和空间之间权衡。

1. hash table (hash map) 的思想

在查字典时，查找一个单词，肯定不会从头翻到尾，而是首先通过这个单词的首字母，找到对应的那一页；再找第 2 个字母、第 3 个字母，…… 这样可以快速跳到那个单词所在的页。

hash：散列，杂凑，哈希
hash table，hash map：哈希表，散列表
hash function：哈希函数，散列函数
key：键
value：值

References