HashMap HashTable HashSet差別剖析總結

HashMap、HashSet、HashTable之間的差別是Java程式員的一個常見面試題目，在此僅以此部落格記錄，并深入源代碼進行分析：

在分析之前，先将其差別列于下面：

1、HashSet底層采用的是HashMap進行實作的，但是沒有key-value，隻有HashMap的key set的視圖，HashSet不容許重複的對象
Hashtable是基于Dictionary類的，而HashMap是基于Map接口的一個實作
Hashtable裡預設的方法是同步的，而HashMap則是非同步的，是以Hashtable是多線程安全的
HashMap可以将空值作為一個表的條目的key或者value,HashMap中由于鍵不能重複，是以隻有一條記錄的Key可以是空值，而value可以有多個為空，但HashTable不允許null值(鍵與值均不行)
記憶體初始大小不同，HashTable初始大小是11，而HashMap初始大小是16
記憶體擴容時采取的方式也不同，Hashtable采用的是2*old+1,而HashMap是2*old。
哈希值的計算方法不同，Hashtable直接使用的是對象的hashCode,而HashMap則是在對象的hashCode的基礎上還進行了一些變化

源代碼分析：

對于差別1，看下面的源碼

[java] view plain copy

//HashSet類的部份源代碼
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{ //用于類的序列化，可以不用管它
static final long serialVersionUID = -5024744406713321676L;
//從這裡可以看出HashSet類裡面真的是采用HashMap來實作的
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
//這裡是生成一個對象，生成這個對象的作用是将每一個鍵的值均關聯于此對象，以滿足HashMap的鍵值對
private static final Object PRESENT = new Object();
//這裡是一個構造函數，開構生成一個HashMap對象，用來存放資料
public HashSet() {
map = new HashMap<E,Object>();
}

從上面的代碼中得出的結論是HashSet的确是采用HashMap來實作的，而且每一個鍵都關鍵同一個Object類的對象，是以鍵所關聯的值沒有意義，真正有意義的是鍵。而HashMap裡的鍵是不允許重複的，是以1也就很容易明白了。

對于差別2，繼續看源代碼如下

[java] view plain copy

//從這裡可以看得出Hashtable是繼承于Dictionary,實作了Map接口
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {

[java] view plain copy

//這裡可以看出的是HashMap是繼承于AbstractMap類，實作了Map接口
//是以與Hashtable繼承的父類不同
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

差別3，找一個具有針對性的方法看看，這個方法就是put

[java] view plain copy

//Hashtable裡的向集體增加鍵值對的方法，從這裡可以明顯看到的是
//采用了synchronized關鍵字，這個關鍵字的作用就是用于線程的同步操作
//是以下面這個方法對于多線程來說是安全的，但這會影響效率
public synchronized V put(K key, V value) {
// Make sure the value is not null
//如果值為空的，則會抛出異常
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
//獲得鍵值的hashCode,從這裡也可以看得出key!=null,否則的話會抛出異常的呦
int hash = key.hashCode();
//擷取鍵據所在的哈希表的位置
int index = (hash & 0x7FFFFFFF) % tab.length;
//從下面這個循環中可以看出的是，内部實作采用了連結清單，即桶狀結構
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
//如果向Hashtable中增加同一個元素時，則會重新更新元素的值
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
//後面的暫時不用管它，大概的意思就是記憶體的個數少于某個閥值時，進行重新配置設定記憶體
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}

[java] view plain copy

//HashMap中的實作則相對來說要簡單的很多了，如下代碼
//這裡的代碼中沒有synchronize關鍵字，即可以看出，這個關鍵函數不是線程安全的
public V put(K key, V value) {
//對于鍵是空時，将向Map中放值一個null-value構成的鍵值對
//對值卻沒有進行判空處理，意味着可以有多個具有鍵，鍵所對應的值卻為空的元素。
if (key == null)
return putForNullKey(value);
//算出鍵所在的哈希表的位置
int hash = hash(key.hashCode());
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;
}

差別4在上面的代碼中，已經分析了，可以再細看一下

差別5記憶體初化大小不同，看看兩者的源代碼：

[java] view plain copy

public Hashtable() {
//從這裡可以看出，預設的初始化大小11，這裡的11并不是11個位元組，而是11個Entry,這個Entry是
//實作連結清單的關鍵結構
//這裡的0.75代表的是裝載因子
this(11, 0.75f);
}

[java] view plain copy

//這裡均是一些定義
public HashMap() {
//這個預設的裝載因子也是0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
//預設的痤為0.75*16
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
//這裡開始是預設的初始化大小，這裡大小是16
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}

從上面的代碼中，可以看出的是兩者的預設大小是不同的，一個是11，一個是16

差別6記憶體的擴容方式，看一看源代碼也是很清楚的，其實差別是不大的，一個是2*oldCapacity+1, 一個是2*oldCapacity,你說大嗎:）

[java] view plain copy

//Hashtable中調整記憶體的函數，這個函數沒有synchronize關鍵字，但是protected呦
protected void rehash() {
//擷取原來的表大小
int oldCapacity = table.length;
Entry[] oldMap = table;
//設定新的大小為2*oldCapacity+1
int newCapacity = oldCapacity * 2 + 1;
//開設空間
Entry[] newMap = new Entry[newCapacity];
//以下就不用管了。。。
modCount++;
threshold = (int)(newCapacity * loadFactor);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}

[java] view plain copy

//HashMap中要簡單的多了，看看就知道了
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//如果超過了閥值
if (size++ >= threshold)
//就将大小設定為原來的2倍
resize(2 * table.length);
}

對于差別7的哈希值計算方法的不同：

[java] view plain copy

//Hashtable中可以看出的是直接采用關鍵字的hashcode作為哈希值
int hash = key.hashCode();
//然後進行模運算，求出所在嘩然表的位置
int index = (hash & 0x7FFFFFFF) % tab.length;

[java] view plain copy

//HashMap中的實作
//這兩行代碼的意思是先計算hashcode,然後再求其在哈希表的相應位置
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

上面的HashMap中可以看出關鍵在兩個函數hash與indexFor

源碼如下:

[java] view plain copy

static int hash(int h) {
// 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);
return h ^ (h >>> 7) ^ (h >>> 4);
}

[java] view plain copy

//求位于哈希表中的位置
static int indexFor(int h, int length) {
return h & (length-1);

HashMap HashTable HashSet差別剖析總結

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器