1 Map

HashMap的底層結構就是：數組+鏈表!（鍵是哈希表結構的存儲）

數組是鏈表數組:每一個數組元素都是鏈表。

HashMap添加元素時，哈希值相同的元素放在一個鏈表裡。

hashmap初始容量大小（16）

鍵值對存放的數組下標一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數組長度取模得到。

HashMap的容量乘以負載因子[默認0.75] = threshold（size的閾值）; // threshold即為開始擴容的臨界值，默認擴容為原來的2倍。

1.1 Hashtable和HashMap

不是HashTable 哦！原因：java源碼開發人員的手誤，一直沿用至今！再NB的人也有犯錯的時候！

Hashtable底層也是哈希表（數組加鏈表）實現的；

Hashtable：線程安全，效率低；不允許null鍵和null值。

HashMap:線程不安全的，效率高。允許null鍵和null值。null鍵最多一個。

Hashtable和HashMap的用法基本完全一樣，它就是用來替代HashMap的。

HashMap和Hashtable都實現了Map接口，但決定用哪一個之前先要弄清楚它們之間的分別。主要的區別有：線程安全性，同步(synchronization)，以及速度。

HashMap幾乎可以等價於Hashtable，除了HashMap是非synchronized的，並可以接受null(HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行)。

HashMap是非synchronized，而Hashtable是synchronized，這意味著Hashtable是線程安全的，多個線程可以共享一個Hashtable；而如果沒有正確的同步的話，多個線程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好。

另一個區別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當有其它線程改變了HashMap的結構（增加或者移除元素），將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常。但這並不是一個一定發生的行為，要看JVM。這條同樣也是Enumeration和Iterator的區別。

由於Hashtable是線程安全的也是synchronized，所以在單線程環境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那麼使用HashMap性能要好過Hashtable。

HashMap不能保證隨著時間的推移Map中的元素次序是不變的。

要注意的一些重要術語：

1) sychronized意味著在一次僅有一個線程能夠更改Hashtable。就是說任何線程要更新Hashtable時要首先獲得同步鎖，其它線程要等到同步鎖被釋放之後才能再次獲得同步鎖更新Hashtable。

2) Fail-safe和iterator迭代器相關。如果某個集合對象創建了Iterator或者ListIterator，然後其它的線程試圖“結構上”更改集合對象，將會拋出ConcurrentModificationException異常。但其它線程可以通過set()方法更改集合對象是允許的，因為這並沒有從“結構上”更改集合。但是假如已經從結構上進行了更改，再調用set()方法，將會拋出IllegalArgumentException異常。

3) 結構上的更改指的是刪除或者插入一個元素，這樣會影響到map的結構

我們能否讓HashMap同步？

HashMap可以通過下面的語句進行同步：

Map m = Collections.synchronizeMap(hashMap);

結論

Hashtable和HashMap有幾個主要的不同：線程安全以及速度。僅在你需要完全的線程安全的時候使用Hashtable，而如果你使用Java 5或以上的話，請使用ConcurrentHashMap吧。

Hashtable和ConcurrentHashMap有什麼分別呢？它們都可以用於多線程的環境，但是當Hashtable的大小增加到一定的時候，性能會急劇下降，因為迭代時需要被鎖定很長的時間。因為ConcurrentHashMap引入了分割(segmentation)，不論它變得多麼大，僅僅需要鎖定map的某個部分，而其它的線程不需要等到迭代完成才能訪問map。簡而言之，在迭代的過程中，ConcurrentHashMap僅僅鎖定map的某個部分，而Hashtable則會鎖定整個map。

2.1 自定義實現HashMap

package cn.gxhc.collection;

import java.util.LinkedList;

/**

* 自定義Map：

* 1. 提高查詢的效率

*/

class SxtEntry {

Object key;

Object value;

public SxtEntry(Object key, Object value) {

super();

this.key = key;

this.value = value;

}

}

public

class SxtMap002 {

LinkedList[] arr = new LinkedList[9]; //Map的底層結構就是：數組+鏈表!

int size;

public void put(Object key,Object value){

SxtEntry e = new SxtEntry(key,value);

int hash = key.hashCode();

hash = hash<0?-hash:hash;

int a = hash%arr.length;

if(arr[a]==null){

LinkedList list = new LinkedList();

arr[a] = list;

list.add(e);

}else{

LinkedList list = arr[a];

for(int i=0;i<list.size>

SxtEntry e2 = (SxtEntry) list.get(i);

if(e2.key.equals(key)){

e2.value = value; //鍵值重複直接覆蓋！

return;

}

}

arr[a].add(e);

}

//a:1000-->1 b:10000-->13

}

public Object get(Object key){

int

a = key.hashCode()%arr.length;

if(arr[a]!=null){

LinkedList list = arr[a];

for(int i=0;i<list.size>

SxtEntry e = (SxtEntry) list.get(i);

if(e.key.equals(key)){

return e.value;

}

}

}

return null;

}

public static void main(String[] args) {

SxtMap002 m =

new SxtMap002();

m.put("鄭一鳴", new Wife("楊冪"));

m.put("葉冠偉", new Wife("李四"));

Wife w = (Wife) m.get("鄭一鳴");

System.out.println(w.name);

}

}

/<list.size>

/<list.size>