hash算法就是,用同一个哈希函数计算:
两个相同的值,计算出的hash值一定相同,
两个不同的值,计算出的hash值可能不同,也可能相同,当相同时就是hash冲突
一、链式寻址法
也叫“拉链法”,把相同hash值的对象组成一条链,O(n)
HashMap中使用过
并且在HashMap 1.8中,当链的长度达到8,并且容量达到64时,会转为红黑树,O(logn)
二、线性寻址法
也叫“开放寻址法”
直接从冲突的数组位置往下寻找一个空的数组下标进行数据存储
ThreadLocal里面有使用到
三、再hash法
hash冲突了,就用新的哈希函数再次计算hash值,直到不冲突为止
降低了效率
布隆过滤器用到
四、公共溢出区
把存在冲突的key统一放在一个公共溢出区里面
好文阅读
评论可见,请评论后查看内容,谢谢!!!评论后请刷新页面。
发表评论