java之Map

前言

本文主要内容：

    1、HashMap简介

    2、ConcurrentHashMap简介

    3、treeMap简介

---

1、HashMap(数组+单向链表+红黑树)

      类图：

     通过类图我们看到HashMap继承了AbstractMap和实现了Serializable(序列化)，Cloneable(),Map

     HashMap里面是一个数组。每一个元素是一个单向链表，每一个Key所处的位置都是通过Key的hashCode（Entry）值进行决定，HashMap中允许存在Key为null，Value为null的数据存在，但是最多允许一条记录的key为null。

     HashMap是非线程安全的，即可以允许多线程访问修改。HashMap结构图:

     从结构图上看，HashMap是存储在一整块磁盘中（数组），当Key的hashCode（Entry）产生冲突时，则当前Key会通过单向链表来存储对应的值。

     查找：Key先进行hashCode(Entry)，找到对应的Entry的位置，然后进行Key值比较，如果是则拿出Value值，如果不是则通过链表找到下一个Entry，然后再进行Key比较，直到拿到对应数据。

     HashMap默认的初始化长度为16，每一次扩容是2的幂，由于每一次的扩容，HashMap需要将数据拷贝至新的存储区域，因此当插入数据超过HashMap定义的大小时，HashMap的速度就会很慢，因此，在初始化时最好能够预估HashMap的大小。

     HashMap会在什么时候会进行扩容呢？HashMap中定义一个阈值（threshold），当HashMap的长度超过阈值时则进行扩容。阈值的计算是通过负载因子（loadFactor）与当前数组容量（capacity）决定，即：threshold = loadFactor * capacity，其中负载因子（loadFactor）默认为0.75。

     由于HashMap查找对应值是需要找到Entry，然后顺着链表进行查找。因此时间复杂度取决于链表长度，时间复杂度O(n)，因此，java8后引入了红黑树，当链表长度超过8以后，链表就转为红黑树进行查询。时间复杂度（O(logN)）。

2、ConcurrentHashMap

      类图：

      从类图上看跟HashMap差不多

      支持并发操作，由一个个Segment组成，而Segment又可以称为：分段锁，槽

      ConcurentHashMap是线程安全的，通过继承ReentrantLock来进行加锁，每次需要加锁锁住的是一个segment，保证每个segment的线程安全，也就实现了全局的线程安全。结构图：

     从结构图中可以看出，ConcurentHashMap默认的并行度（concurrencyLevel）默认为16，也就是说有16个Segments,理论上说最多同时支持16个线程并发写，并行度一旦初始化后就不可以在扩容了。

3、TreeMap

      实现SortedMap接口，把保存的记录根据键排序，默认按键值升序排列。在使用TreeMap时，key必须实现Comparable接口或构造TreeMap传入自定义Comparator，否则运行时抛出ClassCastException