- 概述
- 哈希表
- 哈希函数
从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.
哈希表哈希表 (Hash Table), 是根据关键码值 (Key Value) 直接进行访问的数据结构. 哈希表通过把键 (key) 映射到表中一个位置来访问记录, 以加快查找的速度. 如图:
这个映射函数叫做散列函数, 存放的记录叫做散列表. 哈希表体现了算法设计领域中空间换时间的思想.
哈希函数 (Hash Function) 又称散列算法, 哈希函数. 哈希函数通过将任意长度的输入值转变成固定长度的值输出.
设计哈希函数的原则:
- 一致性: 如果 a==b, 那么 hash(a) == hash(b)
- 高效性: 哈希函数的计算要简单高效
- 均匀性: 尽可能地让哈希值均匀分布
哈希函数处理数据的方法:
- 小整数
- 正整数: 直接使用
- 负整数: 偏移成正整数再使用
- 大整数
- 取部分: 取大整数后 n 位
- 对 m 取模: 通常对质数取模
- 浮点型
- java 中使用 float 和 double 来表示浮点数
- 遵循哈希函数设计将浮点型转换成整型
- 字符串
- 将字符串类型转换为整型处理, 将字符串类型看做 26 进制数表示
- 计算出字符串对应的哈希值后, 对一个质数 M 取模得到哈希函数
- 引用类型
- 引用类型可以直接套用字符串的哈希函数, 求得 hash 值
