H5W3
当前位置:H5W3 > 其他技术问题 > 正文

图解哈希表及其原理

要点回顾

此部分方便知识点快速回顾,首次阅读请从引言部分开始。

  • 哈希表(Hash Table)其实也叫散列表,是一个数据结构。
  • 哈希表本质上就是一个数组,只不过数组存放的是单一的数据,而哈希表中存放的是键值对(key – value pair)。
  • key 通过哈希函数(hash function)得到数组的索引,进而存取索引位置的值。
  • 不同的 key 通过哈希函数可能得到相同的索引值,此时,产生了哈希碰撞。
  • 通过在数组中插入链表或者二叉树,可以解决哈希碰撞问题。

引言

哈希这个词想必大家经常听到,这也说明了它使用的频繁程度,HashMap 和 HashTable 都与哈希这个词有关系。那哈希是什么,要搞清楚它,我们得先来说下哈希表。

什么是哈希表?

哈希表(Hash Table) 是一种用于存储 键值对 的基本数据结构。在 C++ 中,哈希表使用 哈希函数 来计算数组的索引,进而存取数组中对应索引位置的值。

百科定义:

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

计算索引的过程被称为 哈希(hash)

哈希表实现原理

用一个简单的例子来说明哈希表的原理:

假设:有一本中文词典,里面包含了所有的汉字,但是这些汉字是按任意顺序随意排版的,那么想要在其中找到某一个汉字,你就需要从头至尾一个一个核查,如果运气差,这个汉字正好在词典的末尾,那你需要遍历整本词典才能找到你要查的汉字。

优化:因为汉字和拼音之间存在着一种确定的关系,为了提高查找速度,现在将所有汉字按照拼音(key)进行排序(拼音可以根据首字母,第二个字母依次进一步排序),并且每个拼音都有一个对应页码(index),从该页开始,存放拼音对应的汉字(value)。所以找到拼音,也就能在对应的页码找到对应的汉字。其中,拼音和页码之间,有着某种固定的映射关系,可以通过某种方式计算出来(hash function)。

由此可见,哈希表可以根据一个 key 值来直接访问数据,因此查找速度快。

但是,上面的例子,还存在一个问题,放在同一页码(具有相同拼音)的汉字可能不止一个(同音字),这时候通过拼音(key)获取到的汉字(value)应该是哪个呢?这就出现了碰撞(hash collision)

为了解决碰撞,实现哈希表可以有以下两种方式:

  • 数组 + 链表
  • 数组 + 二叉树

所以,哈希表本质上就是一个数组。只不过数组存放的是单一的数据,而哈希表中存放的是键值对。

链表或二叉树是用来解决碰撞的。

下面用图例说明哈希表以及解决哈希碰撞的链表实现:

图解哈希表及其原理

因为哈希表中 key 必须是唯一的,所以图示给拼音加了后缀 _1 和 _2。key han_1han_2 通过哈希函数 F(x) 计算出来的页码都是 244。这时就产生了哈希碰撞。为了解决碰撞问题,新建了一个链表,链表的每个结点都包含了一个键值对,当输入 key han_2 时,哈希表在 244 位置找到了键值对 [han_1 – 汉],但是通过比对发现找到的键值对的 key 是 han_1,不等于 han_2,所以继续遍历到链表的下一个结点,下一个结点存放了键值对 [han_2 – 汗],通过比较发现 key 确实是 han_2,因此返回了汉字(value)

本文地址:H5W3 » 图解哈希表及其原理

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址