第5章 第12节 哈希

2021/01/04 09:54
阅读数 24

●   请你说一下哈希表是做什么的?另外哈希表的实现原理也说一下

参考回答:

Hash表即散列表,其最突出的优点是查找和插入删除具有常数时间的复杂度

其实现原理是:把Key通过一个固定的算法函数即所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。

而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。哈希表又叫做散列表,分为“开散列” 和“闭散列”。

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方。

但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。

●   现在有100W个账户密码,要存起来,要求查找时速度尽可能快,你选择什么数据结构?为什么?

参考回答:

选择hash_map,因为其查找速度与数据量基本无关,是常数级别,但是对空间的要求很高,所以是已空间换时间 

图片


展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部