Hash 分析
2020-11-18 12:11:43 0 举报AI智能生成
hash函数介绍，map中的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
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值。
0 条评论
下一页
为你推荐
查看更多
