哈希表--day1--基本理论介绍

哈希表

Hash table是根据关键码的值来直接进行访问的数据结构。

其实直白来讲其实数组就是一张哈希表，不过其索引是十分简单的，我们通过0来访问num[0]，就是通过索引进行访问，得到对应的数据。

而对于个人理解，哈希表一般都是用来快速判断一个元素是否出现集合里。而涉及到Hash table 就需要了解Hash function。

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数实际上就是通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，然后根据哈希表对应的数组大小，将这个数值%定义的数组的大小，得到的数值就是学生名字映射为哈希表上的索引数字，从而访问数组当中的各个元素。

但是这样子避免不了会出现不同的名字对应相同的映射的索引数字，比如小张和小李都经过哈希函数运算得到1，对应访问的都是数组下的num[1]这一个元素，那该如何去确定到底是该访问小张对应的数据还是小李对应的数据，这就出现了一个矛盾，这就是对应的哈希矛盾或者哈希碰撞。

哈希碰撞

一般来说哈希碰撞有俩种方法进行解决：拉链法或者线性探测法

拉链法

拉链法实际上就是在对应数据域的地方，将其变成链表元素，然后将对应索引数值相同的数据都保存到这个虚拟头节点之后。然后再次进行别的编码函数判断，求得对应的是元素的索引值。

举个例子：校长和小李对应都是索引值为1，那么我们将num[1]定义为头节点，后面串上小张和小李对应的数据，用单链表对应串起来，然后再访问的时候，再根据小张还是小李，再次进行判断，即可。

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。

其实关于哈希碰撞还有非常多的细节，感兴趣的同学可以再好好研究一下，这里我就不再赘述了。

常见的三种哈希函数

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

数组
set （集合）
map(映射)

数组

这里数组就没啥可说的了，占个坑。。。。

set

在C++中，set提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合	底层实现	是否有序	数值是否可以重复	能否修改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

map

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

那么再来看一下map ，在map 是一个key-value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

这里在说一下，一些C++的经典书籍上 例如STL源码剖析，说到了hash_set hash_map，这个与unordered_set，unordered_map又有什么关系呢？

实际上功能都是一样一样的，但是unordered_set在C++11的时候被引入标准库了，而hash_set并没有，所以建议还是使用unordered_set比较好，这就好比一个是官方认证的，hash_set，hash_map 是C++11标准之前民间高手自发造的轮子。

总结

总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。