HashMap与HashTable在hash算法上的优化

HashMapHashTablehash算法上的优化:(两点)

1. HashMap在使用hashCode时不再直接使用,而是用它与它的高16位进行异或得到的新值,(h = key.hashCode()) ^ (h >>> 16)。因为这样防止在哈希表长度较小时,造成哈希码的使用不充分,低位哈希码对应位置大量
堆积导致冲突。
2. 通过hashCode寻找对应位置时,使用(n - 1) & hash代替原来的直接对长度n取模,这是数学公式:在n2的指数时,(n - 1) & hash = hash % n。(这充分利用了HashMap的扩容规律,初始16,每到达75%就扩容2倍)
(而HashTable扩容机制,初始11,每到达75%扩容2倍加一)

全部评论

相关推荐

点赞 评论 收藏
分享
专心打鱼:互联网搬运工,贴子都要偷
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务