哈希表、无序集合、映射的原理与实现

哈希表(Hash table)又称散列表，是一种可以通过key直接进行访问的数据结构。

哈希表由两部分组成

• 一个数据结构，通常是链表、数组
• Hash函数，输入key返回数据结构的索引

例子：

hash_table["lies"]=233的例子，以各ASCII码相加mod20为Hash函数

 

如果其他的key经过hash函数计算也是放在9的位置，那么就会发生hash碰撞。

hash碰撞指的是两个不同的key被计算出同样的Hash结果，把复杂信息映射到小的值域，发生碰撞是不可避免的，好的Hash函数可以减少碰撞发生的机率，让数据尽可能的均衡分布

开散列是最常见的碰撞解决方案

• Hash函数依然用于计算数组下标
• 数组的每个位置存储一个链表的表头指针（我们称它为表头数组）
• 每个链表保存具有同样Hash值得数据

 时间复杂度

期望：插入、查询、删除 O(1) ---------数据分布比较均匀时

最坏：插入、查询、删除O(N)-----------数据全部都被映射为相同得Hash值时

集合与映射

集合(set)存储不重复得元素

• 有序集合，便利时按元素大小排序，一般用平衡二叉搜索树实现，O(logN)
• 无序集合，一般用hash实现，O(1)

映射(map) 存储关键码(key)不重复的键值对(key-value pair)

• 有序映射，遍历时按照key大小排序，一般用平衡二叉搜索树实现，O(logN)
• 无序映射，一般用哈希表实现，O(1)

对于语言内置的类型（int,string）,已经有默认的优秀的hash函数，可以直接放进set/map里使用