【Java 数据结构 算法】宁可累死自己, 也要卷死别人 9 哈希表原理

概述

从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.

哈希表

哈希表 (Hash Table), 是根据关键码值 (Key Value) 直接进行访问的数据结构. 哈希表通过把键 (key) 映射到表中一个位置来访问记录, 以加快查找的速度. 如图:

这个映射函数叫做散列函数, 存放的记录叫做散列表. 哈希表体现了算法设计领域中空间换时间的思想.

哈希函数

哈希函数 (Hash Function) 又称散列算法, 哈希函数. 哈希函数通过将任意长度的输入值转变成固定长度的值输出.

设计哈希函数的原则:

1. 一致性: 如果 a==b, 那么 hash(a) == hash(b)
2. 高效性: 哈希函数的计算要简单高效
3. 均匀性: 尽可能地让哈希值均匀分布

哈希函数处理数据的方法:

1. 小整数
   • 正整数: 直接使用
   • 负整数: 偏移成正整数再使用
2. 大整数
   • 取部分: 取大整数后 n 位
   • 对 m 取模: 通常对质数取模
3. 浮点型
   • java 中使用 float 和 double 来表示浮点数
   • 遵循哈希函数设计将浮点型转换成整型
4. 字符串
   • 将字符串类型转换为整型处理, 将字符串类型看做 26 进制数表示
   • 计算出字符串对应的哈希值后, 对一个质数 M 取模得到哈希函数
5. 引用类型
   • 引用类型可以直接套用字符串的哈希函数, 求得 hash 值