一、哈希的概念1.哈希的定义哈希(hash)⼜称散列是⼀种组织数据的⽅式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系查找时通过这个哈希函数计算出Key存储的位置进⾏快速查找。2.直接定址法的概念与代码实现当关键字的范围⽐较集中时直接定址法就是⾮常简单⾼效的⽅法⽐如⼀组关键字都在[0,99]之间那么我们开⼀个100个数的数组每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在[a,z]的⼩写字⺟那么我们开⼀个26个数的数组每个关键字acsii码-a ascii码就是存储位置的下标。也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。这个⽅法我们在计数排序部分已经⽤过了其次在string章节的下⾯OJ也⽤过了。我们可以通过一道oj题来简单实现一下直接定址法该题目中我们先去遍历整个字符串将每个字符串出现的次数都储存在数组count中然后再从头到尾遍历s发现第一个等于1的字符直接返回下标。总之关于出现次数的题目直接哈希不要犹豫3.哈希冲突直接定址法的缺点也⾮常明显当关键字的范围⽐较分散时就很浪费内存甚⾄内存不够⽤。假设我们只有数据范围是[0, 9999]的N个值我们要映射到⼀个M个空间的数组中(⼀般情况下M N)那么就要借助哈希函数(hash function)hf关键字key被放到数组的h(key)位置这⾥要注意的是h(key)计算出的值必须在[0, M)之间。这⾥存在的⼀个问题就是两个不同的key可能会映射到同⼀个位置去这种问题我们叫做哈希冲突或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突但是实际场景中冲突是不可避免的所以我们尽可能设计出优秀的哈希函数减少冲突的次数同时也要去设计出解决冲突的⽅案。3.1负载因子假设哈希表中已经映射存储了N个值哈希表的总大小为M那么负载因子大小就为N/M而且负载因子越大哈希冲突的概率就越高空间利用率越高反之哈希冲突的概率就越低空间利用率越低。二、哈希函数1.除法散列法顾名思义假设映射存储的值为N哈希表的大小为M那么我们的哈希函数就是h(key)N%M得到的余数的值作为这个值的存储下标存储到哈希表中。当使⽤除法散列法时要尽量避免M为某些值如2的幂10的幂等。如果是2的幂那么key %2的X次方本质相当于保留key的后X位那么后x位相同的值计算出的哈希值都是⼀样的就冲突了。如:{63 , 31}看起来没有关联的值如果M是16也就是 那么计算出的哈希值都是15因为63的⼆进制后8位是 0011111131的⼆进制后8位是 00011111。如果是10的幂就更明显了保留的都是10进值的后x位如{112, 12312}如果M是100也就是 那么计算出的哈希值都是12。所以我们的M一般取不接近2的幂的质数。三、处理哈希冲突在实践当中我们一般还是选择除法散列法作为哈希函数但是无论选择哪一个哈希函数都没有办法完全避免哈希冲突为了处理哈希冲突我们有以下两个方法3.1开放定址法在开放定址法中所有的元素都放到哈希表⾥当⼀个关键字key⽤哈希函数计算出的位置冲突了则按照某种规则找到⼀个没有存储数据的位置进⾏存储开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种线性探测、⼆次探测、双重探测。3.1.1线性探测下面让我们来模拟实现一个简单的哈希表:此时是用线性探测完成的简易哈希表除此之外我们还可以用二次探测3.1.2二次探测此探测方法很好的避免了线性探测导致堆积的问题。但是以上代码只能适用于整型元素根本不适用于其他类型我们需要仿函数和特化来进行处理当key是string/Date等类型时key不能取模那么我们需要给HashTable增加⼀个仿函数这个仿函数⽀持把key转换成⼀个可以取模的整形如果key可以转换为整形并且不容易冲突那么这个仿函数就⽤默认参数即可如果这个Key不能转换为整形我们就需要⾃⼰实现⼀个仿函数传给这个参数实现这个仿函数的要求就是尽量key的每值都参与到计算中让不同的key转换出的整形值不同。string做哈希表的key⾮常常⻅所以我们可以考虑把string特化⼀下。以上是我们优化后的代码我们让每一个字符串的ASCII值加起来并每次都乘以131来保证我们的字符串落到不同的位置。3.1链定址法实现哈希桶开放定址法中所有的元素都放到哈希表⾥链地址法中所有的数据不再直接存储在哈希表中哈希表中存储⼀个指针没有数据映射这个位置时这个指针为空有多个数据映射到这个位置时我们把这些冲突的数据链接成⼀个链表挂在哈希表这个位置下⾯链地址法也叫做拉链法或者哈希桶。以上是我们的代码插入时我们使用头插具体细节可看代码好了以上就是本博客的全部内容我们下期再见