一文彻底搞定哈希表( 二 ) _哈希表

庆哥：的确，我们可以按照人名的首字母去弄一个表格，比如像这样：

文章插图

你看，假如现在我让你去帮我找王二的手机号，你一下子就能找到，不用再挨个的去查找了，这效率就高的多了，那么现在重点来了，人家本来叫王二，你为啥用一个w来标记人家呢？让你找王二为啥你不直接找王二而是去找w呢？
小白：这个？，用w可以更快速的去定位到王二啊
庆哥：说的很对，我们取姓名的首字母作为一个标志，就可以很快的找到以这个字母开头的人名了，那么王二也就能更快的被我们找到，我们也不用再费力气去找什么张二和李二的，因为人家的名字首字母都不是w 。
小白：那必须啊，这个方法好吧
庆哥：对对对，你说到点子上了，那就是方法二字，这里我们就是采用一种方法，什么方法呢？那就是取姓名的首字母做一个排序，那么这是不是就是通过一些特定的方法去得到一个特定的值，比如这里取人名的首字母，那么如果是放到数学中，是不是就是类似一个函数似的，给你一个值，经过某些加工得到另外一个值，就像这里的给你个人名，经过些许加工我们拿到首字母，那么这个函数或者是这个方法在哈希表中就叫做散列函数，其中规定的一些操作就叫做函数法则，这下你知道什么是散列函数了吧
小白：嗯呢，这下真的是很清楚了，说白了，不就是给我一个值，经过捯饬一下，变成另外一个值吗？花个图的话就是这个样子：

文章插图

哈哈，是不是这样？
庆哥：简单来说就是这样滴，咋样，这下知道什么是散列函数了吧？
关键值key是啥？小白：这下知道了，很清楚，那这个关键字key是个啥玩意？
庆哥：这个也好理解啊，就像你画的这个图，1是怎么得出来得，是不是根据未加工之前得101得出来得，这个加工过程其实就是个散列函数，而丢给它的这个101就是这个关键值啊，为啥叫它关键值嘞，那是因为我们要对它做加工才能得出我们想要的1啊，你说它关不关键
小白：哦哦，原来是这样啊，这下就明白啦！对了，我现在有这样的一个理解，你看看对不对啊，那就是哈希表就是通过将关键值也就是key通过一个散列函数加工处理之后得到一个值，这个值就是数据存放的位置，我们就可以根据这个值快速的找到我们想要的数据，是不是这样啊？
庆哥：说的很正确，那你现在对之前那个百科的例子懂了嘛？
小白：嗯呢，这下懂了
庆哥：嗯呢，那就好，其实吧，上面的那中情况并不好，为啥嘞？你想啊，王二在那个位置，如果再来个王三呢？人家的首字母也是w啊，这咋办，位置被王二占了，那王三咋办？这就是哈希冲突啊，撞衫啦
小白：阿西吧，又是哈希冲突，它到底似乎个啥玩意啊
庆哥：不着急，咱们继续来探究哈希表。
再探哈希表庆哥：我们在之前已经知道了哈希表的本质其实是个数组，数组有啥特点啊？
小白：数组嘛，那就是下表从0开始啊，连续的，直接通过下标访问，比如下面这样：

文章插图

有一个数组a，我们可以直接通过a[1]的形式来访问到数值7，所以查询效率很高。
庆哥：完全正确，那么哈希表本质上是个数组，那它跟这个类似吗？我们来再深入探究一下，首先看个图：

文章插图

这张图可是信息量很大啊，你看出来个啥了嘛？
小白：这个？我看到了哈希函数，这是啥？它跟散列函数有啥区别啊？还有Entry是个什么鬼，还有键值对，蒙圈啊
哈希函数庆哥：别蒙圈啊，我来仔细跟你说说，其实这个哈希函数就是我们之前说的散列函数，为啥嘞？这就跟哈希表也叫做散列表一样啊，你叫作散列表的时候有个散列函数，那你叫哈希表的时候，也得有个哈希函数啊，这样才公平嘛，咋样，知道了吧？
小白：我去，原来是这么回事啊，那键值对跟Entry嘞？
键值对和Entry庆哥：这个可是值得好好说道说道，我们知道哈希表本质上是个数组，难道就跟数组的基本使用那样，存个数值，然后通过下表读取之类的嘛？当然不是啦，对于哈希表，它经常存放的是一些键值对的数据，啥是键值对啊，就是我们经常说的key-value啊，简单点说就是一个值对应另外一个值，比如a对应b，那么a就是key，b是value，哈希表存放的就是这样的键值对，在哈希表中是通过哈希函数将一个值映射到另外一个值的，所以在哈希表中，a映射到b，a就叫做键值，而b呢？就叫做a的哈希值，也就是hash值。