ConcurrentBag的实现原理,Java集合类工作原理及实现

bwin必赢棋牌 2

目录

集合类的实现原理

  • 一、前言
  • 二、ConcurrentBag类
  • 三、
    ConcurrentBag线程安全实现原理

    • 1.
      ConcurrentBag的私有字段
    • 2.
      用于数据存储的TrehadLocalList类
    • 3.
      ConcurrentBag实现新增元素
    • 4. ConcurrentBag
      如何实现迭代器模式
  • 四、总结
  • 笔者水平有限,如果错误欢迎各位批评指正!

LRUCache原理

核心算法
map:存放数据的集合    new LinkedHashMap<K, V>(0, 0.75f, true);
size:当前LruCahce的内存占用大小
maxSize:Lrucache的最大容量
putCount:put的次数
createCount:create的次数
evictionCount:回收的次数
hitCount:命中的次数
missCount:丢失的次数

Lru是最近最少使用算法的简称,意思呢就是查询出最近的时间使用次数最少的那个对象。设置为true的时候,如果对一个元素进行了操作(put、get),就会把那个元素放到集合的最后,设置为false的时候,无论怎么操作,集合元素的顺序都是按照插入的顺序来进行存储的。
算法核心:当内容容量达到最大值的时候,只需要移除这个集合的前面的元素直到集合的容量足够存储数据的时候就可以了。


HashMap

图解HashMap(一)bwin必赢棋牌,/)

图解HashMap(二)/)

HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体

bwin必赢棋牌 1

image.png

简单地说,HashMap 在底层将 key-value
当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个
Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry
对象时,会根据 hash 算法来决定其在数组中的存储位置,在根据 equals
方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry
时,也会根据 hash 算法找到其在数组中的存储位置,再根据 equals
方法从该位置上的链表中取出该Entry。

扩容:当 HashMap 中的元素个数超过数组大小
loadFactor时,就会进行数组扩容,loadFactor的默认值为
0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为 16,那么当
HashMap 中元素个数超过 16
0.75=12 的时候,就把数组的大小扩展为
2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知
HashMap 中元素的个数,那么预设元素的个数能够有效的提高 HashMap 的性能。

Fail-Fast 机制:HashMap
不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了
map,那么将抛出 ConcurrentModificationException,这就是所谓 fail-fast
策略。
例如:当某一个线程 A 通过
iterator去遍历某集合的过程中,若该集合的内容被其他线程所改变了;那么线程
A 访问集合时,就会抛出ConcurrentModificationException 异常,产生
fail-fast 事件。
实现原理:判断 modCount 跟 expectedModCount
是否相等,如果不相等就表示已经有其他线程修改了 Map。
解决方案:建议使用“java.util.concurrent 包下的类”去取代“java.util
包下的类”

遍历方式:
第一种:

   Map map = new HashMap();
  Iterator iter = map.entrySet().iterator();
  while (iter.hasNext()) {
  Map.Entry entry = (Map.Entry) iter.next();
  Object key = entry.getKey();
  Object val = entry.getValue();
    }

效率高,以后一定要使用此种方式
第二种:

Map map = new HashMap();
  Iterator iter = map.keySet().iterator();
  while (iter.hasNext()) {
  Object key = iter.next();
  Object val = map.get(key);
  }

效率低,以后尽量少使用!


SparseArray

SparseArray
的使用及实现原理
优势:

  • 避免了基本数据类型的装箱操作
  • 不需要额外的结构体,单个元素的存储成本更低
  • 数据量小的情况下,随机访问的效率更高

有优点就一定有缺点

  • 插入操作需要复制数组,增删效率降低
  • 数据量巨大时,复制数组成本巨大,gc()成本也巨大
  • 数据量巨大时,查询效率也会明显下降

一、前言

笔者最近在做一个项目,项目中为了提升吞吐量,使用了消息队列,中间实现了生产消费模式,在生产消费者模式中需要有一个集合,来存储生产者所生产的物品,笔者使用了最常见的List<T>集合类型。

由于生产者线程有很多个,消费者线程也有很多个,所以不可避免的就产生了线程同步的问题。开始笔者是使用lock关键字,进行线程同步,但是性能并不是特别理想,然后有网友说可以使用SynchronizedList<T>来代替使用List<T>达到线程安全的目的。于是笔者就替换成了SynchronizedList<T>,但是发现性能依旧糟糕,于是查看了SynchronizedList<T>的源代码,发现它就是简单的在List<T>提供的API的基础上加了lock,所以性能基本与笔者实现方式相差无几。

最后笔者找到了解决的方案,使用ConcurrentBag<T>类来实现,性能有很大的改观,于是笔者查看了ConcurrentBag<T>的源代码,实现非常精妙,特此在这记录一下。

HashSet

对于 HashSet 中保存的对象,请注意正确重写其 equals 和 hashCode
方法,以保证放入的对象的唯一性。这两个方法是比较重要的,希望大家在以后的开发过程中需要注意一下。

bwin必赢棋牌 2

image.png

二、ConcurrentBag类

ConcurrentBag<T>实现了IProducerConsumerCollection<T>接口,该接口主要用于生产者消费者模式下,可见该类基本就是为生产消费者模式定制的。然后还实现了常规的IReadOnlyCollection<T>类,实现了该类就需要实现IEnumerable<T>、IEnumerable、 ICollection类。

ConcurrentBag<T>对外提供的方法没有List<T>那么多,但是同样有Enumerable实现的扩展方法。类本身提供的方法如下所示。

名称 说明
Add 将对象添加到 ConcurrentBag 中。
CopyTo 从指定数组索引开始,将 ConcurrentBag 元素复制到现有的一维 Array 中。
Equals(Object) 确定指定的 Object 是否等于当前的 Object。 (继承自 Object。)
Finalize 允许对象在“垃圾回收”回收之前尝试释放资源并执行其他清理操作。 (继承自 Object。)
GetEnumerator 返回循环访问 ConcurrentBag 的枚举器。
GetHashCode 用作特定类型的哈希函数。 (继承自 Object。)
GetType 获取当前实例的 Type。 (继承自 Object。)
MemberwiseClone 创建当前 Object 的浅表副本。 (继承自 Object。)
ToArray 将 ConcurrentBag 元素复制到新数组。
ToString 返回表示当前对象的字符串。 (继承自 Object。)
TryPeek 尝试从 ConcurrentBag 返回一个对象但不移除该对象。
TryTake 尝试从 ConcurrentBag 中移除并返回对象。

Hashtable

HashMap和HashTab的异同

1.HashTable 基于 Dictionary 类,而 HashMap 是基于
AbstractMap。Dictionary 是任何可将键映射到相应值的类的抽象父类,而
AbstractMap 是基于 Map
接口的实现,它以最大限度地减少实现此接口所需的工作。

2.HashMap 的 key 和 value 都允许为 null,而 Hashtable 的 key 和 value
都不允许为 null。HashMap 遇到 key 为 null 的时候,调用 putForNullKey
方法进行处理,而对 value 没有处理;Hashtable遇到 null,直接返回
NullPointerException。

3.Hashtable 方法是同步,而HashMap则不是。我们可以看一下源码,Hashtable
中的几乎所有的 public 的方法都是 synchronized
的,而有些方法也是在内部通过 synchronized
代码块来实现。所以有人一般都建议如果是涉及到多线程同步时采用
HashTable,没有涉及就采用 HashMap,但是在 Collections
类中存在一个静态方法:synchronizedMap(),该方法创建了一个线程安全的
Map 对象,并把它作为一个封装的对象来返回。

三、 ConcurrentBag线程安全实现原理

LinkedHashMap

LinkedHashMap是Hash表和链表的实现,并且依靠着双向链表保证了迭代顺序是插入的顺序
其实 LinkedHashMap 几乎和 HashMap
一样:从技术上来说,不同的是它定义了一个 Entry<K,V> header,这个
header 不是放在 Table 里,它是额外独立出来的。LinkedHashMap 通过继承
hashMap 中的 Entry<K,V>,并添加两个属性 Entry<K,V>
before,after,和 header
结合起来组成一个双向链表,来实现按插入顺序或访问顺序排序。
HashMap,LinkedHashMap,TreeMap的区别

发表评论

电子邮件地址不会被公开。 必填项已用*标注