江苏龙网

  1. 主页 > 生活百科 > >

HashMap的底层数据结构( 三 )

HashMap


数组长度为16时，有两个keyA和keyB 。
KeyA：n-1:0000 0000 0000 0000 0000 0000 0000 1111hash1: 1111 1111 1111 1111 0000 1111 0000 0101&结果:0000 0000 0000 0000 0000 0000 0000 0101 = 5KeyB:n-1:0000 0000 0000 0000 0000 0000 0000 1111 hash1: 1111 1111 1111 1111 0000 1111 0001 0101&结果:0000 0000 0000 0000 0000 0000 0000 0101 = 5在数组长度为16的时候，他们两个hash值冲突会使用拉链发解决冲突 。
当数组长度扩容到32之后，需要重新对每个hash值进行寻址，也就是每个hash值跟新的数组length-1 进行操作 。
KeyA：n-1:0000 0000 0000 0000 0000 0000 000*1* 1111hash1: 1111 1111 1111 1111 0000 1111 0000 0101&结果:0000 0000 0000 0000 0000 0000 0000 0101 = 5KeyB:n-1:0000 0000 0000 0000 0000 000*1* 0000 1111 hash1: 1111 1111 1111 1111 0000 1111 0001 0101&结果:0000 0000 0000 0000 0000 000*1* 0000 0101 = 21判断二进制结果是否多出一个bit的1，如果没有多，那就用原来的index，如果多出来了那就用index+oldCap，通过这个方式，避免了rehash的时候，用每个hash对新数组的length取模，取模性能不高，位运算性能比较高 。




推荐阅读


上一篇：Spring Cloud Gateway提供的简易网关实现方式，你使用过吗？

下一篇：如何利用Kurukshetra以交互式的方式学习如何进行安全编码