首页   快速返回

hashmap在java7和8中的区别     所属分类 java
java7 数组+单链表, java8 单链表超过一定长度后改成红黑树
java7 扩容时需要重新计算哈希值和索引位置,java8 不重新计算哈希值,采用和扩容后容量进行&操作来计算新的索引位置。
java7  单链表头部插入 ,Java8尾部插入

Java7 Entry
java8 TreeNode, Node

because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
2倍扩容 元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置

扩容时,不需要重新计算hash, hash值高位新增的那个bit是1还是0,是0的话索引不变,是1的话索引变成“原索引+oldCap”, 
直接拆分原链表为高低链表相比先保存数据再寻址追加效率更好。


头插法,扩容时会改变链表中元素原本的顺序,并发场景下导致链表成环
尾插法 保持链表元素原本的顺序 不会成环

threshold = loadFactor * capacity 
capacity = tableSize

size > threshold 时扩容  resize 


jdk8 链表长度大于8时 转成 红黑树

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
   treeifyBin(tab, hash);
   
static final int TREEIFY_THRESHOLD = 8;

final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
            
表长度小于  MIN_TREEIFY_CAPACITY 先做resize 

static final int MIN_TREEIFY_CAPACITY = 64;

上一篇     下一篇
java7 hashmap 要点

常用hash算法及冲突解决方法

java8 hashmap 要点

java位运算

HashMap和ConcurrentHashMap中的hash函数

ConcurrentHashMap读不需要加锁的秘密