基于散列的集合中，HashMap應該是用的最多的鍵值對容器，既然用的這么頻繁，我覺得還是很有必要搞清楚原理，而寫出來，思路會更清晰。 先看下簡單的繼承體系： 
從圖上看，繼承體系很簡單，2個標記性接口，然后就是作為Map的功能，很單純。 然后再來看看數(shù)據(jù)結構圖： 
圖上一個空格就代表一個節(jié)點，而每個key-value對都保存在一個節(jié)點中，下面的代碼正式HashMap每個節(jié)點的數(shù)據(jù)結構。 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; } 從數(shù)據(jù)結構圖判斷，HashMap中肯定維護著一個數(shù)組，用來存儲每個節(jié)點，現(xiàn)在就有2個問題，如何在數(shù)組中定位自己的位置（行話叫：桶），萬一桶被占用了怎么辦？ 既然叫HashMap，通過名字大概能夠猜想得出了，是通過hash值來定位的，通過hash算出自己桶的位置，然而位置是有限的，那么通過函數(shù)映射（hash與數(shù)組長取模）到其中的位置時，必然的會出現(xiàn)沖突，解決沖突辦法，就如同上圖所示，鏈表法。 優(yōu)化性能的設計 HashMap設計時候需要考慮速度的問題，鏈表連接的越長性能就越差，極端的例子，退化成單鏈表，時間復雜度O（N）,這樣就失去了快速訪問的特性。 如果為了速度最快，最好的辦法就是沒有鏈表，既然是通過取模的方式進行定位，要達到最少沖突，肯定需要很長的數(shù)組，而數(shù)組越長，就越容易浪費。 為了達到理想的效果，又不浪費太多的空間，hashmap使用了一個閥值，當對象的數(shù)量達到閥值，才會進行擴容，這樣就能夠保證浪費的空間是在可控的有限范圍內。通過調節(jié)閥值，可以使得鏈表的鏈接的節(jié)點盡量的少。 如何定義閥值？hashmap中用了負載因子這么個概念，用數(shù)組的容量*負載因子作為閥值，默認負載因子是0.75。可以自行調整，但是一般不建議，優(yōu)化有時候是個很棘手的問題，不成熟的優(yōu)化是所有罪惡之源，最好的策略就是置之不顧，直到你發(fā)現(xiàn)真正需要優(yōu)化他。
基于散列的集合，除了HashMap外，常用的還有HashSet、LinkedHashSet、LinkedHashMap。而這三個都是在HashMap的基礎上進行改造的，只要明白了HashMap的原理，其他的非常容易清楚。 HashSet 我們來簡單分析下，在jdk中的源碼：
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{ static final long serialVersionUID = -5024744406713321676L; PRivate transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); /** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has * default initial capacity (16) and load factor (0.75). */ public HashSet() { map = new HashMap<>();//實例化時，同時實例化HashMap }上面是摘抄HashSet源碼的一段，發(fā)現(xiàn)沒，這是組合，是代理，用hashMap進行代理，下面最后列舉下最常用的功能：
public boolean add(E e) { return map.put(e, PRESENT)==null; //PRESENT為常量 } public Iterator<E> iterator() { return map.keySet().iterator(); }發(fā)了沒，是委托給HashMap的。 LinkedHashMap 估計 應該都知道，它既能擁有hashmap的速度，又能有序遍歷，直接看源碼：
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>發(fā)現(xiàn)沒，是繼承自HashMap，可以說，復用了大部分的HashMap功能。 思考 ：它是如何在hashmap的基礎上進行改造，使的元素有序？ 我們先看下面這幅圖： 
大家應該都知道了，左邊的是hashmap的元素節(jié)點，而右邊的正是LinkedHashMap的元素節(jié)點。發(fā)現(xiàn)多了什么了嗎？2個指針，指向前驅和指向后繼。想下，如果每個元素都能夠知道后面是誰，從頭開始按照順序進行元素遍歷，這個還難嗎？看下面創(chuàng)造節(jié)點的代碼：
看見沒，createEntry比hashmap多了一個重定位指針的操作。header節(jié)點中保存有第二個和最后一個節(jié)點的指針（不懂看上圖），保證有序，只需要把現(xiàn)有最后一個節(jié)點的after 指向本節(jié)點，就保證新加入的元素是有序，現(xiàn)有最后一個節(jié)點可以通過header.before獲取，同時為了下一次新加入節(jié)點能正常有序，需要把header的前節(jié)點重新地位到新的最后一個節(jié)點（也就是說header.before指向新節(jié)點）。這樣再通過after指針就能順藤摸瓜，順序遍歷了。 LinkedHashSet 看源碼：
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {好像和我們想象的不一樣，不應該是LinkedHashMap嗎？不急繼續(xù)看其構造函數(shù)
public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); } HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }發(fā)現(xiàn)沒，HashSet這種構造方法用的是LinkedHashMap，現(xiàn)在還需要寫下去嗎，如同hashset復用hashMap原理一樣。
新聞熱點
疑難解答
