2019-7-19

部分常用容器类

HashMap

底层数据结构，数组 + 链表/红黑树
链表类 - Node - 单链表

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

红黑树类 - TreeNode

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
}

HashTable

线程安全，数据强一致，size isEmpty contains get put ... 等方法使用synchronized修饰。
线程安全带来的代价是性能较差。

ConcurrentHashMap

线程安全，数据弱一致(get请求是无锁的，所以在get请求时可能会读取到老数据，不能保证每次读取都是最新数据)。
TreeNode，与HashMap中TreeNode相同。
put方法会使用synchronized对操作对象加锁。

ConcurrentSkipListMap

线程安全，数据弱一致。
跳表，redis中map就是通过跳表实现的，跳表相比红黑树，优点是查询速度稳定，不会因为红黑树的再平衡而长时间等待。
相比ConcurrentHashMap，更加适用于大数据量场景。