Hash Value

一、哈希表 - 散列表

• 是一种具有高效查询的数据结构，时间复杂度为 O(1)
• 在表中根据 关键字key 查找 数据存储地址
• 散列表的查找、插入、删除时间复杂度均为 O(1)

二、哈希表的特点

• 一致性；每次输入相同的数值都会获得固定的输出
• 不同的输入映射到不同的数字

三、哈希表的应用

• 模拟映射关系
• 防止重复关系
• 缓存/记住数据

四、哈希函数 - 散列函数

• 为了节省查询速度，免去多次的比较，在他们的 键key 和 存储地址 建立对应的函数关系 hash()，称为哈希函数

五、哈希函数的创建方式

• 直接定址法：
  hash(k) = k / hash(k) = a * k + b，其中 a、b 为常数
• 除留余数法：取关键字被某个不大于散列表表长m的数 p 除后所得余数的散列地址
• 数字分析法、平方取中法、折叠法、随机法

六、负载因子

• 衡量哈希表的空/满程度：
  负载因子 = 填入表中的元素个数/散列表的个数
  负载因子越大，说明哈希表越满，查询速度越慢
• 一般来说负载因子大于 0.7 或 等于 1 的时候，哈希表将自动扩容（扩容时需要重新装填内存，需要耗费大量调整时间）

七、哈希冲突

• 不同的 key 产生相同的 哈希值

八、影响哈希冲突的两个方面

• 负载因子
• 散列函数

九、处理哈希冲突的几种方法

• 开放地址法 - 线性检测：hash = (hash(key) + d) % m, i = 1,2...k（k <= m）
  m 为散列表长，di 为增量序列，i为已发生冲突的次数
• 线性探测：d = 1, 2, 3...（m - 1）
• 平方探测：
• 伪随机探测：d = 伪随机序列
• 拉链法：为存在冲突的地址添加一个链表，如果同一个位置中存在一个较长的链表，会严重影响效率。

十、时间复杂度

• 一个函数定性描述该算法的运算时间
• T(n) 计算出 n 次执行下的所有操作的执行次数
• 例如: 计算几重 for 循环，一重循环为 T(n) = n，二重循环
• 计算出 T(n) 的同数量级，例如 ，它的数量级为 ，所以