哈希（Hash）

type

status

summary

date

slug

1.什么事哈希表（Hash）？

1.散列表（Hash table也叫哈希表），是根据键（key）而直接访问内存存储位置的一个数据结构，也就是说他能通过一个函数来计算一个值的键值，将所查询的数据映射到表中的一个位置来查询，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

2.所以我们知道了哈希表之所以快就是因为它能直接通过key来访问数据，但其实如果说访问数据那肯定是数组的访问效率最高，它能直接通过下标来直接访问数据，那其实哈希表其实本质上就是一个数组

3.散列函数

其实我们在日常生活中经常用到散列函数，就比如我们在填表的时候3班有谁，2班有谁，1班又有谁，其实就是将数据分成了几个“类别”，然后通过类别访问类别里面的数据再进行查找

4.key

那这个hash表里面存的key其实就是数据被散列函数进行过处理获得的一个值，在哈希表中能通过key来快速的访问这个数据

5.那么哈希表是如何存放数据的呢

哈希表其实就是一个数组，我们把key想象为一个下标，那么里面存储的值就是value

2.哈希冲突

既然key是通过一个哈希函数计算出来的，那有没有可能出现重复呢？答案肯定的，这个重复就被称为哈希冲突或者哈希碰撞，那既然碰撞了，那肯定需要去解决呀，不然发生碰撞的值不就没有位置了吗，那应该怎么去解决呢？

处理哈希冲突有两个方法：一个是开放寻址法，另外一个就是拉链法

1.开放寻址法

开放寻址法的解决办法其实非常粗暴，既然你把我位置占了，那我把别人位置也占了不就得了？如果key等于1的位置被占了那我们直接找key等于2的位置，如果2的位置也被占了那就找3，以此类推直到找到空的位置

☝

其实这里再引入一个元素叫负载因子，它是一个用于扩容的因子

= 数据个数 / hash.size 如果说我们设置当他等于0.7时我们就该扩容了，那么当我们使用开放寻址法时就不需要考虑出现没有位置占的情况了

其实java中的ThreadLocal就是使用了这个开放寻址法

1.2扩容

当负载因子到达设定的值之后，我们就需要进行扩容，这里的扩容也不是像我们学习顺序表的时候的realloc而是直接创建一个新的空间，然后重新hash一边将数据放入新的hash表中，因为当数组扩容之后数据通过hash函数计算出来的哈希值也会发生变化需要重新装入新表中

2.拉链法

拉链法其实是最常用的一种，hashmap里面就是运用的这用方式，当发生hash冲突时，将key值相同的数据放在同一个链表中其实就是这一张图

当哈希冲突过多的时候，链表过长，性能降低的时候，那该怎么处理呢

这里举个例子吧，拿java集合类中的HashMap来说吧，如果这里的链表长度大于等于8的话，链表就会转换成树结构，当然如果长度小于等于6的话，就会还原链表。以此来解决链表过长导致的性能问题。

2那这个拉链法是如何在查找中找到数据的呢？

其实就是你的key找到了这个entry，发现上面不是你想要的数据那么cur就变成cur→next然后在对比key这里其实就是链表的查找方法，直到找到你想要的值

说到这里其实我们对哈希其实了解的也差不多了，但是其实哈希最重要的地方就是哈希函数，也是哈希表设计最重要的一个设计部分，如果被一些不怀好意的·人知道了，故意制造哈希冲突使的哈希表混乱那就不好了，接下来我们来介绍几个常用的哈希函数设计方式

1.直接定址法：取关键字或关键字的某个线性函数值为哈希地址。

2.数字分析法：假设关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

3.平方取中法：取关键字平方后的中间几位为哈希地址。

4.斐波那契（Fibonacci）散列法

5.折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。

6.除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H(key)=key MOD p,(p<=m)，这是一种最简单，也是最常用的构造哈希函数的方法。它不仅可以对关键字直接取模（MOD），也可在折叠、平方取中等运算之后取模。

7.随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key)，其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较切当。

3.map,hash_map,unorderd_map的引入

1.map在本网站的其他文章中有对map有详细介绍的文章，但是这里还是简单说一下，map是一个非常有用和有意义的C++标准库里的结构，它提供key-value的查找方式，并且他的内部机制实现是基于红黑树的，

而hash_map就是map基于哈希表实现的其他文章有讲到，map的查找时间复杂度是O(log_2N)而哈希表的查找复杂度是O(1)

3.2 hash_map “直接定址”与“解决冲突”是哈希表的两大特点。

hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：

hash_map 其插入过程是：

得到key 通过hash函数得到hash值得到桶号(一般都为hash值对桶数求模) 存放key和value在桶内。其取值过程是:

得到key 通过hash函数得到hash值得到桶号(一般都为hash值对桶数求模) 比较桶的内部元素是否与key相等，若都不相等，则没有找到。取出相等的记录的value。

hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候).

由此可见，要实现哈希表, 和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。

但是我们在初始化hash_map时，好像没有去制定hash函数和比较函数，原因是我们使用了缺省函数，自动帮我们设置了hash函数和比较函数

3.3unordered_map

其实在最初的时候C++标准库中没有类似hash_map的实现，但是不同的实现者提供了不同版本的hashmap，但是功能上有一些细微的偏差

从C++11开始，hashmap被添加到了标准库中，但是防止与已开发出来的hashmap名字发生冲突，取名叫unordermap，也有暗示无序map的意味

4.unordered_map的用法

unordered_map是C++标准库中的一个容器，它是一个关联容器，内部采用的是哈希表结构拥有快速检索的功能

特性：

关联性：通过key去检索value，而不是通过绝对地址（和顺序容器不同）无序性：使用hash表存储，内部无序 Map : 每个值对应一个键值键唯一性：不存在两个元素的键一样动态内存管理：使用内存管理模型来动态管理所需要的内存空间

Hashtable和bucket 由于unordered_map内部采用的hashtable的数据结构存储，所以，每个特定的key会通过一些特定的哈希运算映射到一个特定的位置，我们知道，hashtable是可能存在冲突的（多个key通过计算映射到同一个位置），在同一个位置的元素会按顺序链在后面。所以把这个位置称为一个bucket是十分形象的（像桶子一样，可以装多个元素）。

1.什么事哈希表（Hash）？

2.哈希冲突

3.map,hash_map,unorderd_map的引入

4.unordered_map的用法

PytC

交流频道

加入我们的社群讨论分享