电子科技学校网站建设,wordpress积分等级,怎么样建设网站赚钱,甘肃网站优化文章目录 1、HashMap 设置值的原理2、HashMap 获取值原理3、HashMap Hash优化4、HashMap 寻址优化5、HashMap 是如何解决Hash冲突的#xff1f;5.1 get数据的时候#xff0c;如果定位到指定位置的元素是一个链表#xff0c;怎么办呢#xff1f;5.2 红黑树 6、数组扩容6.1 数… 文章目录 1、HashMap 设置值的原理2、HashMap 获取值原理3、HashMap Hash优化4、HashMap 寻址优化5、HashMap 是如何解决Hash冲突的5.1 get数据的时候如果定位到指定位置的元素是一个链表怎么办呢5.2 红黑树 6、数组扩容6.1 数组长度为16计算index6.2 数组长度为32 计算index6.3 扩容总结 1、HashMap 设置值的原理
根据key计算HashCode再使用HashCode对 数组长度取模结果一定是存放到数组中 的某一个位置。得到指定位置索引之后就往指定位置设置数据即可。
2、HashMap 获取值原理
根据key计算hashCode,再使用hashCode对 数据长度取模得到一个数组索引然后再根据索引从数组中获取指定数据即可。
3、HashMap Hash优化 // JDK 1.8以后的HashMap里面的一段源码static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}答案hash数组一般不会太大使用 key 的hashCode 和 key的hashCode 右移16位 进行异或运算的目的就是让 高低16位都参与运算减少hash冲突
4、HashMap 寻址优化
hash (n - 1)当n为2的n次方的时候 hash (n - 1) hash % n
答案hash (n - 1) - 效果是跟hash对n取模效果是一样的但是与运算的性能要比hash对n取模要高很多数学问题数组的长度会一直是2的n次方只要他保持数组长度是2的n次方
5、HashMap 是如何解决Hash冲突的
使用链表法解决。在数据的指定位置挂一个链表这个链表里放多个元素让多个 key-value 放在数据的同一个位置
5.1 get数据的时候如果定位到指定位置的元素是一个链表怎么办呢
get 的时候如果定位到数组发现这个位置挂了一个链表哦此时就会遍历 链表从链表里面选择到自己需要的那个 kye-value 就可以了。 5.2 红黑树
为了解决hash冲突的问题就会在 数据的指定为值挂一个链表如果链表的长度达到了一定的长度之后就会将链表转换成红黑树通过遍历一颗红黑树找到一个元素此时时间复杂度是 O(logn), 性能比链表要高一些。如果链表过长遍历的性能不高因此当链表长度超过一定限制的时候就会将链表转换成红黑树提升搜索性能。
6、数组扩容 6.1 数组长度为16计算index
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash1 1111 1111 1111 1111 0000 1111 0000 01010000 0000 0000 0000 0000 0000 0000 0101 5index 5的位置n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash2 1111 1111 1111 1111 0000 1111 0001 01010000 0000 0000 0000 0000 0000 0000 0101 5index 5的位置6.2 数组长度为32 计算index
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
结果 0000 0000 0000 0000 0000 0000 0000 0101 5index 5的位置n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
结果 0000 0000 0000 0000 0000 0000 0001 0101 21index 21的位置6.3 扩容总结
数据扩容 - 2倍扩容 - 重新对map中的每一个元素进行寻址-通过判断二进制结果是否多出来了一个bit为判断index的位置是否变化
如果数组的长度扩容之后 32重新对每个hash值进行寻址也就是用每个hash值跟新数组的length - 1进行与操作
判断二级制结果是否多出来一个bit的1如果没有多那么还是原来的index如果多了出来那么新的index oldIndex oldCap通过这个方法避免了rehash的时候用每个hash对数据的长度进行取模取模的性能不高位运算的性能比较高。
