hashtable源碼

『壹』 hashmap底層實現原理

hashmap底層實現原理是SortedMap介面能夠把它保存的記錄根據鍵排序，默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator遍歷TreeMap時，得到的記錄是排過序的。

如果使用排序的映射，建議使用TreeMap。在使用TreeMap時，key必須實現Comparable介面或者在構造TreeMap傳入自定義的Comparator，否則會在運行時拋出java.lang.ClassCastException類型的異常。

Hashtable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，並且是線程安全的，任一時間只有一個線程能寫Hashtable

從結構實現來講，HashMap是：數組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現的。

(1)hashtable源碼擴展閱讀

從源碼可知，HashMap類中有一個非常重要的欄位，就是 Node[] table，即哈希桶數組。Node是HashMap的一個內部類，實現了Map.Entry介面，本質是就是一個映射(鍵值對)，除了K，V，還包含hash和next。

HashMap就是使用哈希表來存儲的。哈希表為解決沖突，採用鏈地址法來解決問題，鏈地址法，簡單來說，就是數組加鏈表的結合。在每個數組元素上都一個鏈表結構，當數據被Hash後，得到數組下標，把數據放在對應下標元素的鏈表上。

如果哈希桶數組很大，即使較差的Hash演算法也會比較分散，如果哈希桶數組數組很小，即使好的Hash演算法也會出現較多碰撞，所以就需要在空間成本和時間成本之間權衡，其實就是在根據實際情況確定哈希桶數組的大小，並在此基礎上設計好的hash演算法減少Hash碰撞。

『貳』 Hashtable，HashMap和TreeMap的區別

Java為數據結構中的映射定義了一個介面java.util.Map，

它有四個實現類，分別是HashMap、HashTable、LinkedHashMap和TreeMap。

這里介紹這4中實例的用法和區別。

關鍵技術剖析：
Map用於存儲鍵值對，根據鍵得到值，因此不允許鍵重復，值可以重復。
l （1）HashMap是一個最常用的Map，它根據鍵的hashCode值存儲數據，根據鍵可以直接獲取它的值，具有很快的訪問速度。HashMap最多隻允許一條記錄的鍵為null，不允許多條記錄的值為null。HashMap不支持線程的同步，即任一時刻可以有多個線程同時寫HashMap，可能會導致數據的不一致。如果需要同步，可以用Collections.synchronizedMap(HashMap map)方法使HashMap具有同步的能力。

l （2）Hashtable與HashMap類似，不同的是：它不允許記錄的鍵或者值為空；它支持線程的同步，即任一時刻只有一個線程能寫Hashtable，然而，這也導致了Hashtable在寫入時會比較慢。

l （3）LinkedHashMap保存了記錄的插入順序，在用Iteraor遍歷LinkedHashMap時，先得到的記錄肯定是先插入的。在遍歷的時候會比HashMap慢。有HashMap的全部特性。
l （4）TreeMap能夠把它保存的記錄根據鍵排序，默認是按升序排序，也可以指定排序的比較器。當用Iteraor遍歷TreeMap時，得到的記錄是排過序的。TreeMap的鍵和值都不能為空。

importjava.util.HashMap;
importjava.util.Hashtable;
importjava.util.Iterator;
importjava.util.LinkedHashMap;
importjava.util.Map;
importjava.util.TreeMap;


publicclassTestMap{


publicstaticvoidinit(Mapmap){
if(map!=null){
Stringkey=null;
for(inti=5;i>0;i--){
key=newInteger(i).toString()+".0";
map.put(key,key.toString());
//Map中的鍵是不重復的，如果插入兩個鍵值一樣的記錄，
//那麼後插入的記錄會覆蓋先插入的記錄
map.put(key,key.toString()+"0");}
}
}

publicstaticvoidoutput(Mapmap){
if(map!=null){
Objectkey=null;
Objectvalue=null;
//使用迭代器遍歷Map的鍵，根據鍵取值
Iteratorit=map.keySet().iterator();
while(it.hasNext()){
key=it.next();
value=map.get(key);
System.out.println("key:"+key+";value:"+value);
}
//或者使用迭代器遍歷Map的記錄Map.Entry
Map.Entryentry=null;
it=map.entrySet().iterator();
while(it.hasNext()){
//一個Map.Entry代表一條記錄
entry=(Map.Entry)it.next();
//通過entry可以獲得記錄的鍵和值
//System.out.println("key:"+entry.getKey()+";value:"+entry.getValue());
}
}
}

(Mapmap,Objectkey){
if(map!=null){
returnmap.containsKey(key);
}
returnfalse;
}

(Mapmap,Objectvalue){
if(map!=null){
returnmap.containsValue(value);
}
returnfalse;
}

publicstaticvoidtestHashMap(){
MapmyMap=newHashMap();
init(myMap);
//HashMap的鍵可以為null
myMap.put(null,"ddd");
//HashMap的值可以為null
myMap.put("aaa",null);
output(myMap);
}

publicstaticvoidtestHashtable(){
MapmyMap=newHashtable();
init(myMap);
//Hashtable的鍵不能為null
//myMap.put(null,"ddd");
//Hashtable的值不能為null
//myMap.put("aaa",null);
output(myMap);
}

(){
MapmyMap=newLinkedHashMap();
init(myMap);
//LinkedHashMap的鍵可以為null
myMap.put(null,"ddd");
myMap.put(null,"aaa");
//LinkedHashMap的值可以為null
myMap.put("aaa",null);
output(myMap);
}

publicstaticvoidtestTreeMap(){
MapmyMap=newTreeMap();
init(myMap);
//TreeMap的鍵不能為null
//myMap.put(null,"ddd");
//TreeMap的值不能為null
//myMap.put("aaa",null);
output(myMap);
}

publicstaticvoidmain(String[]args){
System.out.println("採用HashMap");
TestMap.testHashMap();
System.out.println("採用Hashtable");
TestMap.testHashtable();
System.out.println("採用LinkedHashMap");
TestMap.testLinkedHashMap();
System.out.println("採用TreeMap");
TestMap.testTreeMap();

MapmyMap=newHashMap();
TestMap.init(myMap);
System.out.println("新初始化一個Map:myMap");
TestMap.output(myMap);
//清空Map
myMap.clear();
System.out.println("將myMapclear後，myMap空了么?"+myMap.isEmpty());
TestMap.output(myMap);
myMap.put("aaa","aaaa");
myMap.put("bbb","bbbb");
//判斷Map是否包含某鍵或者某值
System.out.println("myMap包含鍵aaa?"+TestMap.containsKey(myMap,"aaa"));
System.out.println("myMap包含值aaaa?"+TestMap.containsValue(myMap,"aaaa"));
//根據鍵刪除Map中的記錄
myMap.remove("aaa");
System.out.println("刪除鍵aaa後，myMap包含鍵aaa?"+TestMap.containsKey(myMap,"aaa"));
//獲取Map的記錄數
System.out.println("myMap包含的記錄數:"+myMap.size());
}
}

輸出結果：
採用HashMap
key: null; value: ddd
key: 3.0; value: 3.00
key: aaa; value: null
key: 4.0; value: 4.00
key: 1.0; value: 1.00
key: 5.0; value: 5.00
key: 2.0; value: 2.00
採用Hashtable
key: 4.0; value: 4.00
key: 1.0; value: 1.00
key: 3.0; value: 3.00
key: 5.0; value: 5.00
key: 2.0; value: 2.00
採用LinkedHashMap
key: 5.0; value: 5.00
key: 4.0; value: 4.00
key: 3.0; value: 3.00
key: 2.0; value: 2.00
key: 1.0; value: 1.00
key: null; value: aaa
key: aaa; value: null
採用TreeMap
key: 1.0; value: 1.00
key: 2.0; value: 2.00
key: 3.0; value: 3.00
key: 4.0; value: 4.00
key: 5.0; value: 5.00
新初始化一個Map: myMap
key: 3.0; value: 3.00
key: 4.0; value: 4.00
key: 1.0; value: 1.00
key: 5.0; value: 5.00
key: 2.0; value: 2.00
將myMap clear後，myMap空了么? true
myMap包含鍵aaa? true
myMap包含值aaaa? true
刪除鍵aaa後，myMap包含鍵aaa? false
myMap包含的記錄數: 1

源碼分析：
遍歷Map有兩種方法：
（1）map的keySet()方法獲得鍵的集合，再調用鍵集合的iterator方法獲得鍵的迭代器，以此迭代地取出Map中的鍵，用get方法獲得鍵對應的值，便完成了Map的遍歷。代碼如下所示：
//使用迭代器遍歷Map的鍵，根據鍵取值
Iterator it = map.keySet().iterator();
while (it.hasNext()){
key = it.next();
value = map.get(key);
System.out.println("key: " + key + "; value: " + value );
}
（2）使用Map的entrySet方法獲得Map中記錄的集合，每條對象都是一個Map.Entry對象，使用其getKey方法獲得記錄的鍵，使用其getValue方法獲得記錄的值。代碼如下所示：
//或者使用迭代器遍歷Map的記錄Map.Entry
Map.Entry entry = null;
it = map.entrySet().iterator();
while (it.hasNext()){
//一個Map.Entry代表一條記錄
entry = (Map.Entry)it.next();
//通過entry可以獲得記錄的鍵和值
//System.out.println("key: " + entry.getKey() + "; value: " + entry.getValue());

『叄』 v8源碼解析之HashTable（v8 0.1.5）

在v8引擎中，哈希表的實現是通過一個名為HashTable的類完成的。它繼承自Array類，旨在提供一些通用邏輯以供後續子類使用。我們先來探討一下其內存布局。

HashTable採用了模板類形式，其成員變數prefix_size和element_size分別代表哈希表中每個元素的大小以及前綴部分的大小。這為實現靈活的存儲提供了基礎。

接下來，我們對外部定義的內容進行深入分析。首先是Allocate函數，它負責創建一個新的哈希表。該操作是哈希表創建過程中的核心步驟，為後續的插入和查找操作提供了物質基礎。

緊接著是FindInsertionEntry函數，該函數通過計算給定鍵的哈希值來確定插入位置的索引。值得注意的是，哈希表的內存布局中，初始部分用於存儲額外的數據，因此真正元素的存儲從第n個元素開始。函數返回的索引需要進一步轉換為真正的偏移量。

為了適應數據量的增長，EnsureCapacity函數實現了哈希表的擴容操作。這一機制確保了在數據量不斷增大的情況下，哈希表能夠高效地容納更多元素，從而維持其性能。

最後是FindEntry函數，它通過鍵值查找對應位置。找到的位置是相對位置，實際操作時還需要計算出真正的存儲位置。這一過程體現了哈希表查找操作的高效性。

綜上所述，通過上述功能的協同作用，v8中的HashTable實現了靈活、高效的數據存儲與管理，為JavaScript引擎提供了強大且快速的哈希表支持。