使用线程安全的可导航映射表

本节讲述 ConcurrentNavigableMap 接口。实现了此接口的类存储以下2部分元素:

  • key: 元素的唯一标识
  • 其余数据: 定义此元素

每部分在不同的类中实现。

Java API 也 提供了一个实现了此接口的类,就是 ConcurrentSkipListMap,它实现了一个非阻塞列表且拥有 ConcurrentNavigableMap 接口的行为。 在内部,它使用了一个 Skip List来存储数据。Skip List是一个基于并行列表的数据结构,效率类似二叉树。 作为一个排序的数据结构,它的插入、搜索、删除元素的速度比排序列表要快。

Skip List 由 William Pugh 在 1990 年引入

当插入数据到映射表,它使用key来对数据排序,所以所有元素都将被排好序。 除了返回具体的元素,此类也提供了方法来获取映射表的一个子映射表。

任务

使用 ConcurrentSkipListMap 类来实现一个联系人映射表。

实现

本节的示例代码在 com.elanzone.books.noteeg.chpt6.sect06 package中

  • 数据类 : Contact

    • 属性 name : String 对象,联系人姓名
    • 属性 phone : String 对象,联系人电话
    • 在构造函数中将属性值初始化为参数值
    • 提供属性的 getter 方法
        public class Contact {
    
            private String name;
            private String phone;
    
            public Contact(String name, String phone) {
                this.name = name;
                this.phone = phone;
            }
    
            public String getName() {
                return name;
            }
    
            public String getPhone() {
                return phone;
            }
        }
    
  • Runnable 实现类 : Task

    • 属性 map : ConcurrentSkipListMap<String, Contact> 对象 : 映射表
    • 属性 id : String 对象,线程id
    • 在构造函数中将属性值初始化为参数值
            ConcurrentSkipListMap<String, Contact> map;
            private String id;
    
            public Task(ConcurrentSkipListMap<String, Contact> map, String id) {
                this.map = map;
                this.id = id;
            }
    
    • run() 方法 : 使用 put() 方法保存 1000 个不同的联系人到映射表
      • 用 任务id和一个递增的数字来创建联系人对象
      • 任务id + 递增数字作为在映射表中的 key
                for (int i = 0; i < 1000; i++) {
                    Contact contact = new Contact(id, String.valueOf(i + 1000));
                    map.put(id + contact.getPhone(), contact);
                }
    
  • 控制类 : Main

    • 1: 创建一个 ConcurrentSkipListMap<String, Contact> 对象
    • 2: 创建id从A到Y共25个Task对象及对应的线程,并启动线程
    • 3: 等待线程的结束
                ConcurrentSkipListMap<String, Contact> map = new ConcurrentSkipListMap<>();
    
                Thread threads[] = new Thread[25];
                int count = 0;
                for (char i = 'A'; i < 'Z'; i++) {
                    Task task = new Task(map, String.valueOf(i));
                    threads[count] = new Thread(task);
                    threads[count].start();
                    count++;
                }
    
                for (Thread thread : threads) {
                    try {
                        thread.join();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
    
    • 4: 调用 firstEntry() 方法获取并输出映射表的第一个条目
                System.out.printf("Main: Size of the map: %d\n", map.size());
                Map.Entry<String, Contact> element;
                Contact contact;
                element = map.firstEntry();
                contact = element.getValue();
                System.out.printf("Main: First Entry: %s: %s\n", contact.getName(), contact.getPhone());
    
    • 5: 调用 lastEntry() 方法获取并输出映射表的最后一个条目
                element = map.lastEntry();
                contact = element.getValue();
                System.out.printf("Main: Last Entry: %s: %s\n", contact.getName(), contact.getPhone());
    
    • 6: 调用 subMap() 方法获取映射表的一个子集后
    • 7: 调用 pollFirstEntry() 方法从子映射表中逐个获取并移除第一个条目,直到取完(获得的条目为 null)
                System.out.printf("Main: Submap from A1996 to B1002: \n");
                ConcurrentNavigableMap<String, Contact> submap = map.subMap("A1996", "B1002");
                do {
                    element = submap.pollFirstEntry();
                    if (element != null) {
                        contact = element.getValue();
                        System.out.printf("%s: %s\n", contact.getName(), contact.
                                getPhone());
                    }
                } while (element != null);
    

讲解

本例实现了一个 Task 类来存储 Contact 对象到可导航映射表。 每个联系人的名称是创建它的任务的Id和电话号码(从1000到2000的数字)。两者拼在一起组成了联系人在映射表中的 key 。 每个任务创建 1000 个联系人并用 put() 方法保存到可导航映射表。

如果您插入一个key已经在映射表中存在的元素,此key对应的元素将被新插入的元素代替。

Main 类的 main() 方法创建 25 个 Task 对象,使用字母 A 到 Z 作为ID。然后使用了某些方法从映射表中获取数据。

  • firstEntry() 方法用一个 Map.Entry 对象返回映射表中的第一个元素。此方法不从映射表中移除元素。
    • Map.Entry 对象包含 key 和 元素。
      • 调用 getValue() 方法获得元素
      • 调用 getKey() 方法获得元素的 key
  • lastEntry() 方法用一个 Map.Entry 对象返回映射表的最后一个元素
  • subMap() 方法用一个 ConcurrentNavigableMap 返回映射表中的部分元素(本例中返回 key 从 A1996 到 B1002 的元素)
  • pollFirst() 方法返回并移除映射表中的第一个 Map.Entry 对象

了解更多

ConcurrentSkipListMap 类还有一些其他的方法:

  • headMap(K toKey):返回映射表中从第一个元素到 key 值小于参数 toKey 值的所有元素的子映射表。
    • K 是 ConcurrentSkipListMap 对象的泛型参数中的key参数的值。
  • tailMap(K fromKey): 返回映射表中 key值大于参数 fromKey 值的所有元素到最后一个元素的子映射表。
  • putIfAbsent(K key, V Value): 如果参数 key 指定的值在映射表中不存在,则将 key 和 value 插入到映射表。
  • pollLastEntry(): 返回并移除映射表的最后一个元素(Map.Entry 对象)
  • replace(K key, V Value): 如果 key 对应的元素在映射表中存在,则以 value 替换掉它的值