Hash 分析
2020-11-18 12:11:43 0 举报
AI智能生成
登录查看完整内容
hash函数介绍,map中的hash函数粉嫩小
作者其他创作
大纲/内容
hash函数
直接定址法
直接以关键字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
和hashmap的思路一致的。使用位运算代替取模,然后再对hashcode进行扰动。
使用的是一种变种的Wang/Jenkins哈希算法,主要目的也是为了把高低位组合在一起,避免冲突。
不同
hash方法修改为spread方法
扰动后的散列值与 HASH_BITS 值进行与操作,保证结果为正整数,HASH_BITS的值为 0x7fffffff
HashTable
相当于只是对k做了个简单的hash,取了一下其hashCode。而HashTable中也没有indexOf方法,取而代之的是这段代码:int index = (hash & 0x7FFFFFFF) % tab.length;。也就是说,HashMap和HashTable对于计算数组下标这件事,采用了两种方法。HashMap采用的是位运算,而HashTable采用的是直接取模。
把hash值和0x7FFFFFFF做一次按位与操作
保证得到的index的第一位为0,也就是为了得到一个正数。因为有符号数第一位0代表正数,1代表负数。
为什么没有选择位运算而是直接取模
hashtable的容量一直都是素数,扩容是2n+1,对于素数,简单的取模,哈希结果会更均匀
取消了hash方法,但是哈希的操作还是有的。但是hash值少了和hashSeed的异步操作,而是直接使用对象的hashCode值。
0 条评论
回复 删除
下一页