首页  思维导图  详情



 



Hash 分析

2020-11-18 12:11:43   0  举报





AI智能生成

hash函数介绍，map中的hash函数粉嫩小

hash

map

碰撞

扰动函数

模板推荐

作者其他创作

大纲/内容

直接定址法

直接以关键字k或者k加上某个常数（k+c）作为哈希地址

数字分析法

提取关键字中取值比较均匀的数字作为哈希地址

取余法

用关键字k除以某个不大于哈希长度m的数p，将所得余数作为哈希表地址。

分段叠加法

按照哈希表地址将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。

平方取中法

如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。

伪随机法

采用一个伪随机数当作哈希函数。

hash，一般翻译为“散列”，也可以直接音译为“哈希”。就是把任意长度但输入，通过散列算法，变换为固定长度但输出，该输出就是散列值。这种转换是一种压缩转换，散列值但空间通常小于输入的空间，不同的输入可能会散列成相同的输出。

简单的说，hash函数就是一种将任意长度的消息压缩到某一固定长度的消息摘要

碰撞：两个不同的输入值，根据同一散列函数计算除相同散列值的现象

解决哈希碰撞

开放地址法

一旦发生来冲突，就去寻找下一个空的散列地址。只要散列表足够大，空的散列地址总能找到，并将记录存入

链地址法

将hash表的每个单元作为链表的头节点，所有hash地址冲突的节点都会被放在链表上。采用尾插法，关键字放在链表的尾部

再哈希法

当哈希地址发生冲突时，用其他的函数计算另一个哈希函数地址，知道冲突不再产生为止。

建立公共溢出区

将哈希表分为基本表和溢出表两部分，发生冲突的元素都放在溢出表中

Map中的hash

HashMap

indexFor

将hash生成的整型转换成链表数组中的下标。

源码

优势：位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

注意：必须保证数组容量是2的整数幂

与数组长度-1 进行与操作，最终的结果一定可以保证是正数。

hash

主将Object转换成一个整形，通过扰动的方式

为什么计算哈希地址前，需要先调用hash方法？

因为在对象的hashCode方法实现不好的情况下，会很大概率存在，低外相同，高位不同的情况，在和数组长度取余的过程中，高位被抹掉，相当于只是低位在做与操作，就会出现频繁的碰撞。所有需要hash方法，对hashcode值的高低位进行融合干扰，干扰后就会降低碰撞的概率。

1.7

源码

进行了4次异或操作

1.8

源码

做了优化，只做一次16位右移异或混合，而不是四次

ConcurrenntHashMap

1.7

源码

和hashmap的思路一致的。使用位运算代替取模，然后再对hashcode进行扰动。

使用的是一种变种的Wang/Jenkins哈希算法，主要目的也是为了把高低位组合在一起，避免冲突。

1.8

源码

不同

hash方法修改为spread方法

扰动后的散列值与 HASH_BITS 值进行与操作，保证结果为正整数，HASH_BITS的值为 0x7fffffff

HashTable

1.7

源码

相当于只是对k做了个简单的hash，取了一下其hashCode。而HashTable中也没有indexOf方法，取而代之的是这段代码：int index = (hash & 0x7FFFFFFF) % tab.length;。也就是说，HashMap和HashTable对于计算数组下标这件事，采用了两种方法。HashMap采用的是位运算，而HashTable采用的是直接取模。

把hash值和0x7FFFFFFF做一次按位与操作

保证得到的index的第一位为0，也就是为了得到一个正数。因为有符号数第一位0代表正数，1代表负数。

为什么没有选择位运算而是直接取模

hashtable的容量一直都是素数，扩容是2n+1，对于素数，简单的取模，哈希结果会更均匀

1.8

源码

取消了hash方法，但是哈希的操作还是有的。但是hash值少了和hashSeed的异步操作，而是直接使用对象的hashCode值。