HashMap深入理解

Map的几种基本实现：HashMap、TreeMap、LinkedHashMap、WeekHashMap、ConCurrentHashMap、IdentityHashMap

HashMap—Map基于散列表的实现。HashMap使用equals()判断当前的键是否与表中存在的键相同同时散列码也要相同，所以，要想使用自己的类作为HashMap的键，必须同时重载hashCode()和equals().  

HashMap的数据结构：一个数组+N个链表，数组每一项对应一个链表。即：ArrayList<Entry<Key,Value>>[]

HashMap存储的实现原理：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值（hashCode & (table.length -1)），根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

HashMap查询的实现原理：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor(负载因子)时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

LinkedHashMap—类似HashMap，迭代遍历时，取得“键值对”的顺序是其插入次序，或者是最近最少使用的（LRU）的次序。只比HashMap慢一点，而迭代访问时速度更快，因为它是基于链表维护内部次序。 要实现LRU（Least Recently Used 近期最少使用算法）的Map，可以将LinkedHashMap的构造方法的第三个参数设置为true，即按照访问顺序进行排序。

TreeMap—基于红黑树的实现。它的键或键值对会被重新排序，次序由Comparable或Comparator决定。TreeMap的特点在于得到的结果是进行排序的。默认按照Key的自然顺序进行排序，即使用key进行compareTo后进行排序。

ConcurrentHashMap—线程安全的Map

WeakHashMap—弱引用map，IdentityHashMap—用==代替equals()对键进行比较的散列映射。这二者都是为解决特殊问题而设计的，不常用。