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

左手的ㄟ右手 2022-12-24 15:59 127阅读 0赞

# **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：值

hash (散列，杂凑，哈希) 是将任意长度的输入通过 hash 算法变换为固定长度的输出，输出值就是散列值。它是一种压缩映射，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，不可能从散列值来确定唯一的输入值，很难找到逆向规律。hash 函数是将任意长度的消息压缩到某一固定长度的消息摘要的函数。

hash 算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。

## References ##