ImmutableMap最多5个 map可以存放多少条数据

一、HashMap （数组+ 链表+ 红黑树） HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。我们用下面这张图来介绍HashMap 的结构。

一、HashMap （数组+ 链表+ 红黑树）一、HashMap （数组+ 链表+ 红黑树）

HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。我们用下面这张图来介绍HashMap 的结构。

大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。上图中，每个绿色的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

• capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍；
• loadFactor：负载因子，默认为 0.75；
• threshold：扩容的阈值，等于 capacity * loadFactor；

java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。

根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后（并且hashMap元素总数要超过64个），会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

线程不安全：扩容（jdk 1.7，死循环）、插入新值（jdk 1.7.8都存在问题，覆盖）、更新size值的时候；

JDK 8 的主要优化：

1. 数组+链表改成了数组+链表或红黑树；
2. 链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后；
3. 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
4. 在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；

二、ConcurrentHashMap

1、Segment 段

ConcurrentHashMap 和 HashMap 思路是差不多的，但是因为它支持并发操作，所以要复杂一些。整个 ConcurrentHashMap 由一个个 Segment 组成，Segment 代表”部分“或”一段“的意思，所以很多地方都会将其描述为分段锁。注意，我很多地方用了“槽”来代表一个segment。

2、线程安全（Segment 继承 ReentrantLock 加锁 ）

简单理解就是，ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。

3、并行度

concurrencyLevel：并行级别、并发数、Segment 数。默认是 16，也就是说 ConcurrentHashMap 有 16 个 Segments，所以理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。再具体到每个 Segment 内部，其实每个 Segment 很像之前介绍的 HashMap，不过它要保证线程安全，所以处理起来要麻烦些。

4、Java8 实现 （引入了红黑树）

Java8 对 ConcurrentHashMap 进行了比较大的改动,Java8 也引入了红黑树。

jdk 1.7 jdk 1.8对于 ConcurrentHashMap的不同：

1. 在JDK 1.7中，put操作给链表插入元素是头插，而在JDK 1.8中是尾插；
2. 在JDK 1.7中，它是通过Segment数组分段锁住数据的，一个Segment实例下面有一个HashEntry数组，put或者remove操作的时候就锁住这个实例下面的HashEntry数组；而在JDK 1.8中，因为是尾插的，所以put、remove等操作都会经过链表第一个节点，第一个节点就是一个关口，JDK 1.8锁的就是这个关口（通过Synchronized上锁）；
3. 在JDK 1.7中，数据结构是数组+数组+链表，而在JDK 1.8中是数组+链表+红黑树；

jdk1.8:

• 使用无锁操作 CAS 插入头结点，失败则循环重试；
• 若头结点已经存在，则尝试获取头结点的同步锁，再进行操作；
• 会帮助扩容；

ConcurrentHashMap的高并发性主要来自于三个方面：

1. 用分离锁(Segment锁)实现多个线程间的更深层次的共享访问;
2. 用 HashEntery 对象的不变性来降低执行读操作的线程在遍历链表期间对加锁的需求;
3. 通过对同一个 Volatile 变量的写 / 读访问，协调不同线程间读 / 写操作的内存可见性;

三、HashTable （线程安全）

Hashtable 是遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary 类，并且是线程安全的，任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap，因为ConcurrentHashMap 引入了分段锁。Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。

四、LinkHashMap（记录插入顺序）

LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。true：访问有序 false：插入有序 默认：false插入有序

五、TreeMap （可排序）

TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。

如果使用排序的映射，建议使用 TreeMap。

在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的Comparator，否则会在运行时抛出 java.lang.ClassCastException 类型的异常。