14-2 哈希函数设计

知识点
1 哈希函数 得到的索引 分布越均匀越好
所有类型都转换为整形的哈希函数设计:
2小范围正整数直接用 , 负整数做偏移 -100~100 -> 0~200

3大整数的哈希函数:取模 , 身份证号取后四位 = mod 10000 12343253255312056666 -> 6666 ,
4 mod1000000->056666 , 1205 是生日 , 05 部分取值为01~31 , 而哈希空间为 00~99 , 造成了分布不均匀
5 每个领域都有不同的哈希函数设计 , 很难找到通用的设计
6 对身份证号取模没有利用所有信息( 信息摘要的概念? ) , 因此更容易产生冲突 , 信息越多越能接近唯一性 , 如用年月日区分 , 对比用省市区+年月日 , 更容易产生重复
7 模一个素数 , 更有效利用一个数字的所有信息 , 数论

8 32浮点型在计算机中的表示 , 32 或 64 位的二进制数 , 32 位的情况,单精度 从左边起 , 第一位是符号位 , 2-9 共 8 位是 exponent , 指数位 , 后面 23 位是 fraction 小数位
9 64 位浮点型的表示 , 第一符号位 , 2-12 , 11 位指数位 , 后面是 52 位的小数位
10 浮点型直接当做整形 , 然后同上作哈希
11 字符串也转成整型
12 166 也可以看成字符串 110^2 + 610^1 + 610^0
13 英文字母可以看成 26 进制 , code=c26^4 + o*26^3 ...........
14 字符串特别长的时候可能计算很慢 , 可以做变形减少计算次数

15 字符串特别长并且使用的进制特别大的时候可能产生溢出 , 可以把取模移到每一个里面

16 字符串哈希函数解决方案

17 复合类型 , 如类 , 将类中的属性 , 如 Date { year,month,day} , 取出来同上面的字符串一样取哈希

18 并不一定需要转成整型处理 , 还有其他方法

19 哈希函数设计原则 , 一致性 a 的哈希值永远是同一个 , 高效性, 计算速度快 , 均匀 , 分布均匀

本作品采用《CC 协议》，转载必须注明作者和本文链接