# 散列表

  • 散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash 表”
  • 散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表

三点散列函数设计的基本要求:

  1. 散列函数计算得到的散列值是一个非负整数
  2. 如果 key1 = key2,那 hash(key1) == hash(key2)
  3. 如果 key1 ≠ key2,那 hash(key1) ≠ hash(key2)

避免散列冲突:

  1. 开放寻址法:

开放寻址法

  • 线性探测,当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止

  • 我们通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素。如果相等,则说明就是我们要找的元素;否则就顺序往后依次查找。如果遍历到数组中的空闲位置,还没有找到,就说明要查找的元素并没有在散列表中

  • 二次探测:

  • 线性探测每次探测的步长是 1,二次探测探测的步长就变成了原来的“二次方”,也就是说,它探测的下标序列就是 hash(key)+0,hash(key)+12,hash(key)+22……

  • 双重散列:

  • 意思就是不仅要使用一个散列函数

  • 我们先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置

当数据量比较小、装载因子小的时候,适合采用开放寻址法

  1. 链表法:

链表法

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表,而且,比起开放寻址法,它更加灵活,支持更多的优化策略,比如用红黑树代替链表

# 如何设计散列函数?

  1. 散列函数的设计不能太复杂
  2. 散列函数生成的值要尽可能随机并且均匀分布

# 何为一个工业级的散列表?

  1. 支持快速地查询、插入、删除操作
  2. 内存占用合理,不能浪费过多的内存空间
  3. 性能稳定,极端情况下,散列表的性能也不会退化到无法接受的情况

# 如何实现这样一个散列表呢?

  1. 设计一个合适的散列函数
  2. 定义装载因子阈值,并且设计动态扩容策略
  3. 选择合适的散列冲突解决方法

# 哈希算法

  • 将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值

哈希算法要求:

  1. 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法)
  2. 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同
  3. 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小
  4. 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值

哈希算法应用:

应用一:安全加密,最常用于加密的哈希算法是 MD5(MD5 Message-Digest Algorithm,MD5 消息摘要算法)和 SHA(Secure Hash Algorithm,安全散列算法)

应用二:唯一标识,或者说信息摘要,哈希算法可以对大数据做信息摘要,通过一个较短的二进制编码来表示很大的数据。

应用三:数据校验,分块取哈希值,校验数据的完整性和正确性

应用四:散列函数,散列函数用的散列算法一般都比较简单,比较追求效率

应用五:负载均衡,我们可以通过哈希算法,对客户端 IP 地址或者会话 ID 计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号

应用六:数据分片,我们可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度

应用七:分布式存储,通过哈希算法对数据取哈希值,然后对机器个数取模,这个最终值就是应该存储的缓存机器编号。一致性哈希算法

加盐加密

# 布隆过滤器

  • 布隆过滤器本身就是基于位图的,是对位图的一种改进
  • 位图大小设置为 10 倍数据大小,减少冲突概率,bit位
  • 多次散列
  • 降低冲突
上次更新: 2020-8-18 22:14:00