type
status
date
slug
summary
tags
category
icon
password
@ZZHow(ZZHow1024)
哈希表
- 存储结构
- 拉链法：在找到的位置向下拉一条单链表
- 开放寻址法：从找到的位置开始继续向后寻找空的位置
- 字符串哈希方式：
- 把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。 采用字符的 ASCII 码乘上 P 的次方来计算哈希值。
- 映射公式 (X1 × Pn − 1 + X2 × Pn − 2 + ⋯ + Xn − 1 × P1 + Xn × P0) % Q
- 注意点：
- 任意字符不可以映射成 0，否则会出现不同的字符串都映射成 0 的情况，比如A, AA, AAA 皆为 0。
- 冲突问题：通过设置 P(131 或 13331) , Q()的值，一般可以理解为不产生冲突，P 和 Q 是经验值。
模拟散列表
- 寻找质数
- 处理哈希冲突
- 拉链法
b. 开放寻址法