`
qindongliang1922
  • 浏览: 2180756 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
7265517b-f87e-3137-b62c-5c6e30e26109
证道Lucene4
浏览量:117397
097be4a0-491e-39c0-89ff-3456fadf8262
证道Hadoop
浏览量:125814
41c37529-f6d8-32e4-8563-3b42b2712a50
证道shell编程
浏览量:59779
43832365-bc15-3f5d-b3cd-c9161722a70c
ELK修真
浏览量:71223
社区版块
存档分类
最新评论

理解Java7和8里面HashMap+ConcurrentHashMap的扩容策略

    博客分类:
  • JAVA
阅读更多
### 前言

理解HashMap和ConcurrentHashMap的重点在于:

(1)理解HashMap的数据结构的设计和实现思路

(2)在(1)的基础上,理解ConcurrentHashMap的并发安全的设计和实现思路

前面的文章已经介绍过Map结构的底层实现,这里我们重点放在其扩容方法,
这里分别对JDK7和JDK8版本的HashMap+ConcurrentHashMap来分析:


### JDK7的HashMap扩容

这个版本的HashMap数据结构还是数组+链表的方式,扩容方法如下:

```
void transfer(Entry[] newTable) {  
    Entry[] src = table;                   //src引用了旧的Entry数组  
    int newCapacity = newTable.length;  
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组  
        Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素  
        if (e != null) {  
            src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)  
            do {  
                Entry<K, V> next = e.next;  
                int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置  
                e.next = newTable[i]; //标记[1]  
                newTable[i] = e;      //将元素放在数组上  
                e = next;             //访问下一个Entry链上的元素  
            } while (e != null);  
        }  
    }  
}
```


上面的这段代码不并不难理解,对于扩容操作,底层实现都需要新生成一个数组,然后拷贝旧数组里面的每一个Node链表到新数组里面,这个方法在单线程下执行是没有任何问题的,但是在多线程下面却有很大问题,主要的问题在于基于头插法的数据迁移,会有几率造成链表倒置,从而引发链表闭链,导致程序死循环,并吃满CPU。据说已经有人给原来的SUN公司提过bug,但sun公司认为,这是开发者使用不当造成的,因为这个类本就不是线程安全的,你还偏在多线程下使用,这下好了吧,出了问题这能怪我咯?仔细想想,还有点道理。



### JDK7的ConcurrentHashMap扩容

HashMap是线程不安全的,我们来看下线程安全的ConcurrentHashMap,在JDK7的时候,这种安全策略采用的是分段锁的机制,ConcurrentHashMap维护了一个Segment数组,Segment这个类继承了重入锁ReentrantLock,并且该类里面维护了一个
HashEntry<K,V>[] table数组,在写操作put,remove,扩容的时候,会对Segment加锁,所以仅仅影响这个Segment,不同的Segment还是可以并发的,所以解决了线程的安全问题,同时又采用了分段锁也提升了并发的效率。
![image](http://pic.yupoo.com/goldendoc/Ba4GCFe1/nuEZ0.png)

下面看下其扩容的源码:

```
// 方法参数上的 node 是这次扩容后,需要添加到新的数组中的数据。
private void rehash(HashEntry<K,V> node) {
    HashEntry<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    // 2 倍
    int newCapacity = oldCapacity << 1;
    threshold = (int)(newCapacity * loadFactor);
    // 创建新数组
    HashEntry<K,V>[] newTable =
        (HashEntry<K,V>[]) new HashEntry[newCapacity];
    // 新的掩码,如从 16 扩容到 32,那么 sizeMask 为 31,对应二进制 ‘000...00011111’
    int sizeMask = newCapacity - 1;

    // 遍历原数组,老套路,将原数组位置 i 处的链表拆分到 新数组位置 i 和 i+oldCap 两个位置
    for (int i = 0; i < oldCapacity ; i++) {
        // e 是链表的第一个元素
        HashEntry<K,V> e = oldTable[i];
        if (e != null) {
            HashEntry<K,V> next = e.next;
            // 计算应该放置在新数组中的位置,
            // 假设原数组长度为 16,e 在 oldTable[3] 处,那么 idx 只可能是 3 或者是 3 + 16 = 19
            int idx = e.hash & sizeMask;
            if (next == null)   // 该位置处只有一个元素,那比较好办
                newTable[idx] = e;
            else { // Reuse consecutive sequence at same slot
                // e 是链表表头
                HashEntry<K,V> lastRun = e;
                // idx 是当前链表的头结点 e 的新位置
                int lastIdx = idx;

                // 下面这个 for 循环会找到一个 lastRun 节点,这个节点之后的所有元素是将要放到一起的
                for (HashEntry<K,V> last = next;
                     last != null;
                     last = last.next) {
                    int k = last.hash & sizeMask;
                    if (k != lastIdx) {
                        lastIdx = k;
                        lastRun = last;
                    }
                }
                // 将 lastRun 及其之后的所有节点组成的这个链表放到 lastIdx 这个位置
                newTable[lastIdx] = lastRun;
                // 下面的操作是处理 lastRun 之前的节点,
                //    这些节点可能分配在另一个链表中,也可能分配到上面的那个链表中
                for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
                    V v = p.value;
                    int h = p.hash;
                    int k = h & sizeMask;
                    HashEntry<K,V> n = newTable[k];
                    newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
                }
            }
        }
    }
    // 将新来的 node 放到新数组中刚刚的 两个链表之一 的 头部
    int nodeIndex = node.hash & sizeMask; // add the new node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;
}
```

注意这里面的代码,外部已经加锁,所以这里面是安全的,我们看下具体的实现方式:先对数组的长度增加一倍,然后遍历原来的旧的table数组,把每一个数组元素也就是Node链表迁移到新的数组里面,最后迁移完毕之后,把新数组的引用直接替换旧的。此外这里这有一个小的细节优化,在迁移链表时用了两个for循环,第一个for的目的是为了,判断是否有迁移位置一样的元素并且位置还是相邻,根据HashMap的设计策略,首先table的大小必须是2的n次方,我们知道扩容后的每个链表的元素的位置,要么不变,要么是原table索引位置+原table的容量大小,举个例子假如现在有三个元素(3,5,7)要放入map里面,table的的容量是2,简单的假设元素位置=元素的值 % 2,得到如下结构:

```
[0]=null
[1]=3->5->7
```


现在将table的大小扩容成4,分布如下:
```
[0]=null
[1]=5->7
[2]=null
[3]=3
```

因为扩容必须是2的n次方,所以HashMap在put和get元素的时候直接取key的hashCode然后经过再次均衡后直接采用&位运算就能达到取模效果,这个不再细说,上面这个例子的目的是为了说明扩容后的数据分布策略,要么保留在原位置,要么会被均衡在旧的table位置,这里是1加上旧的table容量这是是2,所以是3。基于这个特点,第一个for循环,作的优化如下,假设我们现在用0表示原位置,1表示迁移到index+oldCap的位置,来代表元素:
```
[0]=null
[1]=0->1->1->0->0->0->0
```

第一个for循环的会记录lastRun,比如要迁移[1]的数据,经过这个循环之后,lastRun的位置会记录第三个0的位置,因为后面的数据都是0,代表他们要迁移到新的数组中同一个位置中,所以就可以把这个中间节点,直接插入到新的数组位置而后面附带的一串元素其实都不需要动。

接着第二个循环里面在此从第一个0的位置开始遍历到lastRun也就是第三个元素的位置就可以了,只循环处理前面的数据即可,这个循环里面根据位置0和1做不同的链表追加,后面的数据已经被优化的迁移走了,但最坏情况下可能后面一个也没优化,比如下面的结构:

```
[0]=null
[1]=1->1->0->0->0->0->1->0
```


这种情况,第一个for循环没多大作用,需要通过第二个for循环从头开始遍历到尾部,按0和1分发迁移,这里面使用的是还是头插法的方式迁移,新迁移的数据是追加在链表的头部,但这里是线程安全的所以不会出现循环链表,导致死循环问题。迁移完成之后直接将最新的元素加入,最后将新的table替换旧的table即可。




### JDK8的HashMap扩容

在JDK8里面,HashMap的底层数据结构已经变为数组+链表+红黑树的结构了,因为在hash冲突严重的情况下,链表的查询效率是O(n),所以JDK8做了优化对于单个链表的个数大于8的链表,会直接转为红黑树结构算是以空间换时间,这样以来查询的效率就变为O(logN),图示如下:



我们看下其扩容代码:

```
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { 
                        //重点关注区域
                        // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

```

在JDK8中,单纯的HashMap数据结构增加了红黑树是一个大的优化,此外根据上面的迁移扩容策略,我们发现JDK8里面HashMap没有采用头插法转移链表数据,而是保留了元素的顺序位置,新的代码里面采用:

```
                        //按原始链表顺序,过滤出来扩容后位置不变的元素(低位=0),放在一起
                        Node<K,V> loHead = null, loTail = null;
                        //按原始链表顺序,过滤出来扩容后位置改变到(index+oldCap)的元素(高位=0),放在一起
                        Node<K,V> hiHead = null, hiTail = null;
```

把要迁移的元素分类之后,最后在分别放到新数组对应的位置上:

```
                        //位置不变    
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //位置迁移(index+oldCap)
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
```


JDK7里面是先判断table的存储元素的数量是否超过当前的threshold=table.length*loadFactor(默认0.75),如果超过就先扩容,在JDK8里面是先插入数据,插入之后在判断下一次++size的大小是否会超过当前的阈值,如果超过就扩容。



### JDK8的ConcurrentHashMap扩容

在JDK8中彻底抛弃了JDK7的分段锁的机制,新的版本主要使用了Unsafe类的CAS自旋赋值+synchronized同步+LockSupport阻塞等手段实现的高效并发,代码可读性稍差。

ConcurrentHashMap的JDK8与JDK7版本的并发实现相比,最大的区别在于JDK8的锁粒度更细,理想情况下talbe数组元素的大小就是其支持并发的最大个数,在JDK7里面最大并发个数就是Segment的个数,默认值是16,可以通过构造函数改变一经创建不可更改,这个值就是并发的粒度,每一个segment下面管理一个table数组,加锁的时候其实锁住的是整个segment,这样设计的好处在于数组的扩容是不会影响其他的segment的,简化了并发设计,不足之处在于并发的粒度稍粗,所以在JDK8里面,去掉了分段锁,将锁的级别控制在了更细粒度的table元素级别,也就是说只需要锁住这个链表的head节点,并不会影响其他的table元素的读写,好处在于并发的粒度更细,影响更小,从而并发效率更好,但不足之处在于并发扩容的时候,由于操作的table都是同一个,不像JDK7中分段控制,所以这里需要等扩容完之后,所有的读写操作才能进行,所以扩容的效率就成为了整个并发的一个瓶颈点,好在Doug lea大神对扩容做了优化,本来在一个线程扩容的时候,如果影响了其他线程的数据,那么其他的线程的读写操作都应该阻塞,但Doug lea说你们闲着也是闲着,不如来一起参与扩容任务,这样人多力量大,办完事你们该干啥干啥,别浪费时间,于是在JDK8的源码里面就引入了一个ForwardingNode类,在一个线程发起扩容的时候,就会改变sizeCtl这个值,其含义如下:

```
sizeCtl :默认为0,用来控制table的初始化和扩容操作,具体应用在后续会体现出来。
-1 代表table正在初始化
-N 表示有N-1个线程正在进行扩容操作
其余情况:
1、如果table未初始化,表示table需要初始化的大小。
2、如果table初始化完成,表示table的容量,默认是table大小的0.75倍
```

扩容时候会判断这个值,如果超过阈值就要扩容,首先根据运算得到需要遍历的次数i,然后利用tabAt方法获得i位置的元素f,初始化一个forwardNode实例fwd,如果f == null,则在table中的i位置放入fwd,否则采用头插法的方式把当前旧table数组的指定任务范围的数据给迁移到新的数组中,然后
给旧table原位置赋值fwd。直到遍历过所有的节点以后就完成了复制工作,把table指向nextTable,并更新sizeCtl为新数组大小的0.75倍 ,扩容完成。在此期间如果其他线程的有读写操作都会判断head节点是否为forwardNode节点,如果是就帮助扩容。

扩容源码如下:

```
    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        int n = tab.length, stride;
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        if (nextTab == null) {            // initiating
            try {
                @SuppressWarnings("unchecked")
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab;
            transferIndex = n;
        }
        int nextn = nextTab.length;
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        boolean advance = true;
        boolean finishing = false; // to ensure sweep before committing nextTab
        for (int i = 0, bound = 0;;) {
            Node<K,V> f; int fh;
            while (advance) {
                int nextIndex, nextBound;
                if (--i >= bound || finishing)
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            else {
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        Node<K,V> ln, hn;
                        if (fh >= 0) {
                            int runBit = fh & n;
                            Node<K,V> lastRun = f;
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            for (Node<K,V> p = f; p != lastRun; p = p.next) {
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                if ((ph & n) == 0)
                                    ln = new Node<K,V>(ph, pk, pv, ln);
                                else
                                    hn = new Node<K,V>(ph, pk, pv, hn);
                            }
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                        else if (f instanceof TreeBin) {
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> lo = null, loTail = null;
                            TreeNode<K,V> hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode<K,V> p = new TreeNode<K,V>
                                    (h, e.key, e.val, null, null);
                                if ((h & n) == 0) {
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else {
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin<K,V>(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin<K,V>(hi) : t;
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }
```


### 在扩容时读写操作如何进行

(1)对于get读操作,如果当前节点有数据,还没迁移完成,此时不影响读,能够正常进行。

如果当前链表已经迁移完成,那么头节点会被设置成fwd节点,此时get线程会帮助扩容。


(2)对于put/remove写操作,如果当前链表已经迁移完成,那么头节点会被设置成fwd节点,此时写线程会帮助扩容,如果扩容没有完成,当前链表的头节点会被锁住,所以写线程会被阻塞,直到扩容完成。

### 对于size和迭代器是弱一致性

volatile修饰的数组引用是强可见的,但是其元素却不一定,所以,这导致size的根据sumCount的方法并不准确。

同理Iteritor的迭代器也一样,并不能准确反映最新的实际情况



### 总结

本文主要了介绍了HashMap+ConcurrentHashMap的扩容策略,扩容的原理是新生成大于原来1倍大小的数组,然后拷贝旧数组数据到新的数组里面,在多线程情况下,这里面如果注意线程安全问题,在解决安全问题的同时,我们也要关注其效率,这才是并发容器类的最出色的地方。













0
0
分享到:
评论

相关推荐

    2.Java7_8+中的+HashMap+和+ConcurrentHashMap+全解析1

    同时,HashMap的扩容策略也有所调整,使得在高负载下性能更优。ConcurrentHashMap在Java 8中也进行了优化,取消了分段锁,改用ForkJoinPool和CAS操作,实现更为细粒度的并发控制,进一步提升了并发性能。 对于Java ...

    java7-8中的 HashMap和ConcurrentHashMap全解析.pdf

    在Java 7和8中,HashMap和ConcurrentHashMap是两种重要的数据结构,分别用于非线程安全和线程安全的键值对存储。本篇文章将深入解析这两种数据结构的内部实现,帮助读者理解它们的工作原理。 HashMap是Java中最常用...

    HashMap与ConcurrentHashMap面试要点.pdf

    8. 最后,HashMap的元素个数加1,如果达到扩容阈值,则进行扩容操作。 ##### JDK8中HashMap的get方法实现过程 HashMap的get方法的步骤如下: 1. 根据key生成hashcode。 2. 判断数组是否为空,若为空返回null。 3....

    java的hashMap多线程并发情况下扩容产生的死锁问题解决.docx

    在Java的HashMap中,多线程并发环境...总之,理解HashMap的扩容机制和潜在的问题对于编写高性能、线程安全的Java程序至关重要。在多线程环境下,合理选择数据结构和同步策略可以避免这类问题,确保程序的稳定性和效率。

    深入Java集合学习系列:HashMap的实现原理

    本文将深入探讨HashMap的内部机制,包括其构造、工作原理、哈希函数、冲突解决策略以及扩容机制。 首先,HashMap的基本结构是由数组(Entry[] table)和链表组成的。每个元素是一个内部类Entry,它包含了键值对...

    Java魔法解密:揭秘HashMap底层机制.pptx.pptx

    **HashMap简介** HashMap是Java编程语言...总的来说,HashMap是Java中不可或缺的数据结构,通过理解其工作原理、存储结构和优化策略,可以帮助开发者更有效地利用HashMap,优化程序性能,同时避免潜在的线程安全问题。

    Java-并发容器之ConcurrentHashMap

    相比于HashMap,ConcurrentHashMap在多线程环境下提供了线程安全的保证,避免了因扩容导致的CPU资源消耗过高问题。传统的线程安全解决方案,如Hashtable或使用Collections.synchronizedMap包装HashMap,虽然实现了...

    自定义map实现java的hashmap

    - 扩容策略:当HashMap达到一定负载因子(如0.75)时,为了保持性能,需要扩容数组并重新分布所有键值对。这通常涉及到复制整个数据结构,是一个开销较大的操作。 - 线程安全:Java中的HashMap不是线程安全的,...

    Java中HashMap详解(通俗易懂).doc

    Java中的HashMap是一个非常重要的数据结构,它实现了Map接口,提供了键值对的高效存储和访问。HashMap基于哈希表(也称为散列表)原理工作,它允许用户通过键(Key)快速查找对应的值(Value)。在HashMap中,键和值...

    一文让你彻底理解JavaHashMap和ConcurrentHashMap

    Java中的HashMap和ConcurrentHashMap是两种非常重要的数据结构,它们都是Map接口的实现,用于存储键值对数据。HashMap是非线程安全的,而ConcurrentHashMap则是为多线程环境设计的线程安全版本。 HashMap在Java 1.7...

    Java-HashMap.rar_hashmap_java hashmap

    当元素数量达到容量与负载因子的乘积时,`HashMap`会自动进行扩容,将容量翻倍。 4. **键值对**:键(Key)必须实现`hashCode()`和`equals()`方法,以确保正确的哈希计算和比较。值(Value)可以是任意对象。 5. *...

    HashMap源码粗略解读(面试必问)

    - **扩容策略的优化**:Java 8解决了Java 7中并发扩容可能导致的死锁问题。 - **链表与红黑树的结合**:当链表长度超过8时,HashMap会将链表转换为红黑树,以进一步提高查找、插入和删除的性能。阈值为8是因为到达...

    通过面试题带你了解java的Map

    核心知识点包括Map的扩容机制、HashMap在Java 7和Java 8的区别、以及ConcurrentHashMap如何实现线程安全。 【标签】: "java" 【正文】: 1. **Map的扩容逻辑**: - 当HashMap中的元素数量达到当前容量的75%时,会...

    关于如何解决HashMap线程安全问题的介绍

    2. resize()方法的问题:HashMap在容量达到阈值时会进行扩容操作,这个过程中需要重新计算键的哈希值并调整元素的位置。在多线程环境下,两个线程同时触发扩容可能导致循环链表的形成,从而引发死循环,这是一种严重...

    HashMap与HashTable的区别(含源码分析)

    在Java编程语言中,`HashMap`和`HashTable`都是实现键值对存储的数据结构,但它们之间存在一些显著的区别,这些区别主要体现在...对于学习和理解,源码阅读是非常有价值的,可以帮助深入理解Java集合框架的设计原理。

    java课件-HashMap

    默认初始容量为16,负载因子为0.75,当实际元素数量达到容量的75%时,HashMap会进行扩容,新的容量通常是原来的两倍。 3. null键和null值:HashMap允许键和值为null。一个HashMap最多只能有一个键为null,因为null键...

    java软件技术文档-深入java8的集合3:HashMap的实现原理.pdf

    了解了以上知识点,我们可以更好地理解和优化在实际编程中使用 HashMap 的场景,比如预估数据量以选择合适的初始容量,或者根据业务需求调整负载因子,以及在多线程环境下考虑同步策略等。通过理解 HashMap 的工作...

    hashmap面试题_hashmap_

    1. HashMap的初始容量和扩容策略是什么? 答:初始容量为16,每次扩容时,新容量是原容量的1.5倍。扩容时,将旧数组中的元素重新散列到新数组中。 2. 为什么HashMap的key不能为null? 答:null键会覆盖原有的null...

    深入解读大厂java面试必考点之HashMap全套学习资料

    通过深入学习和理解这些知识点,你将能够在面试中自信地应对关于HashMap的问题,提升你的专业技能。这套学习资料应该包含了HashMap的实例分析、源码解读、常见面试题以及实战演练等内容,确保你全面掌握这一核心Java...

    Java HashMap高难度面试题集锦解析Java HashMap面试题及答案解析-高难度

    Java HashMap 是一个非常重要的数据结构,它在面试中经常被问到,因为它涉及到许多底层实现细节和并发问题。以下是对给定的Java HashMap面试题的详细解析: 1. **HashMap的内部实现原理**: HashMap基于哈希表,...

Global site tag (gtag.js) - Google Analytics