哈希表又称散列表，表现形式为将任意长度的输入，通过哈希算法变成固定长度的输出，哈希表是一种使用空间换取时间的数据结构。

通常是存储 <key，value>键值对，假设没有哈希表，将 <key，value>键值对存储在数组中，给定key查找的对应的value的时间复杂度为O(n)；

数组就是常见的哈希表，下标就是key，对应存储的值就是value。

通过引入哈希表，将任意长度的输入key转化为哈希表中的下标，将<key，value>键值对映射到哈希表中，进而加速给定给定key，查找value的速度，时间复杂度降低到O(1)。

下图 以两个键值对<key1,value1>、<key2,value2>为例，演示了哈希函数和哈希表之间的关系，以及在哈希中起到的作用。

哈希表基本操作
插入
将键值对<key，value>插入到哈希表中。

更新
若哈希表中已存在键值为key的键值对，更新哈希表键值对<key，value>。

删除
将键值对<key，value>从哈希表中删除。

查询
给定key，有两种查询方式。

查找key 是否存在于哈希表中。
查找key对应的value。
哈希函数
哈希函数又称散列函数，即将给定的任意长度的输入值转化为数组的索引(下标)。

如果有一个长度为n的数组，其可以存储n对键值对，对应的下标为[0,n-1]，通常数组的长度是大于等于键值对的数量。

因此我们需要一个哈希函数，将任意长度的输入映射到[0,n-1]，并且每个不同的key对应的数组下标一定是不一样的，即每个数组下标唯一对应一个key。

下图以三对<key,value>为例，演示了哈希函数hash将原始key，映射到数组下标的过程，具体哈希函数实现可以有很多方法，感兴趣的读者可以自行探究。