说到散列,一般对应于散列表(哈希表)和散列函数。我们今天不谈哈希表,仅谈下散列函数。
定义引一段百度百科关于散列函数的定义。
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。
简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
关于散列函数的定义有很多表述,大同小异,理解其概念和内涵即可。
性质查看维基百科和百度百科,两者关于散列的性质都提到了几点:
1、确定性如果两个散列值是不相同的,那么这两个散列值的原始输入也是不相同的;
2、冲突(碰撞)散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同;
3、不可逆性最后一个是关于是否可逆的,两者表述有所出入:
维基百科中,很明确地提出“散列函数必须具有不可逆性”,而百度百科的表述则模棱两可,相比之下,后者显得太不严谨了。笔者比较倾向于维基百科提到的不可逆性。
4、混淆性在“散列函数的性质”一节,维基百科还提到一点:
输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
该表述中有两个词:“强混淆”, “完全不同”。就是什么含义呢?
先来了解一个概念:雪崩效应其精髓在于“严格雪崩准则”:当任何一个输入位被反转时,输出中的每一位均有50%的概率发生变化。
再了解一个概念:Hamming distance。有的译作“海明距离”,有的则是“汉明距离”。名字不重要,重要的内涵。
两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。举例如下:10101和00110从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。
对应于散列,如果“部分改变输入值”, 前后两个两个散列的海明距离为散列长度的一半(也就是有一半的bit不相同),则为“50%的概率发生变化”。这样的散列函数,就是“具有强混淆特性的散列函数”。
散列函数举例常见的散列函数有MD5和SHA家族等加密散列函数,CRC也该也算是散列。两者都有用于数据校验,而前者还用于数字签名,访问认证等安全领域。不过我们今天不对加密散列做太多展开,主要讲讲下面两个散列:
BKDRHash这个散列函数大家应该见过,可能有的读者不知道它的名字而已。JDK中String的hashCode()就是这个散列函数实现的:
public int hashCode() {
int h = hash;
final int len = length();
if (h == 0 && len > 0) {
for (int i = 0; i < len; i++) {
h = 31 * h + charAt(i);
}
hash = h;
}
return h;
}
定义一个类,如果让IDE自动生成hashCode()函数的话,其实现也是类似的:
public static class Foo{
int a;
double b;
String c;
@Override
public int hashCode() {
int result;
long temp;
result = a;
temp = Double.doubleToLongBits(b);
result = 31 * result + (int) (temp ^ (temp >>> 32));
result = 31 * result + (c != null ? c.hashCode() : 0);
return result;
}
}
为什么总是跟“31”过不去呢?为什么要这样迭代地求积和求和呢?这篇文章讲到了其中一些原理:哈希表之bkdrhash算法解析及扩展而知乎上也有很多大神做了分析:hash算法的数学原理是什么,如何保证尽可能少的碰撞从第二个链接给出的评分对比可以看出,BKDRHash虽然实现简单,但是很有效(冲突率低)。
低冲突,使得BKDRHash不仅仅用于哈希表,还用于索引对象。这样的用法,最常见的还是MD5,有的网站可能会用文件的MD5作为检索文件的key, 像DiskLruCache也是用MD5作为key, 不过通常不是对文件本身计算MD5,而是对url做MD5(例如OkHttp, Glide)。MD5生成的消息摘要有128bit, 如果要标识的对象不多,冲突率会很低;当冲突率远远低于硬件损坏的概率,那么可以认为用MD5作为key是可靠的。对于网站,如果要存储海量文件,不建议用MD5作为key。顺便提一下,UUID其实也是128bit的精度,只是其为了方便阅读多加了几个分割线而已。
扯远了, 回归正题~之所以看到BKDRHash用来索引对象,主要是看到这篇文章(笔者没有研究过Volley源码):Android Volley 源码解析(二),探究缓存机制里面提到Volley缓存的key的设计:
private String getFilenameForKey(String key) {
int firstHalfLength = key.length() / 2;
String localFilename = String.valueOf(key.substring(0, firstHalfLength).hashCode());
localFilename += String.valueOf(key.substring(firstHalfLength).hashCode());
return localFilename;
}
由于JDK的hashCode()返回值是int型,这个函数可以说是64bit精度的。不能说它是散列函数,因为其返回值长度并不固定,按照定义,不能称之为散列函数,虽然思想很接近。其等价写法如下:
public static String getFilenameForKey(String key) {
byte[] bytes = key.getBytes();
int h1 = 0, h2 = 0;
int len = bytes.length;
int firstHalfLength = len / 2;
for (int i = 0; i < firstHalfLength; i++) {
byte ch = bytes[i];
h1 = 31 * h1 + ch;
}
for (int i = firstHalfLength; i < len; i++) {
byte ch = bytes[i];
h2 = 31 * h2 + ch;
}
long hash = (((long) h1 > r;
k *= m;
h ^= k;
h *= m;
}
const unsigned char * data2 = (const unsigned char*)data;
switch(len & 7)
{
case 7: h ^= uint64_t(data2[6])
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?