java集合问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java集合问题,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5096字,纯文字阅读大概需要8分钟。
内容图文
1.jdk1.7
1.1hasmap
1.1.1.结构
数组+链表结构
1.1.2.线程不安全
1.扩容线程的不安全,头插法造成死循环,这个过程出现在扩容的过程中
主要的扩容代码如下,使用的是头插法
【参考1】
do {
Entry<K,V> next = e.next;//取出第一个元素
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
正常的ReHash的过程(单线程):
假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。
最上面的是old hash 表,其中的Hash表的size=2, 所以key = 3, 7, 5,在mod 2以后都冲突在table[1]这里了。
接下来的三个步骤是Hash表 resize成4,然后所有的<key,value> 重新rehash的过程。
并发下的Rehash(多线程)
1)假设我们有两个线程。
而我们的线程二执行完成了。于是我们有下面的这个样子:
注意,因为Thread1的 e 指向了key(3),而next指向了key(7),其在线程二rehash后,指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。在这里线程一变成了操作经过线程二操作后的HashMap。
2)线程一被调度回来执行。
先是执行 newTalbe[i] = e;
然后是e = next,导致了e指向了key(7),
而下一次循环的next = e.next导致了next指向了key(3)。
3)一切安好。
线程一接着工作。把key(7)摘下来,放到newTable[i]的第一个,然后把e和next往下移。这个元素所在的位置上已经存放有其他元素了,那么在同一个位子上的元素将以链表的形式存放,新加入的放在链头,而先前加入的放在链尾。
4)环形链接出现。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)。
注意:此时的key(7).next 已经指向了key(3), 环形链表就这样出现了。
1.1.3.put操作
- 首先判断数组是否初始化,若没有则先进行初始化(初始化为给定参数的最接近的下取整2的幂次方,或者初始化为16默认值)
- 根据hashcode计算hash值(进行二次hash以减少碰撞)
- 根据hash值索引找到对应的位置
- 遍历当前的链表看能否找到对应的equals相同的key,找到后进行覆盖,若没有首先判断当前数组元素数量是否达到扩容阈值(数组长度*loadfactor),达到后先进行扩容,然后头插法插入,如果没有达到阈值那么直接头插法插入。(注意扩容有两个条件:1.首先达到阈值2.存在hash冲突)
5.这里有一个特殊的情况key为null,存入table[0]中。
参考 https://blog.csdn.net/yueaini10000/article/details/108992951
1.2 ConcurrentHashMap
1.2.1 put操作
- 首先进行第一次hash定位到相应的segment,如果还没有初始化就cas进行赋值,然后进行第二次hash操作定位到hashEntry位置,这个时候就会利用Reentrentlock的trylock获取锁,如果获取成功那么就在相应的位置或者链表进行插入,如果获取失败就会进行自旋,当自旋到一定的次数就会挂起。
2.在插入的时候会先进行判断是否超过了hashenry数组的阈值,超过了就先进行扩容 - 如何扩容?首先建立一个2倍大小的数组,然后将数组中的元素,先散列后再插入。
参考: https://blog.csdn.net/csdnlijingran/article/details/88946558
2. jdk1.8
2.1.hashmap
结构:数组+链表+红黑树
2.1.1.put操作
- 首先判断数组是否初始化,若没有初始化则先对数组进行初始化
- 然后计算hash值,根据hash值得到在数组中的索引
- 判断当前索引结点是否为空,如果为空那么直接插入,否则就是红黑树或者链表
- 如果是红黑树,则遍历红黑树,如果存在相同的key那么直接覆盖value,如果不存在插入红黑树中
- 如果是链表就遍历链表,如果存在相同key则直接覆盖,不存在则插入链表尾部,如果链表长度大于8且数组长度小于64,则先进行扩容,如果数组长度大于64,且链表长度大于8则会转化为红黑树,见下源码
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods. * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don‘t change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // 此处,大于8的时候进行树化,但是treeifyBin中还有判断条件 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//如果小于64那么先进行扩容 resize(); else if ((e = tab[index = (n - 1) & hash]) != null) {//否则才进行树化 TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }
2.1.2. 1.8中的线程不安全
1.8中会出现数据覆盖的情况
举例子:(假设两者put的数据在hash表中不存在)假设A,B两个线程,A线程与B线程都要进行put,且计算的hash索引位置相同,那么当A计算判断完没有,此时时间片用完,B判断完没有在尾部插入后,此时A接着完成插入,那么就会覆盖掉B插入的数据
2.2 ConcurrentHashMap
2.2.1 put操作
如何保证了线程安全?
使用了CAS+sychronized实现并发或者更新操作
- 如果数组没有初始化就先进行初始化操作
- 然后利用hash值计算索引位置,如果没有冲突就直接cas插入
- 如果正在扩容就帮助扩容
- 如果存在hash冲突就加锁来保证线程的安全,
- 如果是红黑树,遍历红黑树,如果存在相同的key就覆盖value,否则插入红黑树中
- 如果是链表,那么就遍历链表,如果存在key就覆盖value,如果不存在就插入尾部
如果链表长度大于8且数组长度小于64,则先进行扩容,如果数组长度大于64,且链表长度大于8则会转化为红黑树
3. 1.7与1.8之间的区别
hashmap
区别 | jdk1.7 | jdk1.8 |
---|---|---|
结构 | 数组(entry)+链表 | 数组(node)+链表+红黑树 |
扩容 | 先扩容后插入 | 先插入后扩容 |
插入 | 头插法 | 尾插法 |
哈希值的计算 | 将原哈希值和左移20位、左移12位、左移7位、左移4位的四个值,一起异或运算(^)。参考 https://blog.csdn.net/u013490280/article/details/108860964 | 将原哈希值和左移16位的值,一起异或运算(^)。 |
扩容策略 | 1.7中是只要不小于阈值就直接扩容2倍 | 而1.8的扩容策略会更优化,当数组容量未达到64时,以2倍进行扩容,超过64之后若桶中元素个数不小于7就将链表转换为红黑树,但如果红黑树中的元素个数小于6就会还原为链表,当红黑树中元素不小于32的时候才会再次扩容。 |
下标计算 |
concurrenthashmap
区别 | jdk1.7 | jdk1.8 |
---|---|---|
结构 | 使用segment+hashEntry | 使用node数组 |
冲突后 | 链表 | 树化或链表 |
插入 | 先扩容后插入 | 先插入后扩容 |
参考
-
https://blog.csdn.net/dingjianmin/article/details/79780350
2.https://blog.csdn.net/yueaini10000/article/details/108992951
3.https://blog.csdn.net/csdnlijingran/article/details/88946558
原文:https://www.cnblogs.com/AI-Creator/p/14748696.html
内容总结
以上是互联网集市为您收集整理的java集合问题全部内容,希望文章能够帮你解决java集合问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。