HashMap() 1.结构:A.基于AbstracMap类、哈希表Map接口 B.”链表散列”的数据结构，数组和链表结合体 C.JDK1.8增加红黑树部分，复杂度从O(n)降到O(logn)，链表长度超过8，转为红黑树 2.键和值特点:A.允许出现null值和null键(最多只允许一条记录的键为null，允许多条记录的值为null) B.此类不保证映射顺序，即为无序储存C.不允许出现重复的键(key) 3.特点:A.非线程安全 B.迭代器为fail-fast 4.数据储存:A.根据key的hashCode()方法获取hash值，算出元素在数组下标，若已有元素则以链表形式存放(新加的放在链尾JDK1.8)，若无元素则放在数组中该位置(put()方法) B.若key相同hash值也相同(equal()判断hash值)，则会覆盖数据(HashSet中若key相同不覆盖) 5.数据读取:根据hash值找到数组中对应位置，用key.equal()在对应位置链表中找到值 6.容量:A.默认初始容量16，默认初始负载因子0.75，当数据量=容量*负载因子时，会扩容B.非默认构造方法: HashMap(int initialCapacity, float loadFactor), HashMap(int initialCapacity) 7.Entry类型包含元素(相当于单向列表):A.key值 B.value值 C.Entry<k,v> next D.hash值 8.归纳:HashMap在底层将键-值当作一个整体(Entry数组)处理，存储取出都对Entry[]操作
HashSet 1.特点:A结构:其基于HashMap实现，底层采用HashMap保存元素。HashSet同时实现Set接口，只使用HashMap的Key实现各种特性 B.HashSet比HashMap慢 C.迭代器为fail-fast 2.存储数据:A.不储存key-value键值对，只将value作为key存入HashMap，而对应value值的为new Object()对象 B.hash值由value充当key来计算获得，equal()方法判断对象相等性 C.添加元素e，若set没包含则添加e(用add()方法)，若已包含则不更改set并返回false(Set中元素不重复特性)
HashTable 1.结构:A.散列表(通过拉链法实现的哈希表)，储存键值对，基于Dictionary类 B.key和value都不能为null，遇到null直接返回nullpointerException(和HashMap不同) 2.成员变量:A.table:一个Entry的数组 B.count:HashTable键值对数量 C.threshold:HashTable阀值，threshold=容量*加载因子，超过则调整容量 D.loadFactor:加载因子 E.modCount:实现fail-fast机制，防止在读取过程有更新操作(若有更新，读取会报错) 3.特点:A.线程安全，几乎所有public方法都是Sychronized的 B.速度慢 4.构造函数: A.public HashTable()：默认构造函数，容量为11，加载因子为0.75 B. public HashTable(Map<? extends K, ? extends V> t)：构造与给定的 Map 有相同映射关系的新哈希表 C. HashTable(int initialCapacity, float loadFactor) D.HashTable(int initialCapacity) 5.储存数据过程(put()方法):A.首先判value是否为空，为空抛出异常 B.计算key的Hash值，根据hash值获得key在数据table中位置index C.若table[index]不为空，则迭代，若有相同key则替换，并返回旧value，否则直接插入到table[index] 6.数据获取过程(用get()方法):通过key.hash()求hash值，并找到index索引，迭代列表，返回匹配key的value，找不到则返回null
LinkedHashMap 1.概念:HashMap的子类，能实现有序HashMap，将插入顺序或访问顺序作为迭代顺序，所以不保证映射顺序永远不变 2.结构:A.其本身由Map接口的哈希列表和链表实现，即数组+链表 B.重写HashMap的Entry类，将HashMap数据组成一个双向列表 C.允许null值和null键 D.非线程安全 3.成员变量:A采用的hash算法和Map相同 B.重新定义了Entry元素，保存当前变量外，增加了before和after指针，在哈希表基础上构建双向链表 4.构造方法(public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder)):A.基本容量 B.负载因子 C.accessOrder参数:默认false代表按照插入顺序迭代，设置为true则按访问顺序(调用get方法的顺序，调用get后元素移至链表尾部，不断访问不断移动) 5.对Entry元素初始化操作:A.header=new Entry<>(-1,null,null,null) B.header.before= header. after = header 6.数据储存: A.未重写父类HashMap的put方法(相同hash值且相同key值，会覆盖) 重写put的子方法 B. void recordAccess(HashMap m) { //e.recordAccess(this);覆盖值时调用 LinkedHashMap<k,v> lm=(LinkedHashMap<k,v>)m; If(lm.accessOrder==true){ Im.modCount++; Remove(); addBefore(lm.header);} } C.void addEntry(int hash, K key, V value, int bucketIndex) { //bucketIndex碰撞索引 createEntry(hash，key，value，bucketIndex) //新元素以双向链表的形式加入到映射中 Entry<K,V> eldest = header.after; //删除最近最少使用元素的策略定义 if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } else { if (size >= threshold) resize(2 * table.length); } } D.void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; //新元素插在链表尾部 Entry<K,V> e = new Entry<K,V>(hash, key, value, old); //插入头还是尾只和HashMap有关 table[bucketIndex] = e; // 调用元素addBrefore方法，将元素加入哈希、双向链接列表。 e.addBefore(header); size++; } E.addBefore(Entry<K,V> existingEntry) {//提供了自己特有的双向链接列表的实现 after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; } 7.数据读取:重写父类HashMap()的get方法，实际调用父类getEntry()方法获取元素。若AccessOrder为true，则记录访问顺序，将最新访问记录到链表不表头 8.数据删除private void remove() { before.after = after; after.before = before; }
TreeMap 1.结构:A.有序key-value集合，基于红黑树实现B.继承于AbstractMap C.实现NavigableMap接口:实现一系列导航方法，比如返回有序key集合 D.实现cloneable接口，能被克隆 2.排序方式:该映射根据其键的自然顺序(字母顺序)进行排序，或者创建时提供的Comparator进行排序，取决于使用的构造方法 3.基本操作:containsKey，get，put，remove，时间复杂度为logn 4.特点:A.非线程安全的 B.interator方法迭代器是fail-fast
ConcurrentHashMap 1.设计目的:A.解决HashMap非线程安全 B.有弱一致性:get和containsKey可能返回过时数据 2.设计思路:HashMap基础上做改动，采用分段锁的设计，只有才同一个分段内才有竞争关系，不同分段锁间没有锁竞争 3.分段锁(Segment):A结构:类似于HashMap，内含一个Entry数组，数组中每个元素又是一个链表 B.Segment继承了ReentrantLock 4.HashEntry和Entry差别:其value，next变量都被volatile修饰，多线程读写保持可见性 5.并发度概念:不产生锁竞争的最大线程数，即分段锁个数，Segment[]数组长度 6.并发度值:A.默认为16 B.在构造函数设置并发度时，concurrentHashMap会使用大于等于该值的最小2次幂整数作为实际并发度 C. 运行时通过将key的高n位（n = 32 – segmentShift）和并发度减1（segmentMask）做位与运算定位到所在的Segment。segmentShift与segmentMask都是在构造过程中根据concurrency level被相应的计算出来 D.并发度过小，会导致锁竞争。过大会导致位于同一Segment访问扩散到不同Segment 7.创建分段锁(JDK7):A.除第一个segment，剩余segment采用延迟初始化机制。所以每次put前都需检测对应segment是否为null，若是则调用ensureSegment()保证segment已被创建 B.ensureSegment可在并发情况调用，但未使用锁，而是不安全对象getObjectVolitail()提供的原子读语义结合CAS(比较并替换)来确保Segment创建的原子性 8.储存过程: A.获取segment锁过程:put方法通过tryLock()获取锁，在此过程中对hashcode链表遍历，遍历完仍找不到与key相同HashEntry节点，则为后续put提前创建一个HashEntry，当tryLock一定次数仍无法获得，通过Lock申请锁 B.若头结点变化(put，rehash，remove操作)，将重新对表遍历，其他节点变化不影响遍历 C.遍历目的:希望遍历的链表被CPU cache缓存，为后续put操作提升性能 D.获得锁之后，Segment对链表遍历，若某个HashEntry节点有相同的key，则更新该HashEntry的value值，否则新建一个HashEntry节点，将它设置为链表的新head节点并将原头节点设为新head下一个节点。新建过程中若节点总数（含新建HashEntry）超过threshold，则调用rehash()方法对Segment进行扩容，最后将新建HashEntry写入到数组中 E.put()方法中，链接新节点的下一个节点(HashEntry.setNext())以及将链表写入到数组中(setEntryAt())都是通过不安全的putOrderedObject()方法实现，并未使用具有原子写语义的putObjectVolatile()的原因是：JMM会保证获得锁到释放锁之间所有对象的状态更新都会在锁被释放之后更新到主存，从而保证这些变更对其他线程是可见的 9.删除数据: 和put类似，remove在获得锁前，也对链表进行遍历以提高缓存命中率 10.获取数据: get()与containsKey()一致：都未使用锁，而通过不安全对象getObjectVolatile()方法提供的原子读语义，来获得Segment以及对应的链表，然后对链表遍历判断是否存在key相同的节点以及获得该节点的value。但由于遍历过程中其他线程可能对链表结构做了调整，因此get和containsKey返回的可能是过时的数据，这一点是ConcurrentHashMap在弱一致性上的体现。如果要求强一致性，那么必须使用Collections.synchronizedMap()方法。
