Concurrent包之ConcurrentMap(并发映射)

 /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * The value should be at least 4 * TREEIFY_THRESHOLD to avoid
     * conflicts between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = ;
当桶的容量大于是，链表的长度超过阈值将会自动转化为红黑树

红黑二叉树
	红黑二叉树本质上是一个自平衡二叉查找树
	二叉查找树特点：左小于根，右大于根
	红黑树的特点:父子节点都为红
		i.所有的节点非红即黑
		ii.根节点必须为黑节点
		iii.红节点的子节点必须为黑节点，反之不成立
		iv.从根节点出发相同高度的黑节点总是一致
		v.所有的根节点都为黑色的空节点
		vi.新添加的节点必须为红色
	红黑树修正方案：
		i.叔父节点为红，将父节点以及叔父节点涂黑，祖父节点涂红.
		ii.叔父节点为黑，当前节点为父节点的右子叶，以当前节点为轴进行左旋（与当前节点有关的节点以当前节点为轴逆时针旋转°，并保持左右子树不变）
		iii.叔父节点为黑，当前节点为父节点的左子叶，以当前节点为轴进行右旋旋（与当前节点有关的节点以当前节点为轴顺时针旋转°，并保持左右子树不变）
		iv。红黑树修正过程是链式反应过程
	红黑树的时间复杂度:O(logn)

package com.jmy.ConcurrentMap;

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapDemo {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap();

        // 添加元素
        map.put("a",);
        map.put("b",);
        map.put("c",);

        // 获取所有的key
        System.out.println(map.keySet());
        // 使用key查找value
        System.out.println(map.get("a"));
        // 转化为键值对的集合
        System.out.println(map.entrySet());

    }
}

     */
    public ConcurrentSkipListMap() {
        this.comparator = null;
        initialize();
    }
 /**
     * Initializes or resets state. Needed by constructors, clone,
     * clear, readObject. and ConcurrentSkipListSet.clone.
     * (Note that comparator must be separately initialized.)
     */
    private void initialize() {
        keySet = null;
        entrySet = null;
        values = null;
        descendingMap = null;
        head = new HeadIndex<K,V>(new Node<K,V>(key:null, BASE_HEADER,next:null),
                                  down:null, right:null, level:);
    }

 /** Lazily initialized key set */
    private transient KeySet<K> keySet;
    /** Lazily initialized entry set */
    private transient EntrySet<K,V> entrySet;
    /** Lazily initialized values collection */
    private transient Values<V> values;
    /** Lazily initialized descending key set */
    private transient ConcurrentNavigableMap<K,V> descendingMap;

a.底层是基于跳跃表实现的
b.跳跃表:
	i.元素是有序的
	ii.实际过程中，跳跃表是多层的，最上层的元素至少是两个
	iii.跳跃表是典型的以空间换取时间的产物
	iv.查询的时间复杂度为O(logn)
	v.适用于查询多，而增删少的场景
	vi.在跳跃表中添加元素，新添的元素是否提取到上层的跳跃表中遵循"抛硬币"的原则(自定义算法)

package com.jmy.ConcurrentMap;

import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;

public class ConcurrentSkipListMapDemo {
    public static void main(String[] args) {
        // ConcurrentNavigableMap是一个接口，所以使用的更多的是它的实现类
        ConcurrentNavigableMap<String, Integer> map = new ConcurrentSkipListMap<>();

        // 添加元素
        map.put("d", );
        map.put("e", );
        map.put("w", );
        map.put("a", );
        map.put("h", );
        map.put("y", );
        map.put("u", );

        // 提供了用于截取子映射的方法
        // 从头开始截取到指定元素
        System.out.println(map.headMap("h"));
        // 从指定元素开始截取到尾
        System.out.println(map.tailMap("h"));
        // 从指定元素截取到指定元素
        System.out.println(map.subMap("a", "h"));
    }
}