005-多线程-集合-Map-ConcurrentSkipListMap

一、概述

  ConcurrentSkipListMap是线程安全的有序的哈希表,适用于高并发的场景。

  ConcurrentSkipListMap和TreeMap,它们虽然都是有序的哈希表。但是,第一,它们的线程安全机制不同,TreeMap是非线程安全的,而ConcurrentSkipListMap是线程安全的。第二,ConcurrentSkipListMap是通过跳表实现的,而TreeMap是通过红黑树实现的。

  关于跳表(Skip List),它是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。 

1.1、原理和数据结构

    005-多线程-集合-Map-ConcurrentSkipListMap

  说明

  先以数据“7,14,21,32,37,71,85”序列为例,来对跳表进行简单说明。

  跳表分为许多层(level),每一层都可以看作是数据的索引,这些索引的意义就是加快跳表查找数据速度。每一层的数据都是有序的,上一层数据是下一层数据的子集,并且第一层(level 1)包含了全部的数据;层次越高,跳跃性越大,包含的数据越少。
  跳表包含一个表头,它查找数据时,是从上往下,从左往右进行查找。现在“需要找出值为32的节点”为例,来对比说明跳表和普遍的链表。

  情况1:链表中查找“32”节点
  路径如下图1-02所示:

    005-多线程-集合-Map-ConcurrentSkipListMap

  需要4步(红色部分表示路径)。

  情况2:跳表中查找“32”节点
  路径如下图1-03所示:

    005-多线程-集合-Map-ConcurrentSkipListMap

  忽略索引垂直线路上路径的情况下,只需要2步(红色部分表示路径)。


  下面说说Java中ConcurrentSkipListMap的数据结构。
    (01) ConcurrentSkipListMap继承于AbstractMap类,也就意味着它是一个哈希表。
    (02) Index是ConcurrentSkipListMap的内部类,它与“跳表中的索引相对应”。HeadIndex继承于Index,ConcurrentSkipListMap中含有一个HeadIndex的对象head,head是“跳表的表头”。
    (03) Index是跳表中的索引,它包含“右索引的指针(right)”,“下索引的指针(down)”和“哈希表节点node”。node是Node的对象,Node也是ConcurrentSkipListMap中的内部类。

1.2、示例

/*
 *   ConcurrentSkipListMap是“线程安全”的哈希表,而TreeMap是非线程安全的。
 *
 *   下面是“多个线程同时操作并且遍历map”的示例
 *   (01) 当map是ConcurrentSkipListMap对象时,程序能正常运行。
 *   (02) 当map是TreeMap对象时,程序会产生ConcurrentModificationException异常。
 */
public class ConcurrentSkipListMapDemo1 {

    // TODO: map是TreeMap对象时,程序会出错。
    //private static Map<String, String> map = new TreeMap<String, String>();
    private static Map<String, String> map = new ConcurrentSkipListMap<String, String>();

    public static void main(String[] args) {

        // 同时启动两个线程对map进行操作!
        new MyThread("a").start();
        new MyThread("b").start();
    }

    private static void printAll() {
        String key, value;
        Iterator iter = map.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            key = (String) entry.getKey();
            value = (String) entry.getValue();
            System.out.print("(" + key + ", " + value + "), ");
        }
        System.out.println();
    }

    private static class MyThread extends Thread {
        MyThread(String name) {
            super(name);
        }

        @Override
        public void run() {
            int i = 0;
            while (i++ < 6) {
                // “线程名” + "序号"
                String val = Thread.currentThread().getName() + i;
                map.put(val, "0");
                // 通过“Iterator”遍历map。
                printAll();
            }
        }
    }
}

 

1.3、使用场景

二、源码分析

 

上一篇:java – 使TreeMap Comparator容忍null


下一篇:java集合学习(2):Map和HashMap