关于哈希

数据结构与算法

1.什么是哈希？为什么要用哈希？

简单来说其实哈希也是为了帮助我们进行查找的，不同于其他的查找。我们只需要依据某些关键字就能根据关键字很快得到我们想要的结果。使得一些非数值型的查找成为现实。

2.怎么哈希？哈希函数有哪些方式？如何设计哈希函数？

哈希其实就是索引的别名，通常情况下我们的索引只是映射一个地址。这种最简单的映射方法叫做直接定址法

但是我们数据量比较大的时候这样在计算哈希地址时候消耗比较高。

于是使用一种叫做哈希函数的buff来简化映射。根据提供的关键字来计算对应的地址，因为人比较懒惰，所以设计的哈希函数取值范围不能太大，这样计算量肯定就比较小，但是范围小的劣势就是很容易造成地址冲突，所谓的地址冲突就是传说中的茅坑被占了。可以想到类比这个一元二次函数的不同横坐标对应同一个纵坐标值。

常用的哈希函数

1. 直接定址法
2. 数字分析法
3. 除留余数法

3.什么是地址冲突？如何解决地址冲突？

1. 开放地址法

就是一旦发现我的坑被占了，然后我可以进行一个线性探测（就是线性的增长横坐标值然后对值对应的空位进行探索）。

1. 再散列法

就是在遇到散列冲突的时候使用另一种散列函数进行散列。直到我们不再冲突为止。

3.链地址法

这个链地址的实现就是比较，。，。可以想象HashMap的实现原理，但是好像又不是那样的。于是

我们在冲突的位置上放一个仓库（链表），然后就可以把所有冲突的数值放进链表了。不过这样带来的问题就是在我们查找的过程中可能会去在链表中寻找。这个是非常的消耗时间的。

4.公共溢出区法

就是单独开辟一个新的空间用来放我们的冲突数据。

4.散列表的性能分析