好啦，这就是拉链法，咋样，明白不
小白： 信息量不少啊，好在庆哥讲的比较清楚，明白啦
庆哥： 明白了就好，那我问你一个问题啊，针对开放寻址和拉链法，你有没有觉得会产生什么问题呢？
小白： 嗯嗯，我还真有问题，首先是这个拉链法啊，如果冲突的很多，那这个增加的链表岂不是很长，这样也不咋好吧
庆哥： 的确，如果冲突过多的话，这块的链表会变得比较长，怎么处理呢？这里举个例子吧，拿java集合类中的HashMap来说吧，如果这里的链表长度大于等于8的话，链表就会转换成树结构，当然如果长度小于等于6的话，就会还原链表 。以此来解决链表过长导致的性能问题 。
小白： 为啥是小于等于6啊，咋不是7嘞
庆哥： 这样设计是因为中间有个7作为一个差值，来避免频繁的进行树和链表的转换，因为转换频繁也是影响性能的啊 。
小白： 嗯嗯，这个知道了，关于开放寻址也有个疑问，那就是如果一直找不到空的位置咋整啊？
庆哥： 这个不会的，为啥嘞？你这样想，是因为你考虑了一个前提，那就是位置已经被占光了，没有空位置了，但是实际情况是位置不会被占光的，因为有一定量的位置被占了的时候就会发生扩容 。
小白： 阿西吧，还有扩容，那这个扩容是咋回事呢？
哈希表的扩容庆哥： 其实这里不仅仅是因为你说的那种情况才会扩容，还有一个很重要的原因就是当哈希表被占的位置比较多的时候，出现哈希冲突的概率也就变高了，所以很有必要进行扩容 。
那么这个扩容是怎么扩的呢？这里一般会有一个增长因子的概念，也叫作负载因子，简单点说就是已经被占的位置与总位置的一个百分比，比如一共十个位置，现在已经占了七个位置，就触发了扩容机制，因为它的增长因子是0.7，也就是达到了总位置的百分之七十就需要扩容 。
还拿HashMap来说，当它当前的容量占总容量的百分之七十五的时候就需要扩容了 。
而且这个扩容也不是简单的把数组扩大，而是新创建一个数组是原来的2倍，然后把原数组的所有Entry都重新Hash一遍放到新的数组 。
小白： 这个重新Hash一遍是啥意思啊？
庆哥： 因为数组扩大了，所以一般哈希函数也会有变化，这里的Hash也就是把之前的数据通过新的哈希函数计算出新的位置来存放 。
小白： 嗯嗯，原来是这么回事啊，懂了，对了，那哈希表的数据读取怎么操作的啊？
哈希表如何读取数据庆哥： 要知道这个读取操作，我们还来看这个图：
文章插图
比如我们现在要通过学号102011来查找学生的姓名，怎么操作呢？我们首先通过学号利用哈希函数得出位置1，然后我们就去位置1拿数据啊，拿到这个Entry之后我们得看看这个Entry的key是不是我们的学号102011，一看是101011，什么鬼，一边去，这不是我们要的key啊，然后根据这个Entry的next知道下一给位置，在比较key，好成功找到李四 。
小白： 哦哦，原来是这么回事啊，那对于开放寻址那种是不是也是这个思路，先确定到这个位置，然后再看这个位置上的key是不是我们要的，如过不是那就看看下一个位置的 。
庆哥： 可以的，完全正确，好了现在我们对哈希表的讲解已经差不多了，那么你觉得对于哈希表而言，什么是核心呢？
哈希函数是核心小白： 我觉得应该是哈希函数吧，经过上面的讲解，我觉得，如果一个哈希函数设计的足够好的话，就会减少哈希冲突的概率，如果设计的不好，那就会经常撞衫，那就很影响性能了，比如刚开始我们举的那个例子，拿姓名的首字母来确定位置，这个哈希函数的设计就不咋滴，比如王二，王三，王四什么的，这都会冲突啊
庆哥： 的确，在哈希表中，哈希函数的设计很重要，一个好的哈希函数可以极大的提升性能，而且如果你的哈希函数设计的比较简单粗陋，那很容易被那些不怀好意的人捣乱，比如知道了你哈希函数的规则，故意制造容易冲突的key值，那就有意思了，你的哈希表就会一直撞啊，一直撞啊
小白： 哈哈，那设计哈希函数有什么方法吗？
庆哥： 必须有啊，比如有直接定址法，数字分析法，折叠法，随机数法和除留余数法等等，要不要继续讲啊
小白： 我去，还是不要了吧，消化不了啊，这次先到这吧，谢谢庆哥
推荐阅读
- 微信开发工程师带你一文了解推荐领域最新工作
- 搞定这6个坏习惯，让焦虑这家伙远离你
- 一文看懂加密算法为何物
- 一文秒懂 QPS、TPS、PV、UV、GMV、IP、RPS
- 一文讲清辞退和裁员的区别？认清公司变相裁员伎俩，维护自己权益
- 什么是“分布式事务”？这回彻底懂了
- 一文深度揭开Redis的磁盘持久化机制
- 一文学会如何查询鉴别真假百度蜘蛛，遏止恶意IP抓取
- dfs,bfs 一文搞懂深度优先搜索、广度优先搜索
- 新手化妆教程首公开：日常淡妆需要的11种化妆工具，一次性搞定