HashMap为什么使用尾插法? |
您所在的位置:网站首页 › hashmap尾插法 › HashMap为什么使用尾插法? |
原文链接:https://www.jianshu.com/p/0df1f25139e4 一.那么关于遇到hash冲突时候这个数据是头插呢?还是尾插呢?关于HashMap链表插入问题,java8之前之前是头插法 头插法:就是说新来的值会取代原有的值,原有的值就顺推到链表中去,就像上面的例子一样,因为写这个代码的作者认为后来的值被查找的可能性更大一点,提升查找的效率。 在java8之后,都是所用尾部插入了。 hashmap的扩容原理 hashmap扩容分为两步 扩容:创建一个新的Entry空数组,长度是原数组的2倍。ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。为什么要重新Hash呢,不直接复制过去呢? 因为长度扩大以后,Hash的规则也随之改变。 Hash的公式—> index = HashCode(Key) & (Length - 1) 原来长度(Length)是8你位运算出来的值是2 ,新的长度是16你位运算出来的值明显不一样了,之前的所有数据的hash值得到的位置都需要变化。 如下图:👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇 扩容前: 就可能出现下面的情况,大家发现问题没有? B的下一个指针指向了A 使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了 那是不是意味着Java8就可以把HashMap用在多线程中呢? 我认为即使不会出现死循环,但是通过源码看到put/get方法都没有加同步锁,多线程情况最容易出现的就是:无法保证上一秒put的值,下一秒get的时候还是原值,所以线程安全还是无法保证。 二 .那我问你HashMap的默认初始化长度是多少?16,为啥是16呢?为啥用16不用别的呢? 因为在使用2的幂的数字的时候,Length-1的值是所有二进制位全为1,这种情况下,index的结果等同于HashCode后几位的值。 只要输入的HashCode本身分布均匀,Hash算法的结果就是均匀的。 这是为了实现均匀分布。 三 .为啥我们重写equals方法的时候需要重写hashCode方法呢?因为在java中,所有的对象都是继承于Object类。 Ojbect类中有两个方法equals、hashCode,这两个方法都是用来比较两个对象是否相等的。 在未重写equals方法我们是继承了object的equals方法,那里的 equals是比较两个对象的内存地址,显然我们new了2个对象内存地址肯定不一样 对于值对象,==比较的是两个对象的值 对于引用对象,比较的是两个对象的地址 所以如果我们对equals方法进行了重写,建议一定要对hashCode方法重写,以保证相同的对象返回相同的hash值,不同的对象返回不同的hash值。 不然一个链表的对象,你哪里知道你要找的是哪个,到时候发现hashCode都一样,这不是完犊子嘛。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |