哈希表原理

散列表

核心概念界定

每个键均对应一个对应的值

每当需要获取键时，将其输入散列函数 h(key) 进行计算，以获得相应的下标

随后将该值存储在数组中对应下标的位置

装填因子的计算方式为表中所含元素数量除以表的总容量

散列函数的构造方法 :

(尽管函数设计上要求输入参数为数值类型, 但实际应用中 key 的数据形式可以是字符串, 原因在于字符串内容可通过二进制编码方式进行表达)

直接寻址方式

h(key) = a * key + b (其中 a 与 b 均为固定常数)

余数保留法

h(key) = key mod p (通常选择 p 为质数)

数字特征提取法

h(key) = atoi(key+n) (选取 key 中具有特定意义的若干字符并将其转化为数值形式)

分段叠加法

将 key 按照相同位数进行分割后, 将各部分数值相加得到对应的下标值

平方中间取值法

通过计算 key 的平方值, 并从中截取中间位置的若干位数字作为最终的下标

如何解决冲突 :

当多个不同的输入经过哈希函数处理后得到相同的输出值时，这种情况应当如何应对？

一, 开放定址法

【当发生地址冲突时，应尝试更换其他存储位置
hi = (h(key) + di) mod TableSize
(i 表示第 i 次