iOS-哈希冲突

iOS-哈希冲突

IOS小彩虹2021-07-08 23:09:38130A+A-

哈希表介绍

1. 哈希的相关概念

Hash,音译为哈希,翻译为散列,我们说哈希或者散列其实就是一个东西

Hash就是把任意长度的输入,通过哈希算法(散列算法),变换成固定长度的输出,该输出就是哈希值(散列值)

  • 这种转换是一种压缩映射 (散列值的空间通常小于输入的空间)

根据同一散列函数计算出的散列值如果不同,那么输入值肯定不同

根据同一散列函数计算出的散列值如果相同,散列值不一定相同,即不同的输入可能会输出相同的散列

当两个不同的输入,根据同一散列函数计算出的散列值相同,称该现象为冲突 (碰撞) (有冲突解决方法,下面会说)

2. 数据结构

  • 数组特点:寻址容易,插入和删除困难
  • 链表特点:寻址困难,插入和删除容易

综合两者的特性,实现一种寻址容易、插入和删除也容易的数据结构——这就是哈希表((HashMap),也叫散列表),我们可以理解为链表的数组

image.png 从上图我们可以看到数组的每个成员是一个链表,我们根据每个元素自身的特征将元素分配到不同的链表中去,反过来我们也正是通过这些特征找到正确的链表,再从链表中找到相应的元素

其中,根据元素特征计算元素数组下标的方法就是哈希算法

3. 哈希函数

当使用哈希表进行查询的时候,就是使用哈希函数将key转换为对应的数组下标,下面列出常用的三种哈希函数

  • 除法散列法

index = value % 16 求模,叫除法是因为求模其实是通过除法运算的

  • 平方散列法
  • 斐波那契散列法

(这里我没有去深入看了,有点点头大)

4. 解决碰撞

冲突解决技术可以分为两类:

  • 开散列方法(也称为拉链法):把发生冲突的关键码存储在散列表主表之外
    • 分离链接
  • 闭散列方法(也称为开地址法):发生冲突的关键码存储在表的另一个槽内
    • 线性探测
    • 双重哈希
    • 随机散列

线性探测

线性探测基本上是在发生冲突时对空槽进行线性搜索

  1. index = H(K)
  2. 如果位置index已经有密钥,则令index = (index + 1) mod M (M为表的大小)
举个例子:哈希表大小M = 7, 哈希函数:H(K) = K mod M
插入这些值:701, 145, 217, 19, 13, 749

H(K) = 701 % 7 = 1
H(K) = 145 % 7 = 5
H(K) = 217 % 7 = 0
H(K) = 19 % 7 = 2
H(K) = 13 % 7 = 1(冲突) --> 2(已经有值) --> 3(插入位置3)
H(K) = 749 % 7 = 2(冲突) --> 3(已经有值) --> 4(插入位置4)

可见,随着数据插入,探针遍历次数将会逐渐变低,检索过程就称为穷举

双重哈希

使偏移到下一个探测到的位置取决于键值,因此对于不同的键位置可以不同

需要引入第二个哈希函数 H 2(K),用作探测序列中的偏移量(可以说线性探测就是H 2(K)= 1 的双重哈希)

对于大小为M的哈希表,H 2(K)的值在 1~M-1的范围,如果M为质数,则常见的一个选择是H2(K)= 1 +((K / M)mod(M-1))

  1. index = H(K),offset = H 2(K)
  2. 如果位置index已经有密钥,则令 index = (index + offset) mod M (M为表的大小)

随机散列

与双重哈希应用,随机哈希通过使探测序列取决于密钥来避免聚类

使用随机散列时,探测序列是由密钥播种的伪随机数生成器的输出生成的

  1. 创建以K为种子的RNG,设置 index = RNG.next() mod M
  2. 如果位置index已经有密钥,则令 index = RNG.next() mod M

分离链接(拉链法)

关键是把同一个散列槽(数组的每一个槽)中的所有元素放到一个链表中

通过散列函数计算出索引

  • 如果索引的槽没有元素,直接插入
  • 如果槽有元素
    • 若key值不同,就将数据插入链表的链头
    • 若key值相同,就将value进行更新

假设哈希函数是 H(K) = K mod 8

  1. 没有发生哈希冲突

直接插入 image.png

  1. 发生哈希冲突但key不同

插入到链表链头

image.png

  1. 发生哈希冲突且key相同

更新value

image.png

哈希表在iOS中的应用

1. weak表

weak采用的是一个全局HashMap,当销毁一个对象时,根据对象从哈希表中找到存放所有指向该对象的weak指针的数组,然后将数组中的所有元素都置为nil

基本步骤

  • 对象dealloc的时候,从全局的hashmap中,根据一个唯一代表对象的值作为key,找到存储所有指向该对象的weak指针的数组
  • 将数组的所有元素(weak指针)置为nil

2. Runloop

线程和Runloop的关系是一一对应的,其关系是保存在一个全局的 Dictionary 里

3. 其他

image.png


参考博客

Map 综述(一):彻头彻尾理解 HashMap

全网把Map中的hash()分析的最透彻的文章,别无二家。

iOS中用到的数据结构_哈希表

你还应该知道的哈希冲突解决策略

拉链法解决哈希冲突的方式和几种常见的散列函数

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1

联系我们