数据结构和算法-散列表和哈希算法

简述

散列表:利用数组支持按下标访问数据的特性扩展出的一种数据结构;

哈希算法:将任意长度的二进制值串映射为固定长度的二进制值串的一种算法。

散列表

散列思想:即哈希算法的思想原理;

散列函数:

  1. 计算得出的散列值是一个非负整数;
  2. 两个相等key得出的散列值必然相等;
  3. 两个不相等key得出的散列值必然不相等。

实际上,第三个条件几乎没有任何算法能够满足。

散列冲突:两个不相等key得出同一个散列值。

散列冲突的解决方案:

  • 开放寻址法:如果出现散列冲突,就重新探测新的位置,即从冲突的位置往后找一步步,找到空闲位置就插入,没找到则从头开始找(线性探测);或者是往后1的平方,2的平方步找(二次探测);又或者是对冲突的散列值再进行一次散列(二次散列);不过不管用什么方法,如果散列表中空闲位置不多的话,散列冲突的概率还是很高,为了尽可能保证散列表的操作效率,一般情况下都会尽可能保证三列表中有一定比例的空闲槽位,用装载因子表示空位的多少,计算公式是:load factor = 表中元素个数/散列表总长度,装载因子越大,空位越少,散列表性能越低。
  • 链表法:在冲突的槽位上有一个链表,冲突的即放到相同槽位的链表中,其删除和查找的时间复杂度都是O(n),只和链表长度成正比。
    Word文档的单词提示就可以借助散列表来实现:

常用的英文单词大概在20万个左右,假设单词平均长度为10个字母,平均一个单词占用10个字节的内存空间,那么20万个英文单词大概占用2MB空间,完全可以利用散列表的形式存储在内存中,当用户输入单词时,通过散列函数生成散列值然后去散列表中查找,能够找到即表示拼写可能正确;找不到即提示错误。

散列函数设计原则:

  1. 不能太复杂,否则影响执行效率;
  2. 散列值要随机,并且均匀分布。

散列表设计原则:

  1. 合理的默认初始大小,比如Java中HashMap为16;
  2. 合理的装载因子和扩容方案,比如HashMap的0.75和扩容为两倍;
  3. 散列冲突解决方案,采用线性探测的开放寻址法适合数据量小,装载因子小的时候,比如ThreadLocalMap;采用链表法适合存储大对象,大数据量的散列表,并且有更多的优化策略,比如JDK8的HashMap中链表长度大于8时,链表转换为红黑树,小于8时变成链表

哈希算法的应用

安全加密

MD5信息摘要算法、SHA安全散列算法、DES数据加密标准、AES高级加密标准;

唯一标识

对要上传大量图片时,会对每张图片的二进制码提取部分进行散列,或者对图片的全部二进制码进行散列,作为图片的唯一标识或者图片文件名称,并放入散列表,下次需要查找时,就可以在散列表中快速找到。

数据校验

经常下载Windows镜像文件的都会在下载完成以后进行校验,如果文件不完整,那么生成的散列值肯定和完整的散列值不一致。

负载均衡

负载均衡算法有很多,比如轮询、随机、加权轮询等。会话粘滞(session sticky)的负载均衡算法就是在同一客户端上的会话请求都路由放到同一个服务器上。
对客户端IP地址或者会话ID计算哈希值,对取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。

数据分片

统计关键词出现次数

假如有1T的日志文件,里面记录了用户的搜索关键词,先依次读出所有关键词,并且通过哈希函数计算哈希值,然后跟机器数n进行取模,最终得到的值就是应该被分配到的机器编号。

快速判断图片是否在图库中

1亿张图片,n台机器处理,让每台机器只维护某一部分图片对应的散列表,我们每次从图库中读取一个图片,计算唯一标识,然后与机器个数求余取模,得到的值就对应要分配的机器编号,然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。

分布式存储

海量的数据肯定需要存储,一个机器往往不够,所以用哈希算法提取哈希值,然后对机器个数取模,获得的值就是对应机器编号,扩容时,由于机器数增加,因此原来的哈希算法算出来的哈希值就不对了,这里一致性哈希算法就登场了。

一致性哈希算法:
假设有k台机器,数据的哈希值范围时[0,max],我们将整个范围划分为m个小区间,m远大于k,每个机器负责m/k个小区间,当有新机器加入的时候,我们将某几个小区间的数据,从原来的机器中搬移到新机器中。

坚持原创、技术分享。请作者喝杯茶吧!