一文彻底搞定哈希表 _哈希表

哈希表是个啥？
小白：庆哥，什么是哈希表？这个哈希好熟悉，记得好像有HashMap和HashTable之类的吧，这是一样的嘛？
庆哥：这个哈希确实经常见，足以说明它是个使用非常频繁的玩意儿，而且像你说的HashMap和HashTable之类的与哈希这个词肯定是有关系的，那哈希是个啥玩意啊，这个咱们还是得先来搞明白啥是个哈希表。
我们看看百科解释吧：

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

怎么样？看到这个，你知道哈希表是什么了嘛？
小白：我之前是对哈希表一窍不通啊，不过看了这个百科的解释，我知道如下这些关于哈希表的简单知识点：
1、哈希表其实也叫散列表，两个是一个玩意，英文是Hash Table
2、哈希表是一个数据结构
这两个概念是比较清晰的，至于其他的说什么映射函数叫做散列函数，存放记录的数组叫做散列表这个就有点模糊了，尤其说存放记录的数组称为散列表，那意思是哈希表是个数组？
庆哥：首先你说的很清晰的两点说的是很准确的，哈希表也叫做散列表，这只不过是叫法而已，英文单词是Hash table，看到这个英文单词基本上就能猜到，哈希表其实就是直接根绝英文单词音译过来的，至此你应该知道了啥是哈希了吧，对于另外一点，那就很重要了，那就是哈希表其实是一种数据结构。
要知道数据结构有很多中，每一种都有各自的特点，那么哈希表既然也是一种数据结构，那它有什么特点呢？按照百科的解释，我们大致能知道：可以根据一个key值来直接访问数据，因此查找速度快
对了，你知道最基本的几个数据结构中，哪个的查询效率是最高的嘛？
小白：据我所知，应该是数组吧，我们可以直接使用数组下标来访问数据，因此查询效率是很高滴
庆哥：对，非常对，哈希表其实本质上就是一个数组。
小白：那为啥还叫哈希表呢？，哈希表肯定有啥特别的吧，为啥本质上是一个数组呢？
哈希表本质是数组？庆哥：必须滴啊，哈希表本质上是个数组，只能说它的底层实现是用到了数组，简单点说，在数组的这个基础上再捯饬捯饬，加工加工，变得更加有特色了，然后人家就自立门户，叫哈希表
小白：这是咋个回事啊
庆哥：为什么说哈希表的本质是个数组呢？那就得看看，哈希表是怎么来实现的了，一般来说啊，实现哈希表我们可以采用两种方法：
1、数组+链表
2、数组+二叉树
简单点就有这么两种方式，其实说白了，无论哪个都是必须有数组啊，都是再数组的基础上取搞其他的，而且比如第一种数组+链表的形式，本质上是出现哈希冲突的一种解决办法，使用链表存放，所以综合起来叫做数组+链表的方式来实现一个哈希表，另外数组中一般就是存放的单一的数据，而哈希表中存放的是一个键值对，这是个区别吧！
小白：停！！！有点迷糊，什么哈希冲突，什么玩意儿啊
庆哥：，好吧好吧，我说的有点着急了，你就记住，哈希表在本质上就是个数组就ok了。
小白：可是我还是像知道为啥啊？
庆哥：别着急啊，咱慢慢来讲，另外在百科上有这么一个例子，可以帮助你更好的理解哈希表是个啥，它是这样说的：

文章插图

怎么样？看的懂嘛？
小白：反正是有点模糊，这其中提到的函数关系啊，关键字啊，散列函数还有什么函数法则的有点迷迷糊糊的
哈希表的几个概念啥是散列函数庆哥：确实，这都是哈希表中很重要的几个概念，那咱就先搞懂这几个概念吧，我用大白话给你说说这个例子。
比如说，我现在给你个电话本，上面记录的有姓名和对应的手机号，我想让你帮我找王二的手机号是多少，那么你会怎么做呢？
小白：这样啊，那我就挨个找王二呗？
庆哥：确实可以，那么你有没有想过，如果这个王二是在最后几页，那你去岂不是前面几页都白找了，有没有更快的方式呢？
小白：也是哦，那这样的话，是不是可以按照人名给分个类，比如按照首字母来排序，就abcd那样的顺序，这样根据王二我就知道去找w这些，这样不久快很多了