【数据结构】HashMap 面试题8问

面试题8问:

1. 如果new HashMap(19),bucket数组有多大?

答:hashmap数组大小初始为2的四次方,16,且每一次都是以2倍增长,数组大小总是2的次方倍;
所以给19大小的空间,需要的数组长度为最接近19的2的次方倍,也就是2的五次方32;

2. HashMap什么时候开辟bucket数组占用内存?

答:第一次放数据put时候,且初始化空间大小是16;

3. HashMap何时扩容?

答:超过负载因子(0.75)时候,(负载因子:填入表中的元素个数/散列表的长度),且扩容是2倍扩容的;

4. 当两个对象的hashcode相同时会发生什么?

答:会发生哈希冲突;(哈希冲突:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞)

5. 如果两个键的hashcode相同,要如何取值对象?

答:通过equals方法来取值对象,遍历与hashcode值相等时相连的链表,直到相同或者没有找到(null)

6. 你了解重新调整HashMap大小存在什么问题吗?

答:重新调整过HashMap大小后,原来存在的元素,需要重新哈希到新的链表当中。

7. HashMap中的hash函数作用?

【数据结构】HashMap 面试题8问
答:为了混合哈希值的高位和低位,增加低位的随机性,并且混合后的值也变相保持了高位的特征
(具体:右位移16位,正好是32bit的一半,自己的高半区和低半区做异或,就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来)

8. HashMap中存放数据确定数据存放下标的取模运算源码中为何这样实现?

源码中模运算是在这个indexFor( )函数里完成的。

【数据结构】HashMap 面试题8问
答:这样做的原因是
因为HashMap的数组长度是2的整数幂,数组长度-1 正好是一个奇数,奇数的二进制位的低位(最左边位)一定是1,可以 与运算& 后就可以在低位产生 0或者1,要是直接是数组长度的话,因为是偶数,二进制的低位一定是0,这样 与运算& 后就只在低位产生0。所以这样做之后产生的下标index的可能性就更多,从而也在避免哈希冲突的发生 !

  • over ~
上一篇:javax.servlet.ServletException:org.apache.shrio.session.UnknowSessionException:There is no session w


下一篇:【数字图像处理】二值图像行程编码