建设门户网站费用,推广业务平台,游戏推广赚佣金,沧州推广建站文章目录 哈希表哈希函数哈希碰撞拉链法线性探测法 常见的三种哈希函数数组setmap 总结 哈希表
Hash table是根据关键码的值来直接进行访问的数据结构。
其实直白来讲其实数组就是一张哈希表#xff0c;不过其索引是十分简单的#xff0c;我们通过0来访问num[0]#xff0c… 文章目录 哈希表哈希函数哈希碰撞拉链法线性探测法 常见的三种哈希函数数组setmap 总结 哈希表
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_setunordered_map又有什么关系呢
实际上功能都是一样一样的但是unordered_set在C11的时候被引入标准库了而hash_set并没有所以建议还是使用unordered_set比较好这就好比一个是官方认证的hash_sethash_map 是C11标准之前民间高手自发造的轮子。
总结
总结一下当我们遇到了要快速判断一个元素是否出现集合里的时候就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间因为我们要使用额外的数组set或者是map来存放数据才能实现快速的查找。
