前言
本文主要内容：
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
网友评论