對于HashMap、Hashtable、TreeMap、LinkedHashMap的内部排序，發現網上有很多人都了解錯了。
比如，有的人認為：
Hashtable.keySet() 降序
TreeMap.keySet() 升序
HashMap.keySet() 亂序
LinkedHashMap.keySet() 原序
也有的人認為是keyset跟entryset的差別導緻的。那麼下面我就通過兩種周遊方式來給大家試驗一下。
把全部要論證的問題先抛在這裡，待會看代碼看結果：
1.HashMap、Hashtable、TreeMap、LinkedHashMap的内部排序
2.分别用 keyset跟entryset周遊出來的結果有差別嗎
3.HashMap、Hashtable、TreeMap、LinkedHashMap初始預設的大小
研究了一些天，有了些結果，都是通過代碼測試出來的，親測有效~~~ （分别對int，String進行測試，主要看key的排序）
（終極聲明，大家先不要吐槽範型的問題，我隻是做個測試，不影響實際操作，謝過）
先來重制一下網上的輿論結果，看我的代碼
package testCollections;
import java.util.*;
import java.util.Map.Entry;
public class TestOfOrderOfMap {
//測試Keyset的排序
public void testOfKeyset(Map map, Object obj[]){
for(int i=0; i<obj.length; i++){
map.put(obj[i], obj[i]);
}
if(map instanceof LinkedHashMap){//LinkedHashMap也是一種HashMap，是以對其測試要放在前面
System.out.println("LinkedHashMap" +": " + map);
}else if(map instanceof HashMap){
System.out.println("HashMap" +": " + map);
}else if(map instanceof Hashtable){
System.out.println("Hashtable" +": " + map);
}else if(map instanceof TreeMap){
System.out.println("TreeMap" +": " + map);
}
System.out.print("key: ");
Iterator it = map.keySet().iterator();
<span style="white-space:pre"> </span>while (it.hasNext()) {
<span style="white-space:pre"> </span>Object key = it.next();
System.out.print(key+" ");
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>System.out.println();
}
//測試Entryset的排序
public void testOfEntryset(Map map, Object obj[]){
for(int i=0; i<obj.length; i++){
map.put(obj[i], obj[i]);
}
if(map instanceof LinkedHashMap){//LinkedHashMap也是一種HashMap，是以對其測試要放在前面
System.out.println("LinkedHashMap" +": " + map);
}else if(map instanceof HashMap){
System.out.println("HashMap" +": " + map);
}else if(map instanceof Hashtable){
System.out.println("Hashtable" +": " + map);
}else if(map instanceof TreeMap){
System.out.println("TreeMap" +": " + map);
}
System.out.print("key: ");
Iterator it = map.entrySet().iterator();
<span style="white-space:pre"> </span>while (it.hasNext()) {
<span style="white-space:pre"> </span>Entry e = (Entry) it.next();
<span style="white-space:pre"> </span>System.out.print(e.getKey()+" ");
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span> System.out.println();
}
public static void main(String[] args) {
TestOfOrderOfMap test = new TestOfOrderOfMap();
HashMap hm1 = new HashMap(); //第一組集合是用來測試int類型的key
Hashtable ht1 = new Hashtable();
TreeMap tm1 = new TreeMap();
LinkedHashMap lhm1 = new LinkedHashMap();
Integer a[] = new Integer[]{3, 2, 5, 1, 4};
//測試Keyset中key為數字的排序
System.out.println("這裡是KeySet的測試：");
test.testOfKeyset(hm1, a);
test.testOfKeyset(ht1, a);
test.testOfKeyset(tm1, a);
test.testOfKeyset(lhm1, a);
//測試Entryset中key為數字的排序
System.out.println();
System.out.println("這裡是EntrySet的測試：");
test.testOfEntryset(hm1, a);
test.testOfEntryset(ht1, a);
test.testOfEntryset(tm1, a);
test.testOfEntryset(lhm1, a);
}
}
看結果
圖1
大家是不是覺得就跟上面說的一樣啊，部落客，你逗我們的吧？
Hashtable.keySet() 降序
TreeMap.keySet() 升序
HashMap.keySet() 亂序
LinkedHashMap.keySet() 原序
且聽部落客慢慢講解噢，在這裡可以肯定的是keyset 跟 entryset所周遊的結果完全是一樣的，證明了第二點，那麼第一點呢，
如果我把上面的 Integer a[] = new Integer[]{3, 2, 5, 1, 4}; 改為 Integer a[] = new Integer[]{13, 2, 5, 1, 4}; 也就是把3改為了13,
你們再看結果
圖2
是不是想說，咦，這是什麼鬼。是不是上面的論斷結果是錯誤的了呀，
Hashtable.keySet() 降序 //錯誤
TreeMap.keySet() 升序 //正确
HashMap.keySet() 亂序 //可以說錯誤，因為你還不懂它的原理
LinkedHashMap.keySet() 原序 //可以說錯誤，因為你還不懂它的原理，這和LinkedHashMap的構造方法有關，後面我會說
再來看幾組結果，聽我分析。（以後我隻列出keyset的結果截圖，因為entryset 跟 keyset一樣）
如果我把上面的 Integer a[] = new Integer[]{3, 2, 5, 1, 4}; 改為 Integer a[] = new Integer[]{16, 2, 5, 1, 4};
圖3
如果我把上面的 Integer a[] = new Integer[]{3, 2, 5, 1, 4}; 改為 Integer a[] = new Integer[]{11, 2, 5, 1, 4};
圖4
如果我把上面的 Integer a[] = new Integer[]{3, 2, 5, 1, 4}; 改為 Integer a[] = new Integer[]{0, 65, 3， 17, 32};
圖5
大家看出端倪沒有，是這樣的，如果看過這些集合類源碼的哥哥姐姐可能就會知道，它們的周遊與它們的存儲有關，而存儲與容器的大小有關，
而在我們建立容器卻沒有指定容器大小的情況下，容器一般都會有一個預設大小，這個很好了解。
HashMap 的預設大小為16，每次增長會加倍，Hashtable的預設大小為11，每次增長原來的2倍加1，TreeMap 跟 LinkedHashMap暫時無法确定或者說無限大，
不過在這裡不影響我們的了解。好了，HashMap是會根據key的hashCode再進行hash計算，最後散列到Entry中，看源碼
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);<span style="white-space:pre"> </span>//求key的hash值
int i = indexFor(hash, table.length); //找準位置插下去
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);//将其添加到該哈希值對應的連結清單中
return null;
}
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);<span style="white-space:pre"> </span>//這裡很複雜，重新計算了哈希值
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1); //實際上就是求模
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //擴容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);// 将“key-value”插入指定位置，bucketIndex是位置索引。
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);// 建立Entry。将“key-value”插入指定位置。
size++;
}
取value的過程也一樣，就是根據key存放的位置來取，是以說HashMap不是無序的，而是按照hash值來存取的，隻不過這個hash值，我們比較難以計算出來罷了。
有個小發現，當key的值不超過16時，HashMap的存取是按照從小到大的順序來存取的
圖6
至于Hashtable的存取，跟HashMap大同小異，隻不過在方法前加了個synchronized同步字段，其次是hash值的計算有點小差別
有個小發現，當key的個數不超過11且key的值不超過11時，Hashtable的存取是按照從大到小的順序來存取的
圖7
T
reeMap就比較好了解了，其底層實作采用的是紅黑樹，key按照從小到大的順序排好，搞定。
LinkedHashMap這裡呢，有兩個順序，一個是插入的順序，一個是通路的順序，取決于構造方法裡面的參數accessOrder是否為true，當accessOrder為true時，周遊LinkedHashMap是按照通路順序存儲，當accessOrder為false時，LinkedHashMap是按照插入順序存儲，預設為false。看例子。
package testCollections;
import java.util.*;
import java.util.Map.Entry;
public class TestOfOrderOfMap {
public void testOfKeyset(Map map, Object obj[]){
for(int i=0; i<obj.length; i++){
map.put(obj[i], obj[i]);
}
System.out.println("LinkedHashMap" +": " + map);
System.out.print("key: ");
Iterator it = map.keySet().iterator();
while (it.hasNext()) {
Object key = it.next();
System.out.print(key+" ");
}
System.out.println();
}
public static void main(String[] args) {
TestOfOrderOfMap test = new TestOfOrderOfMap();
LinkedHashMap lhm1 = new LinkedHashMap();
Integer a[] = new Integer[]{7, 0, 5, 10, 17, 6, 2, 8, 3, 31};
test.testOfKeyset(lhm1, a);
}
}
結果：
圖8
插入的順序為Integer a[] = new Integer[]{7, 0, 5, 10, 17, 6, 2, 8, 3, 31}
列印的順序也是 7, 0, 5, 10, 17, 6, 2, 8, 3, 31
下面看按通路順序的，把上面的
LinkedHashMap lhm1 = new LinkedHashMap();
改為 LinkedHashMap lhm1 = new LinkedHashMap(16, 0.75f,true);全部修改如下：
package testCollections;
import java.util.*;
import java.util.Map.Entry;
public class TestOfOrderOfMap {
<span style="white-space:pre"> </span>public void testOfKeyset(Map map, Object obj[]){
<span style="white-space:pre"> </span>for(int i=0; i<obj.length; i++){
<span style="white-space:pre"> </span>map.put(obj[i], obj[i]);
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>System.out.println("LinkedHashMap" +": " + map);
<span style="white-space:pre"> </span>System.out.print("通路 " + map.get(7)+" 之後： ");
<span style="white-space:pre"> </span>System.out.println(map);
<span style="white-space:pre"> </span>System.out.print("通路 " + map.get(10)+" 之後： ");
<span style="white-space:pre"> </span>System.out.println(map);
<span style="white-space:pre"> </span>System.out.print("最後key: ");
<span style="white-space:pre"> </span>Iterator it = map.keySet().iterator();
<span style="white-space:pre"> </span>while (it.hasNext()) {
<span style="white-space:pre"> </span>Object key = it.next();
<span style="white-space:pre"> </span>System.out.print(key+" ");
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>System.out.println();
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>public static void main(String[] args) {
<span style="white-space:pre"> </span>TestOfOrderOfMap test = new TestOfOrderOfMap();
<span style="white-space:pre"> </span>LinkedHashMap lhm1 = new LinkedHashMap(16, 0.75f,true);
<span style="white-space:pre"> </span>Integer a[] = new Integer[]{7, 0, 5, 10, 17, 6, 2, 8, 3, 31};
<span style="white-space:pre"> </span>test.testOfKeyset(lhm1, a);
<span style="white-space:pre"> </span>}
}
結果為
圖9
分析：插入的順序為 7, 0, 5, 10, 17, 6, 2, 8, 3, 31 map.get(7)之後，也就是通路7之後，就把7放在了連結清單的最末尾，也就是放在了31之後，變成了
0,5,10,17,6,2,8,3,31,7 接着map.get(10)之後，也就是通路10之後，就把10放在了連結清單的最末尾，也就是7之後，變成了 0,5,17,6,2,8,3,31,7,10
這就是按通路順序存儲，據說這樣的好處就是可以實作LRU，即把所有通路過的對象放在了最後，那麼沒有被通路過的對象就在最前面了，當記憶體不夠用時，
就可以直接把前面最近最久沒有使用的對象删除以接受新對象，進而實作置換。
下面附加一個小知識，
當構造方法的參數 accessOrder為true時，LinkedHashMap的get()方法會改變資料連結清單,那會有什麼後果呢？先看結果
圖10
啊哦，報錯了，java.util.ConcurrentModificationException，先說明下，當用Entryset 來周遊的時候就不會有錯，用keyset 周遊的時候就會有錯，就是下面這段代碼
<span style="white-space:pre"> </span>Iterator it = map.keySet().iterator();
while (it.hasNext()) {
<span style="white-space:pre"> </span>Object key = it.next();
<span style="white-space:pre"> </span>System.out.print(key+" ");
<span style="white-space:pre"> </span>System.out.print(map.get(key));
}
這是為什麼呀，根據報錯的源代碼就很好了解了
<span style="white-space:pre"> </span>nextEntry() {
if (modCount != expectedModCount) //Entry 被修改的次數不等于它期望的被修改次數，是以抛出了ConcurrentModificationException異常
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
因為當 accessOrder為true時， LinkedHashMap的get( )方法會改變資料連結清單,因為每通路一次都要把這個key對應的Entry放到連結清單的最末尾（上面已經分析過），而Keyset 的 Iterator對象不允許我們動态去改變LinkedHashMap的資料連結清單結構，正如上面的源代碼所說的，Entry 被修改的次數不等于它期望的被修改次數。因為本來就是排好序的了，你現在每通路一個，就把它放在最末尾，那麼我接下來去找它的下一個的時候卻發現原來那個已經不在了，因為這是動态發生的，誰也察覺不到，隻有當通路到它的時候才發現不在那個位置了（拿上面那個例子，通路第一個位置上7的時候還是沒問題的，通路完之後，把7放到最後面，原來的第二個位置對應的0，現在被頂到了第一個位置上，那麼我下一輪該通路0的時候卻發現0不見了，換成了5，那麼是不是就應該報錯呢）。現在明白了吧。就好比我用書包背十個乒乓球去體育館打球，突然過來一個同學偷偷摸摸拿走了一個，還把一個壞了的放我書包裡面，也不跟我打聲招呼，我也沒看見，過了一個小時，我把其中的9個乒乓球都打壞了，想拿第十個來用，發現，咦，怎麼是壞的啊，誰換了我的乒乓球啊，我這時是不是該報警啊（哈哈，開個玩笑）
那為什麼accessOrder 為false時，采用keyset周遊就不會出現這種異常啊，因為為false 時，是按插入順序存儲啊，沒有破壞原來的順序啊，也就不會出現
modCount != expectdModCount 的情況了。
那為什麼entryset周遊的時候就不會出錯呀？因為，keyset 隻是預先把所有的key 放到了set當中，沒有跟value對應起來，
而entryset是把預先所有的Entry 都放在了set中，Entry中有key對應的value，是以key改變的時候value 也會跟着改變，就不會發現錯位的情況了。
兩個的源碼比較
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
}
其中next（）裡面的return，在KeyIterator類中還多了一個getKey（）。
記得啊，你要犯這一個錯誤得要有三個條件才行呢，1，accessOrder 設為true。2，用keyset 周遊。3，使用map.get（key）方法
到此，最開始提出的三個問題都已經解決了。
那麼回過頭來，我們來測試當key為String 對象的時候又是個什麼情形呢，其實也是大同小異啦
package testCollections;
import java.util.*;
import java.util.Map.Entry;
public class TestOfOrderOfMap {
public void testOfKeyset(Map map, Object obj[]){
for(int i=0; i<obj.length; i++){
map.put(obj[i], obj[i]);
}
if(map instanceof LinkedHashMap){//LinkedHashMap也是一種HashMap，是以對其測試要放在前面
System.out.println("LinkedHashMap" +": " + map);
}else if(map instanceof HashMap){
System.out.println("HashMap" +": " + map);
}else if(map instanceof Hashtable){
System.out.println("Hashtable" +": " + map);
}else if(map instanceof TreeMap){
System.out.println("TreeMap" +": " + map);
}
System.out.print("key: ");
Iterator it = map.keySet().iterator();
<span style="white-space:pre"> </span>while (it.hasNext()) {
<span style="white-space:pre"> </span>Object key = it.next();
<span style="white-space:pre"> </span>System.out.print(key+" ");
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>System.out.println();
}
public static void main(String[] args) {
TestOfOrderOfMap test = new TestOfOrderOfMap();
HashMap hm2= new HashMap(); //第二組集合是用來測試String類型的key
Hashtable ht2 = new Hashtable();
TreeMap tm2 = new TreeMap();
LinkedHashMap lhm2 = new LinkedHashMap(10, 0.75f, true);
//Integer a[] = new Integer[]{7, 0, 5, 10, 17,6,2,8,3,31};
String a[] = new String[]{"aa", "Ok", "YOU", "abc", "67k"};
//測試Keyset中key為數字的排序
System.out.println("這裡是KeySet的測試：");
test.testOfKeyset(hm2, a);
test.testOfKeyset(ht2, a);
test.testOfKeyset(tm2, a);
test.testOfKeyset(lhm2, a);
/*//測試Entryset中key為數字的排序
System.out.println();
System.out.println("這裡是EntrySet的測試：");
test.testOfEntryset(hm2, a);
test.testOfEntryset(ht2, a);
test.testOfEntryset(tm2, a);
test.testOfEntryset(lhm2, a);*/
}
}
結果
圖11
分析，HashMap 跟 Hashtable 一樣都是無章可循的，根據它自己的hashCode來存儲，TreeMap呢，根據key 的第一個字母進行排序，先數字到大寫字母再到小寫字母。
LinkedHashMap 就還是跟上面的分析一樣。完畢！
總結：
1、HashMap、Hashtable的存儲順序跟key 所對應的hashCode有關，但是有小規律，當key的值不超過16時，HashMap的存取是按照從小到大的順序來存取的， 當key的個 數不超過11且key的值不超過11時，Hashtable的存取是按照從大到小的順序來存取的。TreeMap 的順序按照從小到大，LinkedHashMap的順序有兩種，一種是按插入順 序，一種是按通路順序，取決于accessOrder是否為true。
2、keyset 跟 entryset 的周遊結果沒有差別，有一點點差別是在LinkedHashMap中當按通路順序存儲時，采用keyset 周遊 get（）方法會報錯。
3、HashMap 的預設大小為16，每次增長會加倍，Hashtable的預設大小為11，每次增長原來的2倍加1，TreeMap 跟 LinkedHashMap暫時無法确定或者說無限大，不過在這 裡不影響我們的了解。
天快亮了，人生第一次寫這麼長的部落格，有什麼纰漏的地方還望各位不吝賜教，畢竟一個人的思維深度是有限的，3Q噢。（還有不得不說CSDN寫部落格的編輯框排版很有問題）