HashMap

  TreeMap是SortedMap接口的实现类，TreeMap底层是红黑树数据结构，每个key-value作为红黑树的一个节点。TreeMap存储节点时，根据key对节点进行排序，主要是自然排序和自定义排序。类似于TreeSet。

  WeakHashMap用法基本和HashMap类似，不同的是WeakHashMap是对实际对象的弱引用，弱引用就是当WeakHashMap的key所引用的对象没有被其他强引用变量进行引用时，key所对应的对象就可能会被垃圾回收，WeakHashMap会自动删除该key所对应的key-value对。而HashMap的key是保留实际对象的强引用，强引用就是当HashMap对象不被销毁的时候，HashMap所有key所引用的对象就不会被垃圾回收。

  IdentityHashMap也基本类似于HashMap，有一些特殊的地方在于：判断两个key相等。HashMap中判断key相等只需要判断两个key通过equals()方法比较返回true，而IdentityHashMap是仅当两个key通过(key1==key2)相等时才认为相等。IdentityHashMap同样支持null作为key和value。

  EnumMap是Map的枚举实现类，所有key都必须是单个枚举类的枚举值。创建EnumMap的时候必须显式或者隐式指定对应的枚举类。
  EnumMap在内部是以数组的形式保存元素，根据key的自然顺序，即枚举值在枚举类中定义的顺序来保存key-value对的顺序。EnumMap不允许null作为key，但是可以使用null作为value。

  当HashMap内的元素对象存储的爆满时，就容易出现hash冲突的现象，这个时候就需要底层数组扩容。当然，HashMap这种扩容的操作也是比较消耗性能的，因为这需要原数组中的数据重新计算其在新数组中的位置。
  扩容的时机是什么？当HashMap中的元素个数超过数组大小时（即负载因子loadFactor），HashMap底层就会进行数组的扩容，loadFactor的默认值为0.75，这是一个折中的取值。数组大小默认为16，当HashMap中元素对象个数超过16*0.75=12时，就把数组的大小扩容到2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，因此实际使用的时候，若已知晓HashMap大概需要存储多少元素时，则预设元素的个数就可以提高HashMap的性能。
折中：负载因子loadFactor衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表空间利用率高。查找一个元素的平均时间为o(1+a)，当负载因子变大的时候，空间利用率高了，但是查询效率降低；当负载因子变小的时候，元素就会稀疏，但是查询效率高，所以要折中时间和空间。

1. 开放定址法：线性探测再散列、二次探测再散列、随机探测再散列；
2. 再哈希法：换一种哈希函数；
3. 链地址法：在数组中冲突元素后面拉一条链路，存储重复的元素；
4. 建立一个公共溢出区：其实就是建立一个表，存放那些冲突的元素。

HashMap中什么时候会产生冲突？
HashMap中调用hashCode()方法来计算hashCode。由于在Java中两个不同的对象可能有一样的hashCode,所以不同的键可能有一样hashCode，从而导致冲突的产生。

1. 在Java8之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。为了解决在频繁冲突时Hashmap性能降低的问题，Java 8中使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。
2. 在Java 8中使用常量TREEIFY_THRESHOLD来控制是否切换到平衡树来存储。目前，这个常量值是8，这意味着当有超过8个元素的索引一样时，HashMap会使用树来存储它们。
3. 在Java 7中为了优化常用类对ArrayList和HashMap采用了延迟加载的机制，在有元素加入之前不会分配内存，这会减少空的链表和HashMap占用的内存。
4. 这种动态解决hash冲突的特性使得HashMap一开始使用链表，并在冲突的元素数量超过指定值时用平衡二叉树替换链表。这一特性在所有基于hash table的类中没有，例如Hashtable和WeakHashMap。只有ConcurrentHashMap,LinkedHashMap和HashMap会在频繁冲突的情况下使用平衡树。

  以上就是Java中HashMap如何处理冲突。这种方法被称为链地址法，因为使用链表存储同一桶内的元素。通常情况HashMap，HashSet，LinkedHashSet，LinkedHashMap，ConcurrentHashMap，HashTable，IdentityHashMap和WeakHashMap均采用这种方法处理冲突。从JDK 8开始，HashMap，LinkedHashMap和ConcurrentHashMap为了提升性能，在频繁冲突的时候使用平衡树来替代链表。因为HashSet内部使用了HashMap，LinkedHashSet内部使用了LinkedHashMap，所以他们的性能也会得到提升。

1. 查询插入等用途：在Map中插入、删除和定位元素，HashMap适合；若要按顺序遍历键，则TreeMap适合。
2. 优化：HashMap可以调优初始容量和负载因子；TreeMap没有调优选项，因为树总处于平衡状态。
3. 实现接口：都实现了Cloneable接口。TreeMap实现SortMap接口，能够把它保存的记录根据键排序（默认按键的升序），HashMap继承AbstractMap；
4. 底层实现：TreeMap底层是数组+红黑树；HashMap底层是数组+链表法（从Java 8开始，HashMap，ConcurrentHashMap和LinkedHashMap在处理频繁冲突时将使用平衡树来代替链表，当同一hash桶中的元素数量超过特定的值（默认为8）便会由链表切换到平衡树，这会将get()方法的性能从O(n)提高到O(logn)。）

HashSet底层是通过HashMap实现的。add的时候，调用map的put方法，value始终是PRESENT，所以HashSet是所有value值都相同的HashMap。

1. 实现接口：HashSet实现了Set集合的接口，不允许有重复的值（准确说应该是元素作为key，value是定义为final的对象），将对象存储在HashSet之前，需要确保对象已经重写了equals和hashCode方法，这样才能比较两个对象的值是否相等，确保set中没有存储相等的对象。HashMap实现了Map集合接口，对键值对进行映射。Map中不允许重复的键。
2. 存储元素：HashMap存储的是键值对，不允许有重复的键；Hashset存储的是对象，不能有重复的对象元素。
3. 添加元素方法：HashMap使用put方法将元素放入map中，HashSet使用add方法将元素放入set中。
4. hashCode值的计算：HashMap中使用键对象计算hashcode的值，HashSet中使用成员对象来计算hashcode值。
5. 效率：HashMap比较快，因为使用唯一的键来获取对象，HashSet比HashMap慢。
6. 底层实现：HashSet是所有value值都相同的HashMap。HashSet内部使用HashMap实现，只不过HashSet里面的HashMap所有的value都是同一个object而已。private transient HashMap<E,Object> map;只是包含了hashmap的key。

同：
两者都是用key-value方式获取数据。
异：

1. null值：HashMap允许null值作为key和value；Hashtable不允许null的键值；
2. 顺序性：HashMap不保证映射的顺序不变，但是作为HashMap的子类LinkedHashMap默认按照插入顺序来进行映射的顺序；Hashtable无法保证；
3. 线程安全：HashMap是非同步的（非线程安全），效率高；Hashtable是同步的（线程安全的），效率低。（HashMap同步通过Collections.synchronizedMap()实现）
4. 快速失败机制：迭代HashMap采用fail-fast快速失败机制（快速失败机制：是一个线程或软件对于其故障做出的响应，用来即时报告可能会导致失败的任何故障情况，如果一个Iterator在集合对象上创建了，其他线程想结构化的修改该集合对象，抛出并发修改异常ConcurrentModificationException）；而HashTable的enumerator迭代器不是fail-fast的（Hashtable的上下文同步：一个时间点只能有一个线程可以修改哈希表，任何线程在执行Hashtable的更新操作前需要获取对象锁，其他线程等待锁的释放；
5. 父类：HashMap继承AbstractMap，Hashtable继承Dictionary；
6. 数组默认大小：HashMap底层数组的默认大小是16，扩容是2*old；Hashtable底层数组默认是11，扩容方式是2*old+1；
7. 效率：HashMap是非线程安全的，单线程下效率高；Hashtable是线程安全的，方法都加了synchronized关键字进行同步，效率较低；
8. 计算hash方式不同：HashMap是二次hash，对key的hashCode进行二次hash，获得更好的散列值；而Hashtable是直接使用key的hashCode对table数组进行取模。

  通过Collections集合工具类中的synchronizedMap()方法实现同步：Map map = Collections.synchronizedMap(hashMap);。
Collections.synchronizedMap()实现原理是Collections定义了一个 SynchronizedMap的内部类，这个类实现了Map接口，在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的。

    private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;
        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize
        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNonNull(m);
            mutex = this;
        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        public int size() {
            synchronized (mutex) {return m.size();}
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        public boolean containsKey(Object key) {
            synchronized (mutex) {return m.containsKey(key);}
        public boolean containsValue(Object value) {
            synchronized (mutex) {return m.containsValue(value);}
        public V get(Object key) {
            synchronized (mutex) {return m.get(key);}
        public V put(K key, V value) {
            synchronized (mutex) {return m.put(key, value);}
        public V remove(Object key) {
            synchronized (mutex) {return m.remove(key);}
        public void putAll(Map<? extends K, ? extends V> map) {
            synchronized (mutex) {m.putAll(map);}
        public void clear() {
            synchronized (mutex) {m.clear();}
        private transient Set<K> keySet;
        private transient Set<Map.Entry<K,V>> entrySet;
        private transient Collection<V> values;
        public Set<K> keySet() {
            synchronized (mutex) {
                if (keySet==null)
                    keySet = new SynchronizedSet<>(m.keySet(), mutex);
                return keySet;
        public Set<Map.Entry<K,V>> entrySet() {
            synchronized (mutex) {
                if (entrySet==null)
                    entrySet = new SynchronizedSet<>(m.entrySet(), mutex);
                return entrySet;
        public Collection<V> values() {
            synchronized (mutex) {
                if (values==null)
                    values = new SynchronizedCollection<>(m.values(), mutex);
                return values;
        public boolean equals(Object o) {
            if (this == o)
                return true;
            synchronized (mutex) {return m.equals(o);}
        public int hashCode() {
            synchronized (mutex) {return m.hashCode();}
        public String toString() {
            synchronized (mutex) {return m.toString();}
        // Override default methods in Map
        @Override
        public V getOrDefault(Object k, V defaultValue) {
            synchronized (mutex) {return m.getOrDefault(k, defaultValue);}
        @Override
        public void forEach(BiConsumer<? super K, ? super V> action) {
            synchronized (mutex) {m.forEach(action);}
        @Override
        public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
            synchronized (mutex) {m.replaceAll(function);}
        @Override
        public V putIfAbsent(K key, V value) {
            synchronized (mutex) {return m.putIfAbsent(key, value);}
        @Override
        public boolean remove(Object key, Object value) {
            synchronized (mutex) {return m.remove(key, value);}
        @Override
        public boolean replace(K key, V oldValue, V newValue) {
            synchronized (mutex) {return m.replace(key, oldValue, newValue);}
        @Override
        public V replace(K key, V value) {
            synchronized (mutex) {return m.replace(key, value);}
        @Override
        public V computeIfAbsent(K key,
                Function<? super K, ? extends V> mappingFunction) {
            synchronized (mutex) {return m.computeIfAbsent(key, mappingFunction);}
        @Override
        public V computeIfPresent(K key,
                BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
            synchronized (mutex) {return m.computeIfPresent(key, remappingFunction);}
        @Override
        public V compute(K key,
                BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
            synchronized (mutex) {return m.compute(key, remappingFunction);}
        @Override
        public V merge(K key, V value,
                BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
            synchronized (mutex) {return m.merge(key, value, remappingFunction);}
        private void writeObject(ObjectOutputStream s) throws IOException {
            synchronized (mutex) {s.defaultWriteObject();}