算法基础9：散列表
算法是基础，小蓝同学准备些总结一系列算法分享给大家，这是第9篇《散列表》，非常赞！希望对大家有帮助，大家会喜欢！
前面系列文章：
散列表是我们比较简单的一种查找算法，是用这种建议方法的扩展并能够处理更加复杂的类型的键。我们可以通过算数操作将键转化为数组的索引来访问数组中的键值对。
使用散列表的查找算法分为两步 第一步用散列函数将被查找的键转化为数组的一个索引。理想情况下，不同的键都可以变为不同的索引，但有时有特殊情况，这就涉及到我们的第二步处理碰撞冲突的过程。
一、散列函数键值转换
散列算法有很多种实现，在java中没中类型都需要相应的散列函数，例如;在正整数 最常用的是除留余数法（k%M）。 于是Java令所有数据类型都继承了一个能够返回一个32比特整数的hashCode()方法。 如果a.equals（b）返回ture 那么a.hashCode的返回值必然和b.hashCode()相等 反之亦然。
总的来说 要为数据类型实现一个优秀的散列方法需要满足下面三个条件：
1）一致性 --等价键必然产生相等的散列值
2）高效性 --计算简便
3）均匀性 -- 均匀的散列所有的键
二、处理碰撞冲突
基于拉链法来处理碰撞问题，也就是处理两个键或多个键的散列值相同的情况，拉链法指的是将大小为Md数组中的每一个元素指向一条链表，链表中的每一个节点都存储了散列值为该元素的索引的键值对，例如我先按hash值找到对应的链，在从链中找到对应的值。大家一致用的java的HashMap 就是按这种方式来处理碰撞冲突问题的。
基于线性探测法来处理碰撞问题，开放寻址法中最简单的是线性探测法：当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1，这样的线性探测会出现三种结果：
命中，该位置的键和被查找的键相同
未命中，键为空
继续查找，该位置和键被查找的键不同。
三、应用
散列表的应用是使用最广泛的算法之一
信息安全领域：
Hash算法 可用作加密算法。
如文件校验：通过对文件摘要，可以得到文件的“数字指纹”，你下载的任何副本的“数字指纹”只要和官方给出的“数字指纹”一致，那么就可以知道这是未经篡改的。例如著名的MD5 ；
数据结构领域：
Hash算法 通常还可用作快速查找。
这是今天我想说的部分。根据Hash函数 我们可以实现一种叫做哈希表（Hash Table）的数据结构。这种结构可以实现对数据进行快速的存取。HashMap的实现及HashSet的实现
猜你喜欢
加入技术讨论群
《大数据和云计算技术》社区群人数已经3000+，欢迎大家加下面助手微信，拉大家进群，自由交流。
喜欢钉钉扫码下面的群：
喜欢QQ群的，可以扫描下面二维码：
欢迎大家通过二维码打赏支持技术社区（英雄请留名，社区感谢您，打赏次数超过108+）：