澳门至尊网站-首页

您的位置:澳门至尊网站 > 黑客安全 > ConcurrentBag的实现原理,Java集合类工作原理及实现

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

2019-10-20 01:12

目录

会集类的贯彻原理

  • 一、前言
  • 二、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(一)/)

图解HashMap(二)/)

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

图片 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 相月素个数超过 160.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 方法,以担保归入的靶子的独一日千里性。那五个方式是拾壹分首要的,希望大家在之后的支出进度中须要专心一下。

图片 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的区别

1. ConcurrentBag的民用字段

ConcurrentBag线程安全完成首假若因此它的数目存款和储蓄的结交涉细颗粒度的锁。

   public class ConcurrentBag<T> : IProducerConsumerCollection<T>, IReadOnlyCollection<T>
    {
        // ThreadLocalList对象包含每个线程的数据
        ThreadLocal<ThreadLocalList> m_locals;

        // 这个头指针和尾指针指向中的第一个和最后一个本地列表,这些本地列表分散在不同线程中
        // 允许在线程局部对象上枚举
        volatile ThreadLocalList m_headList, m_tailList;

        // 这个标志是告知操作线程必须同步操作
        // 在GlobalListsLock 锁中 设置
        bool m_needSync;

}

首荐大家来看它评释的民用字段,在那之中须要在意的是集聚的数据是寄放在在ThreadLocal线程本地存款和储蓄中的。也便是说访问它的每一种线程会维护贰个投机的聚合数据列表,三个集合中的数据大概会寄放在差异线程的本地存款和储蓄空间中,所以假使线程访问自个儿本地存储的目的,那么是尚未难点的,那正是促成线程安全的第风度翩翩层,使用线程本地存款和储蓄数据

接下来能够观望ThreadLocalList m_headList, m_tailList;以此是寄放着地点列表对象的头指针和尾指针,通过那八个指针,大家就足以通过遍历的格局来做客具备地点列表。它使用volatile修饰,差别意线程举办地面缓存,每一种线程的读写都以直接操作在分享内部存款和储蓄器上,这就保障了变量始终富有黄金时代致性。任何线程在其他时间展开读写操作均是风靡值。对于volatile修饰符,感谢本身是程序员提议描述不当。

最后又定义了二个表明,这几个标记告知操作线程必需实行同步操作,那是落实了贰个细颗粒度的锁,因为只有在多少个尺码满意的事态下才要求进行线程同步。

LinkedHashSet

  • LinkedHashSet 是 Set 的多个现实得以达成,其珍贵着二个运作于具有规规矩矩的再一次链接列表。此链接列表定义了迭代逐一,该迭代顺序可为插入顺序或是访谈顺序。
  • LinkedHashSet 承袭与 HashSet,并且当中间是透过 LinkedHashMap 来落实的。有一点点类似于大家前边说的LinkedHashMap 其内部是依照 Hashmap 达成平等,可是依然有一丝丝差其他(具体的差异大家能够团结去思维一下)。
  • 如若大家必要迭代的相继为插入顺序也许访谈顺序,那么 LinkedHashSet 是急需你首先怀想的。

2. 用以数据存款和储蓄的TrehadLocalList类

接下去我们来看一下ThreadLocalList类的结构,该类便是实际存款和储蓄了数额的地点。实际上它是选拔双向链表这种结构进行多少存储。

[Serializable]
// 构造了双向链表的节点
internal class Node
{
    public Node(T value)
    {
        m_value = value;
    }
    public readonly T m_value;
    public Node m_next;
    public Node m_prev;
}

/// <summary>
/// 集合操作类型
/// </summary>
internal enum ListOperation
{
    None,
    Add,
    Take
};

/// <summary>
/// 线程锁定的类
/// </summary>
internal class ThreadLocalList
{
    // 双向链表的头结点 如果为null那么表示链表为空
    internal volatile Node m_head;

    // 双向链表的尾节点
    private volatile Node m_tail;

    // 定义当前对List进行操作的种类 
    // 与前面的 ListOperation 相对应
    internal volatile int m_currentOp;

    // 这个列表元素的计数
    private int m_count;

    // The stealing count
    // 这个不是特别理解 好像是在本地列表中 删除某个Node 以后的计数
    internal int m_stealCount;

    // 下一个列表 可能会在其它线程中
    internal volatile ThreadLocalList m_nextList;

    // 设定锁定是否已进行
    internal bool m_lockTaken;

    // The owner thread for this list
    internal Thread m_ownerThread;

    // 列表的版本,只有当列表从空变为非空统计是底层
    internal volatile int m_version;

    /// <summary>
    /// ThreadLocalList 构造器
    /// </summary>
    /// <param name="ownerThread">拥有这个集合的线程</param>
    internal ThreadLocalList(Thread ownerThread)
    {
        m_ownerThread = ownerThread;
    }
    /// <summary>
    /// 添加一个新的item到链表首部
    /// </summary>
    /// <param name="item">The item to add.</param>
    /// <param name="updateCount">是否更新计数.</param>
    internal void Add(T item, bool updateCount)
    {
        checked
        {
            m_count++;
        }
        Node node = new Node(item);
        if (m_head == null)
        {
            Debug.Assert(m_tail == null);
            m_head = node;
            m_tail = node;
            m_version++; // 因为进行初始化了,所以将空状态改为非空状态
        }
        else
        {
            // 使用头插法 将新的元素插入链表
            node.m_next = m_head;
            m_head.m_prev = node;
            m_head = node;
        }
        if (updateCount) // 更新计数以避免此添加同步时溢出
        {
            m_count = m_count - m_stealCount;
            m_stealCount = 0;
        }
    }

    /// <summary>
    /// 从列表的头部删除一个item
    /// </summary>
    /// <param name="result">The removed item</param>
    internal void Remove(out T result)
    {
        // 双向链表删除头结点数据的流程
        Debug.Assert(m_head != null);
        Node head = m_head;
        m_head = m_head.m_next;
        if (m_head != null)
        {
            m_head.m_prev = null;
        }
        else
        {
            m_tail = null;
        }
        m_count--;
        result = head.m_value;

    }

    /// <summary>
    /// 返回列表头部的元素
    /// </summary>
    /// <param name="result">the peeked item</param>
    /// <returns>True if succeeded, false otherwise</returns>
    internal bool Peek(out T result)
    {
        Node head = m_head;
        if (head != null)
        {
            result = head.m_value;
            return true;
        }
        result = default(T);
        return false;
    }

    /// <summary>
    /// 从列表的尾部获取一个item
    /// </summary>
    /// <param name="result">the removed item</param>
    /// <param name="remove">remove or peek flag</param>
    internal void Steal(out T result, bool remove)
    {
        Node tail = m_tail;
        Debug.Assert(tail != null);
        if (remove) // Take operation
        {
            m_tail = m_tail.m_prev;
            if (m_tail != null)
            {
                m_tail.m_next = null;
            }
            else
            {
                m_head = null;
            }
            // Increment the steal count
            m_stealCount++;
        }
        result = tail.m_value;
    }


    /// <summary>
    /// 获取总计列表计数, 它不是线程安全的, 如果同时调用它, 则可能提供不正确的计数
    /// </summary>
    internal int Count
    {
        get
        {
            return m_count - m_stealCount;
        }
    }
}

从下边包车型大巴代码中大家得以进一步证实早先的眼光,正是ConcurentBag<T>在三个线程中积攒数据时,使用的是双向链表ThreadLocalList落实了黄金年代组对链表增加和删除改查的办法。

ArrayList

底层接纳Object[]数组来贯彻
ArrayList 能够知晓为动态数组,用 MSDN 中的说法,正是 Array 的繁缛版本。与 Java 中的数组相比较,它的容积能动态增进。ArrayList 是 List 接口的可变数组的兑现。实现了装有可选列表操作,并允许包含 null 在内的兼具因素。除了达成 List 接口外,此类还提供部分办法来操作内部用来囤积列表的数组的轻重缓急。(此类大概上同样Vector 类,除了此类是不一致台的。)

3. ConcurrentBag落到实处新增比索素

接下去大家看黄金年代看ConcurentBag<T>是怎样新添成分的。

/// <summary>
/// 尝试获取无主列表,无主列表是指线程已经被暂停或者终止,但是集合中的部分数据还存储在那里
/// 这是避免内存泄漏的方法
/// </summary>
/// <returns></returns>
private ThreadLocalList GetUnownedList()
{
    //此时必须持有全局锁
    Contract.Assert(Monitor.IsEntered(GlobalListsLock));

    // 从头线程列表开始枚举 找到那些已经被关闭的线程
    // 将它所在的列表对象 返回
    ThreadLocalList currentList = m_headList;
    while (currentList != null)
    {
        if (currentList.m_ownerThread.ThreadState == System.Threading.ThreadState.Stopped)
        {
            currentList.m_ownerThread = Thread.CurrentThread; // the caller should acquire a lock to make this line thread safe
            return currentList;
        }
        currentList = currentList.m_nextList;
    }
    return null;
}
/// <summary>
/// 本地帮助方法,通过线程对象检索线程线程本地列表
/// </summary>
/// <param name="forceCreate">如果列表不存在,那么创建新列表</param>
/// <returns>The local list object</returns>
private ThreadLocalList GetThreadList(bool forceCreate)
{
    ThreadLocalList list = m_locals.Value;

    if (list != null)
    {
        return list;
    }
    else if (forceCreate)
    {
        // 获取用于更新操作的 m_tailList 锁
        lock (GlobalListsLock)
        {
            // 如果头列表等于空,那么说明集合中还没有元素
            // 直接创建一个新的
            if (m_headList == null)
            {
                list = new ThreadLocalList(Thread.CurrentThread);
                m_headList = list;
                m_tailList = list;
            }
            else
            {
               // ConcurrentBag内的数据是以双向链表的形式分散存储在各个线程的本地区域中
                // 通过下面这个方法 可以找到那些存储有数据 但是已经被停止的线程
                // 然后将已停止线程的数据 移交到当前线程管理
                list = GetUnownedList();
                // 如果没有 那么就新建一个列表 然后更新尾指针的位置
                if (list == null)
                {
                    list = new ThreadLocalList(Thread.CurrentThread);
                    m_tailList.m_nextList = list;
                    m_tailList = list;
                }
            }
            m_locals.Value = list;
        }
    }
    else
    {
        return null;
    }
    Debug.Assert(list != null);
    return list;
}
/// <summary>
/// Adds an object to the <see cref="ConcurrentBag{T}"/>.
/// </summary>
/// <param name="item">The object to be added to the
/// <see cref="ConcurrentBag{T}"/>. The value can be a null reference
/// (Nothing in Visual Basic) for reference types.</param>
public void Add(T item)
{
    // 获取该线程的本地列表, 如果此线程不存在, 则创建一个新列表 (第一次调用 add)
    ThreadLocalList list = GetThreadList(true);
    // 实际的数据添加操作 在AddInternal中执行
    AddInternal(list, item);
}

/// <summary>
/// </summary>
/// <param name="list"></param>
/// <param name="item"></param>
private void AddInternal(ThreadLocalList list, T item)
{
    bool lockTaken = false;
    try
    {
        #pragma warning disable 0420
        Interlocked.Exchange(ref list.m_currentOp, (int)ListOperation.Add);
        #pragma warning restore 0420
        // 同步案例:
        // 如果列表计数小于两个, 因为是双向链表的关系 为了避免与任何窃取线程发生冲突 必须获取锁
        // 如果设置了 m_needSync, 这意味着有一个线程需要冻结包 也必须获取锁
        if (list.Count < 2 || m_needSync)
        {
            // 将其重置为None 以避免与窃取线程的死锁
            list.m_currentOp = (int)ListOperation.None;
            // 锁定当前对象
            Monitor.Enter(list, ref lockTaken);
        }
        // 调用 ThreadLocalList.Add方法 将数据添加到双向链表中
        // 如果已经锁定 那么说明线程安全  可以更新Count 计数
        list.Add(item, lockTaken);
    }
    finally
    {
        list.m_currentOp = (int)ListOperation.None;
        if (lockTaken)
        {
            Monitor.Exit(list);
        }
    }
}

从地点代码中,大家能够很了解的精通Add()方式是什么样运作的,在这之中的要紧就是GetThreadList()主意,通过该办法能够获得当前线程的数据存款和储蓄列表对象,如若不设有数据存储列表,它会自行创造大概通过GetUnownedList()措施来寻找那多少个被终止但是还蕴藏有数据列表的线程,然后将数据列表再次回到给当下线程中,防止了内部存款和储蓄器泄漏。

在数额拉长的经过中,完结了细颗粒度的lock联手锁,所以品质会异常高。删除和别的操作与新扩展类似,本文不再赘述。

LinkedList

LinkedList 是依靠链表结构完毕,所以在类中富含了 first 和 last 多个指针(Node)。Node 中带有了上二个节点和下八个节点的援引,那样就结成了双向的链表。每一个 Node 只好知道本人的前一个节点和后一个节点,但对此链表来说,这早就足足了。

4. ConcurrentBag 如何兑现迭代器情势

看完上边包车型大巴代码后,小编很奇怪ConcurrentBag<T>是何许兑现IEnumerator来贯彻迭代访谈的,因为ConcurrentBag<T>是透过分散在不一样线程中的ThreadLocalList来存款和储蓄数据的,那么在贯彻迭代器情势时,进程会相比较复杂。

后边再查看了源码之后,开采ConcurrentBag<T>为了促成迭代器形式,将分在分裂线程中的数据全都存到二个List<T>聚拢中,然后重返了该别本的迭代器。所以每一遍访谈迭代器,它都会新建叁个List<T>的别本,那样固然浪费了一定的存放空间,可是逻辑上越来越简约了。

/// <summary>
/// 本地帮助器方法释放所有本地列表锁
/// </summary>
private void ReleaseAllLocks()
{
    // 该方法用于在执行线程同步以后 释放掉所有本地锁
    // 通过遍历每个线程中存储的 ThreadLocalList对象 释放所占用的锁
    ThreadLocalList currentList = m_headList;
    while (currentList != null)
    {

        if (currentList.m_lockTaken)
        {
            currentList.m_lockTaken = false;
            Monitor.Exit(currentList);
        }
        currentList = currentList.m_nextList;
    }
}

/// <summary>
/// 从冻结状态解冻包的本地帮助器方法
/// </summary>
/// <param name="lockTaken">The lock taken result from the Freeze method</param>
private void UnfreezeBag(bool lockTaken)
{
    // 首先释放掉 每个线程中 本地变量的锁
    // 然后释放全局锁
    ReleaseAllLocks();
    m_needSync = false;
    if (lockTaken)
    {
        Monitor.Exit(GlobalListsLock);
    }
}

/// <summary>
/// 本地帮助器函数等待所有未同步的操作
/// </summary>
private void WaitAllOperations()
{
    Contract.Assert(Monitor.IsEntered(GlobalListsLock));

    ThreadLocalList currentList = m_headList;
    // 自旋等待 等待其它操作完成
    while (currentList != null)
    {
        if (currentList.m_currentOp != (int)ListOperation.None)
        {
            SpinWait spinner = new SpinWait();
            // 有其它线程进行操作时,会将cuurentOp 设置成 正在操作的枚举
            while (currentList.m_currentOp != (int)ListOperation.None)
            {
                spinner.SpinOnce();
            }
        }
        currentList = currentList.m_nextList;
    }
}

/// <summary>
/// 本地帮助器方法获取所有本地列表锁
/// </summary>
private void AcquireAllLocks()
{
    Contract.Assert(Monitor.IsEntered(GlobalListsLock));

    bool lockTaken = false;
    ThreadLocalList currentList = m_headList;

    // 遍历每个线程的ThreadLocalList 然后获取对应ThreadLocalList的锁
    while (currentList != null)
    {
        // 尝试/最后 bllock 以避免在获取锁和设置所采取的标志之间的线程港口
        try
        {
            Monitor.Enter(currentList, ref lockTaken);
        }
        finally
        {
            if (lockTaken)
            {
                currentList.m_lockTaken = true;
                lockTaken = false;
            }
        }
        currentList = currentList.m_nextList;
    }
}

/// <summary>
/// Local helper method to freeze all bag operations, it
/// 1- Acquire the global lock to prevent any other thread to freeze the bag, and also new new thread can be added
/// to the dictionary
/// 2- Then Acquire all local lists locks to prevent steal and synchronized operations
/// 3- Wait for all un-synchronized operations to be done
/// </summary>
/// <param name="lockTaken">Retrieve the lock taken result for the global lock, to be passed to Unfreeze method</param>
private void FreezeBag(ref bool lockTaken)
{
    Contract.Assert(!Monitor.IsEntered(GlobalListsLock));

    // 全局锁定可安全地防止多线程调用计数和损坏 m_needSync
    Monitor.Enter(GlobalListsLock, ref lockTaken);

    // 这将强制同步任何将来的添加/执行操作
    m_needSync = true;

    // 获取所有列表的锁
    AcquireAllLocks();

    // 等待所有操作完成
    WaitAllOperations();
}

/// <summary>
/// 本地帮助器函数返回列表中的包项, 这主要由 CopyTo 和 ToArray 使用。
/// 这不是线程安全, 应该被称为冻结/解冻袋块
/// 本方法是私有的 只有使用 Freeze/UnFreeze之后才是安全的 
/// </summary>
/// <returns>List the contains the bag items</returns>
private List<T> ToList()
{
    Contract.Assert(Monitor.IsEntered(GlobalListsLock));
    // 创建一个新的List
    List<T> list = new List<T>();
    ThreadLocalList currentList = m_headList;
    // 遍历每个线程中的ThreadLocalList 将里面的Node的数据 添加到list中
    while (currentList != null)
    {
        Node currentNode = currentList.m_head;
        while (currentNode != null)
        {
            list.Add(currentNode.m_value);
            currentNode = currentNode.m_next;
        }
        currentList = currentList.m_nextList;
    }

    return list;
}

/// <summary>
/// Returns an enumerator that iterates through the <see
/// cref="ConcurrentBag{T}"/>.
/// </summary>
/// <returns>An enumerator for the contents of the <see
/// cref="ConcurrentBag{T}"/>.</returns>
/// <remarks>
/// The enumeration represents a moment-in-time snapshot of the contents
/// of the bag.  It does not reflect any updates to the collection after 
/// <see cref="GetEnumerator"/> was called.  The enumerator is safe to use
/// concurrently with reads from and writes to the bag.
/// </remarks>
public IEnumerator<T> GetEnumerator()
{
    // Short path if the bag is empty
    if (m_headList == null)
        return new List<T>().GetEnumerator(); // empty list

    bool lockTaken = false;
    try
    {
        // 首先冻结整个 ConcurrentBag集合
        FreezeBag(ref lockTaken);
        // 然后ToList 再拿到 List的 IEnumerator
        return ToList().GetEnumerator();
    }
    finally
    {
        UnfreezeBag(lockTaken);
    }
}

由地点的代码可通晓,为了拿走迭代器对象,总共进行了三步关键的操作。

  1. 使用FreezeBag()艺术,冻结后生可畏切ConcurrentBag<T>聚拢。因为需求扭转集结的List<T>别本,生成副本时期不能够有别的线程改动损坏数据。
  2. ConcurrrentBag<T>生成List<T>副本。因为ConcurrentBag<T>积攒数据的主意相比奇特,直接实现迭代器方式困难,思量到线程安全和逻辑,最棒的措施是生成一个别本。
  3. 成就上述操作之后,就足以选择UnfreezeBag()措施解冻整个集结。

那么FreezeBag()方法是怎么来冻结英姿焕发切会集的呢?也是分为三步走。

  1. 率先得到全局锁,通过Monitor.Enter(GlobalListsLock, ref lockTaken);这么一条语句,那样任何线程就不可能冻结集结。
  2. 接下来拿走具有线程中ThreadLocalList的锁,通过`AcquireAllLocks()方法来遍历获取。这样任何线程就不能对它进行操作损坏数据。
  3. 伺机已经进去了操作流程线程甘休,通过WaitAllOperations()艺术来落到实处,该方法会遍历每贰个ThreadLocalList对象的m_currentOp脾性,确定保证全体处在None操作。

达成上述流程后,那么就是真正的结冰了整个ConcurrentBag<T>集结,要解冻的话也类似。在那不再赘言。

ConcurrentHashMap

ConcurrentHashMap 的分子变量中,包涵了三个 Segment 的数组(final Segment<K,V>[] segments;),而 Segment 是 ConcurrentHashMap 的里边类,然后在 Segment 这一个类中,包括了三个 HashEntry 的数组(transient volatile HashEntry<K,V>[] table;)。而 HashEntry 也是 ConcurrentHashMap 的当中类。HashEntry 中,包涵了 key 和 value 以至 next 指针(类似于 HashMap 中 Entry),所以 HashEntry 能够组合四个链表。

故此通俗的讲,ConcurrentHashMap 数据结构为二个 Segment 数组,Segment 的数据结构为 HashEntry 的数组,而 HashEntry 存的是大家的键值对,能够组成链表。

ConcurrentHashMap 的高并发性首要来源于多少个地方:

  • 用分离锁完毕多个线程间的越来越深档期的顺序的分享访谈。
  • 用 HashEntery 对象的不变性来减弱施行读操作的线程在遍历链表时期对加锁的必要。
  • 通过对同一个 Volatile 变量的写 / 读访谈,和谐不一样线程间读 / 写操作的内存可知性。

行使分别锁,减小了必要 同一个锁的效能。

经过 HashEntery 对象的不改变性及对同三个 Volatile 变量的读 / 写来和谐内部存款和储蓄器可以见到性,使得 读操作大好多时候无需加锁就能够学有所成收获到须求的值。由于散列映射表在事实上行使中山大学部操作都是大功告成的 读操作,所以 2 和 3 不只能够削减乞请同一个锁的成效,也足以使得削减少持有股票数量有锁的年月。通过减弱伏乞同四个锁的频率和尽量减少持有锁的时辰,使得 ConcurrentHashMap 的并发性相对于 HashTable 和用意气风发块包装器包装的 HashMap有了质的滋长。

四、总结

上边给出一张图,描述了ConcurrentBag<T>是何许存款和储蓄数据的。通过各样线程中的ThreadLocal来贯彻线程本地存款和储蓄,各类线程中都有那般的结构,互不苦闷。然后每一个线程中的m_headList总是指向ConcurrentBag<T>的第一个列表,m_tailList本着最后叁个列表。列表与列表之间通过m_locals 下的 m_nextList不仅,构成三个单链表。

数量存款和储蓄在种种线程的m_locals中,通过Node类构成四个双向链表。
PS: 要注意m_tailListm_headList并不是储存在ThreadLocal中,而是有着的线程分享后生可畏份。

图片 3

如上便是有关ConcurrentBag<T>类的完成,小编的片段笔录和深入分析。

小编水平有限,如若不当接待各位商酌指正!

附上ConcurrentBag<T>源码地址:戳一戳

本文由澳门至尊网站发布于黑客安全,转载请注明出处:ConcurrentBag的实现原理,Java集合类工作原理及实现

关键词: