非线程安全
1.hashmap
- 根据hashcode存储数据，容易直接定位到它的值。遍历顺序不确定。
jdk7数组+链表
一个数据，数组中每个元素是一个单向链表。每个实体是嵌套类entry实例（四个属性：key, value, hash值，单向链表的next）。
- capacity: 当前数据容量，扩容数组大小为当前2倍。
- loadfactor：负载因子，默认0.75。就是到这个比例就扩容。
- threshold：扩容的阈值。
jdk8数组+链表/红黑树
元素大于8，链表转换为红黑树
链表最差的时间复杂度为o(n)。红黑树时间复杂度度降低到o(logN)。
2.treemap可排序
- 实现 SortedMap 接口
- 用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。（实现 Comparable 接口）
3.linkedhashmap（记录插入顺序）
可实现redis lru（latest recently use）算法
线程安全
1.concurrentHashMap[segment数组]
Segment(段，继承reentrantlock，jdk7)
整个 ConcurrentHashMap 由一个个 Segment 组成，Segment 代表”部分“或”一段“的意思，所以很多地方都会将其描述为分段锁。
ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。
并行度(多少个segment并发操作，默认16)
理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。
2.ConcurrentSkipListMap跳表有序（jdk6）
和TreeMap效率相差不大。
Skip list的性质
(1) 由很多层结构组成，level是通过一定的概率随机产生的。
(2) 每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序，具体取决于使用的构造方法。
(3) 最底层(Level 1)的链表包含所有元素。
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
ConcurrentSkipListMap优点：
1、ConcurrentSkipListMap 的key是有序的。
2、ConcurrentSkipListMap 支持更高的并发。ConcurrentSkipListMap 的存取时间是log（N），和线程数几乎无关。也就是说在数据量一定的情况下，并发的线程越多，ConcurrentSkipListMap越能体现出他的优势。
3.hashtable(全局锁，只有一个线程并发)
任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap，因为 ConcurrentHashMap 引入了分段锁。
4.SynchronizedMap(效率和hashtable差不多)
这个同步方式实现也比较简单，看出SynchronizedMap的实现方式是加了个对象锁，每次对HashMap的操作都要先获取这个mutex的对象锁才能进入，所以性能也不会比HashTable好到哪里去，也不建议使用。