HashMap

HashMap

源码解析+常见HashMap问题转载自：https://blog.csdn.net/richard_jason/article/details/53887222

强子HashMap存储结构博客：https://blog.51cloud.win/2017/05/14/HashMap/#more
HashMap解析：https://blog.51cloud.win/2018/03/05/浅析JavaHashMap源码/#more

总结：
什么是map?
map即映射，也就是平时说的key-value键值对，entry：也是key，value的形式存储的，有了entry后从map里取值，赋值上更方便[对象操作对象]（查了好多资料都是这样说的，而且好多实现都是把值存到entry中，在存到map里，而jdk8用的不是entry用的是node，而对hash算法，也是对entry或者是node的使用进行了hash而对map本身没有影响）

什么是hashMap?
也就是使用了hash算法的map

        HashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树的引入是为了提高效率（JDK1.8中引入了红黑树，当链表长度太长（默认超过8））。

        默认的初始容量(capacity)是16，最大容量(max_capacity)是1<<30(很大)，默认的负载因子(loadFactor)为0.75，当HashMap的容量达到threshold（16*0.75=12）时候会扩容（resize）。扩容是将原来的数组扩大两倍（HashMap的数组大小一定是2的n次方）。

HashMap不是线程安全的类，在并发情况下，resize(扩容)可能会出现死锁。

HashMap与HashTable的区别:
1：继承的父类不同。
HashMap是Map接口的一个实现类，HashTable是Dictionary的子类同时也实现了Map接口。
2：线程安全性不同。
HashMap不是线程安全的，HashTable是线程安全的（每个方法都用synchronize修饰变成同步方法）。
3：是否允许key、value值为null。
HashMap允许key、value为null，HashTable不允许key、value是null。 
4：是否提供contains方法。       
HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。
Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。
5：hash值不同。
HashMap是重新计算hash（内部使用static final int hash(Object key)获取hash值），HashTable是直接使用key的hashCode作为hash值。 
HashMape取哈希桶下标是利用hashcode值的高16位或低16位进行计算，HashTable取哈希桶下标是直接用模运算%(hashcode)。（因为其默认容量也不是2的n次方。所以也无法用位运算替代模运算） 
6：内部实现使用的数组初始化和扩容方式不同。
HashMap的默认容量为16（哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。），HashTable默认容量是11。
扩容时，HashMap中容量(key所在数组)变成原来的2倍，HashTable容量是原来的2倍+1。int newCapacity = (oldCapacity << 1) + 1。

补充：
HashSet：
查看源代码可知，HashSet底层维护HashMap，因此其实现原理和HashMap一样。

LinkedHashMap和HashMap的区别：
HashMap输出时是无序的。
LinkedHashMap是HashMap的子类，输出时其元素是有序的。（如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现,它还可以按读取顺序来排列，像连接池中可以应用。）