HashMap
HashMap使用hash数组+单链表实现，数组中的每个元素都是链表，由Node内部类实现，当链表长度超过8时，转化为红黑树。
HashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素；除该类未实现同步外，其余跟Hashtable大致相同；
跟TreeMap不同，该容器不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个HashMap的顺序可能会不同。
根据对冲突的处理方式不同(解决哈希冲突的方式)，哈希表有两种实现方式，一种开放定址法(Open addressing)，另一种是拉链冲突法(Separate chaining with linked lists)。
1.调用hash方法计算K的Hash值，结合数组长度，计算得到数组下标。
2.顺序遍历链表，equals()方法查找相同Node链表中的K值对应的V值。
hashCode是定位的，存储位置，equals是定性的，比较两者是否相等。
- 多线程put操作后,get操作导致死循环
- 多线程put非null元素后,get操作得到null值
-
多线程put操作,导致袁术丢失
-
HashMap是采用链表解决Hash冲突,因为是链表结构,那么就很容易形成闭合的链路,这样在循环的时候只要有线程对这个HashMap进行get操作就会产生死循环。
- 在单线程情况下,只有一个线程对HashMap的数据结构进行操作,是不可能产生闭合的回路的。
- 那就只有在多线程并发的情况下才会出现这种情况,那就是在put操作的时候,如果size > initialCapacity * loadfactory,那么这时候HashMap就会进行rehash操作,随之HashMap的结构就会发生翻天覆地的变化。
很有可能就是两个线程在这个时候同时触发了rehash操作，产生了闭合的回路(环形链表)。
TreeMap
基于红黑树实现
TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。
HashTable
和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。
现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap。
使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用(LRU)顺序。
ConcurrentHashMap
为什么HashTable慢
Hashtable之所以效率低下主要是因为其实现使用了synchronized关键字对put等操作进行加锁，而synchronized关键字加锁是对整个对象进行加锁，也就是说在进行put等修改Hash表的操作时，锁住了整个Hash表，从而使得其表现的效率低下。
在JDK1.5~1.7版本，Java使用了分段锁机制实现ConcurrentHashMap.
简而言之，ConcurrentHashMap在对象中保存了一个Segment数组，即将整个Hash表划分为多个分段；而每个Segment元素，即每个分段则类似于一个Hashtable；
这样，在执行put操作时首先根据hash算法定位到元素属于哪个Segment，然后对该Segment加锁即可。
因此，ConcurrentHashMap在多线程并发编程中可是实现多线程put操作。
核心参数 concurrencyLevel:
并行级别、并发数、Segment 数，怎么翻译不重要，理解它。默认是 16，也就是说 ConcurrentHashMap 有 16 个 Segments，所以理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。
这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。
在JDK1.7之前，ConcurrentHashMap是通过分段锁机制来实现的，所以其最大并发度受Segment的个数限制。
因此，在JDK1.8中，ConcurrentHashMap的实现原理摒弃了这种设计，而是选择了与HashMap类似的数组+链表+红黑树的方式实现，而加锁则采用CAS和synchronized实现。
WeakHashMap，从名字可以看出它是某种 Map。它的特殊之处在于 WeakHashMap 里的entry可能会被GC自动删除，即使程序员没有调用remove()或者clear()方法。
更直观的说，当使用 WeakHashMap 时，即使没有显示的添加或删除任何元素，也可能发生如下情况:
- 调用两次size()方法返回不同的值；
- 两次调用isEmpty()方法，第一次返回false，第二次返回true；
- 两次调用containsKey()方法，第一次返回true，第二次返回false，尽管两次使用的是同一个key；
- 两次调用get()方法，第一次返回一个value，第二次返回null，尽管两次使用的是同一个对象。
WeakHashMap 的这个特点特别适用于需要缓存的场景。
在缓存场景下，由于内存是有限的，不能缓存所有对象；对象缓存命中可以提高系统效率，但缓存MISS也不会造成错误，因为可以通过计算重新得到。
要明白 WeakHashMap 的工作原理，还需要引入一个概念 : 弱引用(WeakReference)。我们都知道Java中内存是通过GC自动管理的，GC会在程序运行过程中自动判断哪些对象是可以被回收的，并在合适的时机进行内存释放。
GC判断某个对象是否可被回收的依据是，是否有有效的引用指向该对象。如果没有有效引用指向该对象(基本意味着不存在访问该对象的方式)，那么该对象就是可回收的。这里的有效引用 并不包括弱引用。
也就是说，虽然弱引用可以用来访问对象，但进行垃圾回收时弱引用并不会被考虑在内，仅有弱引用指向的对象仍然会被GC回收。
WeakHashMap 内部是通过弱引用来管理entry的，弱引用的特性对应到 WeakHashMap 上意味着什么呢？
将一对key, value放入到 WeakHashMap 里并不能避免该key值被GC回收，除非在 WeakHashMap 之外还有对该key的强引用。
Original: https://www.cnblogs.com/winter0730/p/15329690.html
Author: cos晓风残月
Title: Java基础六—Java集合框架Map
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/576248/
转载文章受原作者版权保护。转载请注明原作者出处！