藁城专业网站建设,杭州桐庐网站建设,狼人在线观看视频人在线,深圳市建设集团股份有限公司HashMap相关问题
HashMap实现原理
HashMap是以键值对的形式存储数据#xff0c;内部是通过数组链表结构实现#xff0c;在1.7之后的版本#xff0c;链表结构可以升级为红黑树#xff0c;提高查询效率
key和value都支持为null#xff1b;key为null时hash值是0#xff0…HashMap相关问题
HashMap实现原理
HashMap是以键值对的形式存储数据内部是通过数组链表结构实现在1.7之后的版本链表结构可以升级为红黑树提高查询效率
key和value都支持为nullkey为null时hash值是0取模后也是0 也是就是会存放在数组第一个链表中
HashMap的put、get、remove过程
put过程 先根据key值计算Hash值 再根据hash值与数组长度进行取模运算计算出要落在数组哪个位置上 接着判断数组是否为空为空的话对数组进行初始化默认数组容量是16 然后判断该数组位置是否已经存在元素如果不存在则直接创建Node结点放入数组对应位置 如果存在则继续判断是否是红黑树如果是红黑树则在红黑树中创建或者更新Node结点 如果是链表结构则先插入元素然后判断链表中元素个数是否已经到达阈值8个如果到达了并且数组容量大于64个则将当前链表升级为红黑树结构如果不足64则进行一次扩容 在扩容时红黑树会进行拆分拆分过程中会判断红黑树中结点是否少于阈值6个如果是的话变回链表结构 remove元素时判断根节点和左右子节点是否为null来决定是否转回链表结构而没有根据阈值6来判断 最后插入完元素后会判断当前元素总的个数是否达到阈值默认是数组容量的3/4如果达到了则进行扩容 3/4是根据空间和时间综合判定的如果设置过小则扩容频繁如果设置过大则hash冲突概率增加查找效率更低
get过程 先通过key计算hash值然后与数组长度取模运算确定在数组中的位置 然后判断数组中对应元素key值是否相同相同则返回该结点的value值 接着判断是否是红黑树如果是的话从红黑树中查找该key对应结点 如果是链表则遍历链表中每一个元素找到key值相同的Node结点并返回value值
remove过程 remove过程和查找差不多也是先计算hash值取模计算出数组位置然后判断是否红黑树等等找到元素后从原来位置删除 从红黑树中删除之后会判断根节点以及其左右结点是否为空来决定要不要转回链表结构
容量转为2的n次幂 int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; 现将设置的容量减1然后不断进行右移和或运算目的是将低位上的数都转为1(0000 1111)最后再1,形成(0001 0000)这种结构结果必然是2的n次方
Hash算法和Hash冲突问题 (key null) ? 0 : (h key.hashCode()) ^ (h 16) key可以为null hash值的计算key的hash值与它的高16位右移后进行异或运算目的是为了降低低16位相同的概率从而减少hash碰撞 这是因为跟数组长度-1进行与运算时数组长度-1的高位基本都是0进行与运算后结果也是0 如果两个数高位不同低位相同就会导致计算结果一致发生hash碰撞 所以需要降低低位相同的概率就能减少hash碰撞 为什么进行异或运算而不是与运算或者或等其他运算 因为如果进行与运算会导致结果趋向于0更多 进行或运算结果趋向于1更多 只有进行异或运算结果0和1的个数会趋于一样多这样结果随机性就更大hash碰撞概率就小很多 降低hash冲突办法 计算hash值的时候进行异或运算 降低负载因子(load factor)增加数组容量大小
计算数组中的位置 (n - 1) hash 根据Hash值和数组长度减1进行与运算相当于对数组长度取模运算保证取模后结果在数组长度范围内与运算速度要比取模运算快 数组容量大小是2的n次方可以保证数组大小-1后与hash值与运算后结果在数组范围内取代模运算效率更高
HashMap扩容机制 扩容时会先判断容量是否有初始化如果没有则先初始化为默认容量16或者传入的容量容量最大不能超过2的30次方 然后判断当前容量是否超过阈值默认是当前容量的3/4如果超过则进行扩容每次扩容会把容量增加到原来的2倍 接着会将原来数组中的数据根据hash值复制到扩容后的数组中在拷贝数据过程中原有链表或者红黑树会被拆分成两份一部分会保存在原有数组位置另一部分会存在当前数组位置加上原有数组容量大小的位置 根据if ((e.hash oldCap) 0) 判断链表中的元素是否需要移动如果等于0则不移动否则移动到当前数组位置加上旧数组容量大小的位置newTab[joldCap] 因为同一个Hash值跟数组扩容前和扩容后的大小进行取模运算后只有两种情况要么跟原来位置不变要么比原来位置多原来数组容量大小 扩容导致死循环问题 因为在1.7版本中HashMap扩容时采用的是头插法也就是拷贝旧数组中元素到新数组中时新元素是插入到链表头部的当并发时可能出现多个线程同时在扩容当其中一个线程正在将元素A移动到新的位置时A的下一个元素时B另一个线程正在将B插入A的前面但是A指向B的链接还没有断开B就指向了A这就会导致A和B互相链接着形成环状当调用get方法遍历链表时就可能会卡死在这里永远无法退出循环
HashMap如何保证线程安全
HashTable 底层实现也是数组链表 使用了Synchronized同步锁会锁住整个HashTable对象效率低 线程安全key和value都不能为null
ConcurrentHashMap 线程安全 将整个Map分成N个段Segment保存在数组中每个Segment又可以看做一个小型的HashMap内部由数据链表结构实现Segment继承自可重入锁 锁分段技术每一个Segment都是一个可重入锁每次只会锁住该段中的元素不会影响到其他段中元素的读写 扩容采用段内扩容每次扩容只针对当前Segment不会对整个表扩容 有些操作需要锁定整个表比如获取所有元素个数size或者判断某个元素是否在表中containsValue操作 在计算size时会先尝试几次不加锁统计当发现算了几次结果都一样时则任务没有新增或者删除如果有变化则强制将所有Segment加锁后再统计 jdk1.8后的变化 参考地址https://blog.csdn.net/qq_26542493/article/details/105651338cd1hlzh-CNctclnkglphstrip1
HashMap是否有序如何保证有序
无序的LinkedHashMap可以保证有序
为什么容量必须是2的N次方
很多地方用到二进制运算比如计算hash值计算数组中的位置扩容等使用2的N次方转成二进制就是一个1其他都是0方便二进制运算
参考链接https://blog.csdn.net/qq_26542493/article/details/105482732cd1hlzh-CNctclnkglphstrip1
