程序员常说的「哈希表」是个什么鬼?

微鼎云

2017-05-11 19:07 浏览15668

       今天聊聊「哈希表」,「哈希表」主要作用在于高效查找。

  在编程实现中,常常面临着两个问题:存储和查找,存储和查找的效率往往决定了整个程序的效率。

  脑补下,你在家里忘记了指甲刀放在哪里,通常要在你家所有抽屉中顺序寻找,直到找到,最差情况下,有N个抽屉,你就要打开N个抽屉。这种存储方式叫数组,查找方法称为「遍历」。

  脑补下,你是一个整理控,所有物品必须分门别类放入整理箱,再将整理箱编号,比如1号放入针线,2号放入证件,3号放入细软。这种存储和查找方式称为「哈希」,如果这个时候要查找护照,你不许要再翻所有抽屉,直接可在2号整理箱中获取,通常只用一次查找即可,如何编号整理箱,称为哈希算法。

  同样是查找,差距怎么那么大涅~,假设我们有100亿条数据记录,那差距就变得明显,遍历需要查找最多100亿次,最少1次,哈希只需1次。

  让我们正式介绍哈希和哈希算法,哈希也称散列,哈希表是一种与数组、链表等不同的数据结构,与他们需要不断的遍历比较来查找的办法,哈希表设计了一个映射关系f(key)= address,根据key来计算存储地址address,这样可以1次查找,f既是存储数据过程中用来指引数据存储到什么位置的函数,也是将来查找这个位置的算法,叫做哈希算法。

  让我们举个例子,比如下面这几个人物,按数组存储:

程序员常说的「哈希表」是个什么鬼?

  这样我要找到大胸姐的电话号码,需要顺序查找对比整个数组,第一个余罪,不是,第二个不是,第三个不是,直到第四个找到大胸姐。

  如果以hash存储呢?首先让我们来看看如何设计哈希算法,哈希算法可以随意设计,教科书上一般会说以下几种方法:直接定址发,平方取中法,除数取余法,哈希算法的本质上是计算一个数字,如果用这几种方法讲解会稍显晦涩,我们假设我们的哈希算法是取姓名的首字母。所以f(余罪) = y, f(傅老大) = f,f(沈嘉文) = s,f(大胸姐) = d。

  构建的hash表如下:

程序员常说的「哈希表」是个什么鬼?

  我们看到他们分别以姓名首字母的位置插入到这一张表格中,这样我们构建了这样一个Key-Value表格,此表就是哈希表,也称为Hash Table。未来,当我们要查找余罪的时候,通过计算,余罪在y位置,可以通过1次查找,找到这条记录,也即手机号。

  这个时候有客官问了,那以首字母为哈希函数的话,应该有很多比如以y的姓名啊,这个时候就不是一次查找了吧,其实有很多条记录都映射到一个位置上,称为哈希冲突。

  哈希冲突是跟哈希函数的设计正相关的,你的随机性越大,那么产生哈希冲突的可能性越小,在小概率下,如果还有冲突怎么办,这个时候要做些有损的设计,比如如果有两个首字母为y的姓名,那么可以接到余罪的后面,当查找的时候,需要先查找到y,然后再顺序查找,如图所示:

程序员常说的「哈希表」是个什么鬼?

  还有一些解决哈希冲突的办法叫「哈希再哈希」,也就是针对第一次哈希的结果再进行一次hash来减小冲突的概率。

  这就是Hash表,首先Ta是一种数据结构,是一种效率极高的查找方式,哈希表的核心在于哈希函数的设计,哈希冲突了不要紧,我们要增加随机性以及对冲突进行适当的有损化的处理。