哈希表基礎
哈希表的英文叫“Hash Table”如筛，我們平時也叫它“散列表”或者“Hash 表”碎连，是一種常用的數(shù)據(jù)結構。Java中的HashMap函筋、HashTable就是基于哈希表實現(xiàn)的。
為了學習哈希表圣拄，我們先從LeetCode上一個的問題開始：
這是LeetCode上的第387號問題：字符串中的第一個唯一字符荣刑。需求是：給定一個字符串措嵌，找到它的第一個不重復的字符与柑，并返回它的索引谤辜。如果不存在，則返回 -1价捧。案例：
s = "leetcode"
返回 0
s = "loveleetcode"
返回 2
這道題相對來說比較簡單丑念，解題思路也比較多。這里給出的一種思路就是聲明一個長度為26的整型數(shù)組干旧，該數(shù)組的索引 0 ~ 1 就對應著字母 a ~ z渠欺。首先妹蔽，遍歷目標字符串椎眯，通過計算 char - 'a' 得到字符所對應的數(shù)組索引，并將該索引的元素進行+1胳岂，這樣就實現(xiàn)了對出現(xiàn)的字符進行計數(shù)编整。最后，再遍歷一次目標字符串乳丰，同樣計算 char - 'a' 得到對應的數(shù)組索引掌测，并判斷該索引位置的數(shù)值是否為1，為1就代表已經找到第一個不重復的字符所在的索引了产园。
具體的實現(xiàn)代碼如下：
public int firstUniqChar(String s) {
int[] freq = new int[26];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
if (freq[s.charAt(i) - 'a'] == 1) {
return i;
}
}
return -1;
}
實際上這就是一種典型的哈希表思想汞斧，因為其中的 int[26] freq 就是一個哈希表。通過這個數(shù)組什燕，我們建立了每個字符和一個數(shù)字之間的映射關系粘勒。
而 s.charAt(i) - 'a' 則是一個哈希函數(shù)，所謂哈希函數(shù)就是可以基于某種規(guī)則對數(shù)據(jù)進行計算得到數(shù)據(jù)所映射的位置屎即。在我們這個例子中庙睡，“數(shù)據(jù)”指的是字符串中的字符，“位置”則指的是數(shù)組中的索引技俐。
通過這個簡單的計算我們就能得到字符所對應的數(shù)組索引乘陪，進而得到字符所出現(xiàn)的次數(shù)，看得出來這個操作的時間復雜度是 雕擂。因此啡邑，訪問哈希表的時間復雜度也就是
。
哈希表用的是數(shù)組支持按照下標隨機訪問數(shù)據(jù)的特性井赌，實現(xiàn)高效的數(shù)據(jù)操作谤逼。所以哈希表其實就是數(shù)組的一種擴展募寨，由數(shù)組演化而來∩可以說拔鹰，如果沒有數(shù)組，就沒有哈希表贵涵。
稍微總結一下哈希表就是：一種基于數(shù)組實現(xiàn)的線性結構列肢，通過哈希函數(shù)來實現(xiàn)尋址，能夠建立一種“數(shù)據(jù)”與“位置”的映射關系宾茂。利用的是數(shù)組支持按照下標隨機訪問元素的特性瓷马，通常情況下查詢操作具有 的時間復雜度。
哈希函數(shù)的設計
從上一小節(jié)的例子我們可以看到跨晴，哈希函數(shù)在哈希表中起著非常關鍵的作用欧聘。在該例子中，哈希函數(shù)就是一個簡單的運算端盆，比較簡單怀骤，也比較容易想到。
但是如果要設計一個“工業(yè)級”的哈希函數(shù)還是比較難的焕妙，對于一個通用的數(shù)據(jù)結構蒋伦，我們需要考慮不同的數(shù)據(jù)類型：字符串、浮點數(shù)焚鹊、日期等以及不同的數(shù)據(jù)格式：身份證號痕届、單詞、車牌號等末患，對于這種不同的情況如何得到能用于哈希計算的依據(jù)研叫。所以對于一些特殊領域，有特殊領域的哈希函數(shù)設計方式璧针，甚至還有專門的論文嚷炉。
除此之外，我們還要設計哈希函數(shù)的計算規(guī)則陈莽，如何使數(shù)據(jù)能在數(shù)組中均勻的分布渤昌。然后還得思考如何解決哈希沖突，因為要想找到一個不同的 key 對應的哈希值都不一樣的哈希函數(shù)走搁，幾乎是不可能的独柑。即便像業(yè)界著名的MD5、SHA私植、CRC等哈希算法忌栅，也無法完全避免這種哈希沖突。而且，因為數(shù)組的存儲空間有限索绪，也會加大哈希沖突的概率湖员。
這里總結下幾點哈希函數(shù)設計的基本要求：
- 哈希函數(shù)計算得到的哈希值是一個非負整數(shù)
- 高效性：計算高效簡便
- 均勻性：哈希值均勻分布
- 一致性：
- 如果
，那
- 如果
瑞驱，那
- 如果
對于 “如果 娘摔，那
” 只是邏輯上的體現(xiàn)，因為我們之前也說了唤反，在真實情況下幾乎無法找到一個完美的無沖突的散列函數(shù)凳寺，即便能找到，付出的時間成本彤侍、計算成本也是很大的肠缨，所以針對散列沖突問題，我們需要通過其他途徑來解決盏阶。
取模在哈希函數(shù)中的應用
這里介紹一種簡單的哈希函數(shù)設計思路晒奕，那就是取模。對一個合適的數(shù)進行取模能得到一個小范圍的整數(shù)名斟，即便得到負整數(shù)也能通過簡單的偏移規(guī)則轉換成正整數(shù)脑慧。但你可能會有疑問了，數(shù)據(jù)類型有各種各樣蒸眠，都能進行取模嗎漾橙？應該對什么樣的數(shù)進行取模杆融？
對于第一個問題楞卡，其實對于各種各樣的數(shù)據(jù)類型，我們都可以將其轉換為相應的整數(shù)脾歇。對于第二個問題蒋腮，一般需要視情況而定。小整數(shù)對什么數(shù)取模差別不大藕各，甚至都不需要取模池摧，直接每個數(shù)字對應一個索引。如同上一小節(jié)中的例子激况，每個單詞對應一個數(shù)組索引就可以了作彤。
而對于大整型，例如身份證號乌逐、手機號等竭讳，這種無法直接對應索引的就需要進行取模了，一個簡單的解決辦法就是模一個素數(shù)浙踢。至于為什么是素數(shù)绢慢，這是一個數(shù)學上的問題，超出了本文的討論范圍洛波，有興趣的可以自行了解一下胰舆。下面這個網站列出了不同規(guī)模的整數(shù)用于取模的最佳素數(shù)：
同樣的骚露，浮點型也可以轉換成整型進行取模，因為在計算機中都是32位或者64位的二進制表示缚窿，只不過計算機解析成了浮點數(shù)棘幸，所以轉成整型處理即可。
字符串類型則相對來說稍微復雜點倦零，但同樣也是轉成整型够话，只是套路不太一樣。對于數(shù)字內容的字符串光绕，例如 166 女嘲，我們可以將其每個字符想象成十進制的表示法，通過如下方式轉換成整數(shù)：
166 = 1 * 10^2 + 6 * 10^1 + 6 * 10^0
這個計算很簡單诞帐，因為 char 類型是可運算的欣尼，將每一個字符乘以進制數(shù)的 n 次方再加起來就可以了，這里的 n 取值是該字符后面的字符數(shù)量停蕉。例如愕鼓，1 這個字符它后面還有兩個字符，那么這個 n 就是 2 慧起，然后因為是 10 進制表示菇晃，所以其進制數(shù)是 10，也就得出了 1 * 10^2蚓挤，其他字符以此類推磺送，最后再進行相加就能將該字符串轉換成整數(shù)了。
同理灿意，字符串內容為單詞的計算方式也是一樣估灿，只不過進制數(shù)需要改變一下，我們可以將字母看成是26進制的缤剧。如下示例：
code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0
這個進制數(shù)根據(jù)字符串內容不同是不固定的馅袁，例如要包含大寫字母，可能進制數(shù)就需要設置為52荒辕，要包含標點符號汗销、特殊符號等還需要將這個值設置得再大一些〉种希總結成公式大概就是這樣：
code = c * B^3 + o * B^2 + d * B^1 + e * B^0
因此弛针，哈希函數(shù)的表示如下：
hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M
這個計算方式還有優(yōu)化的空間，只需要簡單的變換一下就能節(jié)省一些計算估脆。如下所示：
hash(code) = ((((c * B) + o) * B + d) * B + e) % M
但是這樣的計算對于整型來說還會有溢出的問題钦奋，所以我們需要將取模計算放進去，最終得出的哈希函數(shù)如下：
hash(code) = ((((c % M) * B + o) % M * B + d) % M * B + e) % M
轉換成代碼的表達如下：
int hash = 0;
for(int i = 0; i < s.length(); i++) {
hash = (hash * B + s.charAt(i)) % M
}
解決了字符串的取模問題，復合類型也就簡單了付材，因為和字符串類似朦拖。我們可以通過類似于 toString 的方式將復合類型轉換為字符串，然后再根據(jù)上述規(guī)則轉換成整型后取模厌衔。例如璧帝，日期類型：
Date: year, month, day, hour
hash(date) = ((((date.year % M) * B + date.month) % M * B + date.day) % M * B + date.hour) % M
Java中的 hashCode 方法
我們知道在Java中，可以通過重寫 hashCode 方法來提供一個對象的哈希值富寿。并且基礎數(shù)據(jù)類型的包裝類如Integer睬隶、Double、String等都已經重寫了 hashCode 方法页徐，對于這些類型直接調用即可苏潜。
對于我們自己定義的類型來說，就需要自行重寫 hashCode 方法了变勇。而通常一個對象里的字段都由基礎類型或其包裝類組成恤左，因此也可以利用這些類型已有的 hashCode 方法。如下示例：
public class Student {
int grade;
int cls;
String firstName;
String lastName;
@Override
public int hashCode() {
// 哪些字段參與計算
Object[] a = new Object[]{grade, cls, firstName, lastName};
// 按照實際情況取合適的進制數(shù)搀绣，這里是仿照jdk源碼取的31
int B = 31;
int result = 1;
for (Object element : a) {
result = result * B + (element == null ? 0 : element.hashCode());
}
return result;
}
}
重寫了 hashCode 方法后飞袋，我們還需要重寫 equals 方法。因為不同的兩個對象有可能哈希值是相等的链患，這也就是哈希沖突巧鸭。此時我們就需要進一步通過 equals 方法來比較兩個對象的內容是否相等，以此來區(qū)別它們是不是同一個對象麻捻。由此纲仍，我們可以得出一個結論：hashCode 相等不一定是同一個對象，hashCode 和 equals 都相等的情況下才能認為是同一個對象芯肤， 而 equals 相等時 hashCode 必然相等巷折。
重寫 equals 方法也是有套路的，而且現(xiàn)在大部分IDE都支持自動生成崖咨，這里就不過多解釋了。代碼如下：
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Student student = (Student) o;
return grade == student.grade &&
cls == student.cls &&
Objects.equals(firstName, student.firstName) &&
Objects.equals(lastName, student.lastName);
}
鏈地址法 Separate Chaining
現(xiàn)在我們已經了解清楚了哈希函數(shù)的設計油吭，以及在Java中如何取得一個對象的哈希值击蹲、如何比較兩個對象是否相等。接下來我們就可以進一步看看如何解決哈希沖突的問題了婉宰，我們常用的哈希沖突解決方法有兩類歌豺，開放尋址法（open addressing）和鏈地址法（separate chaining）也叫鏈表法或拉鏈法。
開放尋址法的核心思想是心包，如果出現(xiàn)了散列沖突类咧，我們就重新探測一個空閑位置，將其插入。但這種方法并不常用痕惋，因為相對復雜且局限性大区宇，一般用于小數(shù)據(jù)量的情況，Java中的 ThreadLocalMap 用的是這種方法值戳。
而鏈表法則是一種更加常用的哈希沖突解決辦法议谷，相比開放尋址法，它要簡單很多堕虹。Java中的 HashMap卧晓、HashTable 就是用的這種方法。我們來看這個圖赴捞，在哈希表中逼裆，每個“桶（bucket）”或者“槽（slot）”會對應一條鏈表，所有哈希值相同的元素我們都放到相同槽位對應的鏈表中：
當插入的時候赦政，我們只需要通過哈希函數(shù)計算出對應的哈希槽位波附，將其插入到對應鏈表中即可，所以插入的時間復雜度是 昼钻。當查找掸屡、刪除一個元素時，我們同樣通過哈希函數(shù)計算出對應的槽然评，然后遍歷鏈表查找或者刪除仅财。那查找或刪除操作的時間復雜度是多少呢？
實際上碗淌，這兩個操作的時間復雜度跟鏈表的長度 k 成正比盏求，也就是 。對于分布比較均勻的哈希函數(shù)來說亿眠，理論上講碎罚，
，其中 n 表示哈希表中數(shù)據(jù)的個數(shù)纳像，m 表示哈希表中“槽”的個數(shù)荆烈。
當哈希沖突比較大，鏈表達到一定長度時竟趾，我們可以將其轉換成一棵樹憔购，例如紅黑樹，避免查詢效率退化到 岔帽。這也是Java8為什么會在
HashMap 中引入紅黑樹的原因玫鸟。
實現(xiàn)屬于我們自己的哈希表
有了前面的鋪墊后，我們對哈希表的幾個核心要點有了一定的了解犀勒，現(xiàn)在我們就來實現(xiàn)屬于我們自己的哈希表屎飘。具體代碼如下：
package hash;
import java.util.TreeMap;
/**
* 哈希表
*
* @author 01
* @date 2021-01-20
**/
public class HashTable<K, V> {
/**
* 借助TreeMap數(shù)組作為實際的存儲容器
* 目的是不需要自己去實現(xiàn)紅黑樹了妥曲，只需要關注哈希表實現(xiàn)本身
*/
private TreeMap<K, V>[] table;
/**
* 哈希表的大小
*/
private int capacity;
/**
* 元素的個數(shù)
*/
private int size;
public HashTable(int capacity) {
this.capacity = capacity;
this.size = 0;
this.table = new TreeMap[capacity];
// 初始化數(shù)組
for (int i = 0; i < capacity; i++) {
this.table[i] = new TreeMap<>();
}
}
public HashTable() {
// 默認使用一個素數(shù)作為初始大小
this(97);
}
/**
* 哈希函數(shù)，計算出key所對應的數(shù)組索引
*/
private int hash(K key) {
// 消除hashCode的符號钦购，即轉換成正整數(shù)檐盟，因為hashCode有可能是負數(shù)，然后對capacity取模
return (key.hashCode() & Integer.MAX_VALUE) % capacity;
}
public int getSize() {
return size;
}
/**
* 添加元素
*/
public void add(K key, V value) {
TreeMap<K, V> node = table[hash(key)];
if (node.containsKey(key)) {
// key已存在肮雨，則更新
node.put(key, value);
}
// 否則就是新增遵堵，維護下size
node.put(key, value);
size++;
}
/**
* 刪除元素
*/
public V remove(K key) {
TreeMap<K, V> node = table[hash(key)];
V ret = null;
if (node.containsKey(key)) {
ret = node.remove(key);
size--;
}
return ret;
}
/**
* 更新元素
*/
public void set(K key, V value) {
TreeMap<K, V> node = table[hash(key)];
if (!node.containsKey(key)) {
throw new IllegalArgumentException(key + " doesn't exist!");
}
node.put(key, value);
}
/**
* 判斷key是否存在
*/
public boolean containsKey(K key) {
return table[hash(key)].containsKey(key);
}
/**
* 根據(jù)key獲取value
*/
public V get(K key) {
return table[hash(key)].get(key);
}
}
哈希表的動態(tài)空間處理
上一小節(jié)中我們已經實現(xiàn)了一個基礎的哈希表，為了簡化實現(xiàn)使用了Java的 TreeMap 來作為裝載數(shù)據(jù)的容器怨规，省得自己去實現(xiàn)鏈表或紅黑樹了陌宿，讓我們只需要關注哈希表的實現(xiàn)本身。但它依舊是個數(shù)組波丰，我們也還得實現(xiàn)哈希函數(shù)計算出key所對應的數(shù)組索引壳坪，以及相應的增刪查改方法。
正因為我們將 TreeMap 聲明為一個數(shù)組掰烟，所以在初始化后爽蝴，數(shù)組的長度就是固定的了。隨著不斷地添加數(shù)據(jù)纫骑，哈希表中的數(shù)據(jù)越來越密集蝎亚，哈希沖突的概率就會越來越大，從而導致每個 TreeMap 里存儲越來越多的數(shù)據(jù)先馆，會使得哈希表的時間復雜度從 退化至
发框，如果使用的是鏈表的話會退化至
。
為了解決這個問題煤墙，我們就要像實現(xiàn)動態(tài)數(shù)組那樣梅惯，對哈希表實現(xiàn)動態(tài)擴容。擴容到合適的大小后可以減少哈希沖突的概率仿野，將哈希表維持在一個較好的性能水平铣减，這也是設計哈希表時非常關鍵的一個要素。
但是哈希表的動態(tài)擴容不像實現(xiàn)數(shù)組的動態(tài)擴容那么簡單脚作，數(shù)組動態(tài)擴容的條件只需要判斷數(shù)組是否滿了葫哗。而在哈希表中，初始化時就會填滿數(shù)組鳖枕，數(shù)組中存放的是一個個的 TreeMap 魄梯，這里的 TreeMap 可以想象為一顆樹的根節(jié)點，我們添加的元素是掛到 TreeMap 里的宾符。
所以我們的擴容條件就要變成：當數(shù)組中平均每個 TreeMap 承載的元素達到一定的程度時，就進行擴容灭翔。這個“程度”是一個具體的數(shù)值魏烫，通常稱之為負載因子辣苏。即滿足 元素個數(shù) / 數(shù)組長度 >= 負載因子 時，我們就需要對哈希表進行擴容哄褒。同理稀蟋，有擴容就有縮容，我們需要進行一個反向操作呐赡，當滿足 元素個數(shù) / 數(shù)組長度 < 負載因子 時退客，進行縮容。
基于這種方式链嘀，我們改造一下之前的哈希表萌狂，為其添加動態(tài)擴縮容功能。具體代碼如下（僅貼出有改動的代碼）：
public class HashTable<K, V> {
...
/**
* 負載因子
*/
private static final double loadFactor = 0.75;
/**
* 初始容量
*/
private static final int initCapacity = 16;
...
public HashTable() {
this(initCapacity);
}
...
/**
* 添加元素
*/
public void add(K key, V value) {
TreeMap<K, V> node = table[hash(key)];
if (node.containsKey(key)) {
// key已存在怀泊，則更新
node.put(key, value);
}
// 否則就是新增茫藏，維護下size
node.put(key, value);
size++;
// 大于負載因子進行擴容
if (size >= loadFactor * capacity) {
// 每次擴容兩倍
resize(2 * capacity);
}
}
/**
* 刪除元素
*/
public V remove(K key) {
TreeMap<K, V> node = table[hash(key)];
V ret = null;
if (node.containsKey(key)) {
ret = node.remove(key);
size--;
// 小于負載因子進行縮容，并保證數(shù)組長度不小于initCapacity
if (size < loadFactor * capacity && capacity / 2 >= initCapacity) {
// 每次縮容兩倍
resize(capacity / 2);
}
}
return ret;
}
/**
* 動態(tài)擴縮容
*/
private void resize(int newCapacity) {
TreeMap<K, V>[] newTable = new TreeMap[newCapacity];
for (int i = 0; i < newCapacity; i++) {
newTable[i] = new TreeMap<>();
}
this.capacity = newCapacity;
// 將原本數(shù)組中的數(shù)據(jù)遷移到新的數(shù)組中
for (TreeMap<K, V> node : table) {
// 為保證元素能夠均勻分布在新的數(shù)組中霹琼，在遷移元素時务傲，需要對元素重新進行哈希計算
for (Map.Entry<K, V> entry : node.entrySet()) {
newTable[hash(entry.getKey())]
.put(entry.getKey(), entry.getValue());
}
}
this.table = newTable;
}
...
}
哈希表更復雜的動態(tài)空間處理方法
在上一小節(jié)中，我們?yōu)楣１硖砑恿藙討B(tài)擴縮容的功能枣申。你可能會有疑問售葡，每次擴縮容都是原來的兩倍，那么 capacity 不就無法保持是一個素數(shù)了嗎忠藤？是的挟伙，如果只是簡單的設置為兩倍，就無法讓 capacity 保持是一個素數(shù)熄驼，甚至不會是一個對取模友好的數(shù)像寒。這會使得哈希函數(shù)的計算分布不均勻，增加哈希沖突的概率瓜贾。
所以我們可以再對其做進一步的改造诺祸，在對象中聲明一個素數(shù)表，當擴容到不同的規(guī)模時就從該素數(shù)表中取不同的素數(shù)作為新的數(shù)組長度祭芦。最終我們實現(xiàn)的哈希表代碼如下：
package hash;
import java.util.Map;
import java.util.TreeMap;
/**
* 哈希表
*
* @author 01
* @date 2021-01-20
**/
public class HashTable<K, V> {
/**
* 借助TreeMap數(shù)組作為實際的存儲容器
* 目的是不需要自己去實現(xiàn)紅黑樹了筷笨，只需要關注哈希表實現(xiàn)本身
*/
private TreeMap<K, V>[] table;
/**
* 哈希表的大小
*/
private int capacity;
/**
* 負載因子
*/
private static final double loadFactor = 0.75;
/**
* 初始容量所對應的素數(shù)表索引
*/
private int capacityIndex = 0;
/**
* 元素的個數(shù)
*/
private int size;
/**
* 從 https://planetmath.org/goodhashtableprimes 網站
* 中獲取到的不同規(guī)模的整數(shù)用于取模的最佳素數(shù)，我們基于這里的素數(shù)
* 作為擴縮容的大小龟劲，使得每次擴縮容可以將數(shù)組的長度保持始終是素數(shù)
*/
private final int[] capacityArray = {
53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
402653189, 805306457, 1610612741
};
public HashTable() {
this.capacity = capacityArray[capacityIndex];
this.size = 0;
this.table = new TreeMap[capacity];
// 初始化數(shù)組
for (int i = 0; i < capacity; i++) {
this.table[i] = new TreeMap<>();
}
}
/**
* 哈希函數(shù)胃夏，計算出key所對應的數(shù)組索引
*/
private int hash(K key) {
// 消除hashCode的符號，即轉換成正整數(shù)昌跌，因為hashCode有可能是負數(shù)仰禀，然后對 capacity 取模
return (key.hashCode() & Integer.MAX_VALUE) % capacity;
}
public int getSize() {
return size;
}
/**
* 添加元素
*/
public void add(K key, V value) {
TreeMap<K, V> node = table[hash(key)];
if (node.containsKey(key)) {
// key已存在，則更新
node.put(key, value);
}
// 否則就是新增蚕愤，維護下size
node.put(key, value);
size++;
// 大于負載因子進行擴容答恶，并確保不會發(fā)生數(shù)組越界
if (size >= loadFactor * capacity &&
capacityIndex + 1 < capacityArray.length) {
// 每次擴容的大小是下一個素數(shù)
capacityIndex++;
resize(capacityArray[capacityIndex]);
}
}
/**
* 刪除元素
*/
public V remove(K key) {
TreeMap<K, V> node = table[hash(key)];
V ret = null;
if (node.containsKey(key)) {
ret = node.remove(key);
size--;
// 小于負載因子進行縮容饺蚊，并確保不會發(fā)生數(shù)組越界
if (size < loadFactor * capacity && capacityIndex - 1 >= 0) {
// 每次縮容的大小是上一個素數(shù)
capacityIndex--;
resize(capacityArray[capacityIndex]);
}
}
return ret;
}
/**
* 動態(tài)擴縮容
*/
private void resize(int newCapacity) {
TreeMap<K, V>[] newTable = new TreeMap[newCapacity];
for (int i = 0; i < newCapacity; i++) {
newTable[i] = new TreeMap<>();
}
this.capacity = newCapacity;
// 將原本數(shù)組中的數(shù)據(jù)遷移到新的數(shù)組中
for (TreeMap<K, V> node : table) {
// 為保證元素能夠均勻分布在新的數(shù)組中，在遷移元素時悬嗓，需要對元素重新進行哈希計算
for (Map.Entry<K, V> entry : node.entrySet()) {
newTable[hash(entry.getKey())]
.put(entry.getKey(), entry.getValue());
}
}
this.table = newTable;
}
/**
* 更新元素
*/
public void set(K key, V value) {
TreeMap<K, V> node = table[hash(key)];
if (!node.containsKey(key)) {
throw new IllegalArgumentException(key + " doesn't exist!");
}
node.put(key, value);
}
/**
* 判斷key是否存在
*/
public boolean containsKey(K key) {
return table[hash(key)].containsKey(key);
}
/**
* 根據(jù)key獲取value
*/
public V get(K key) {
return table[hash(key)].get(key);
}
}
完成了動態(tài)擴縮容功能后污呼，我們可以簡單分析下添加操作的時間復雜度。插入一個數(shù)據(jù)包竹，最好情況下燕酷，不需要擴容，最好時間復雜度是 周瞎。最壞情況下苗缩，哈希表負載達到負載因子，啟動擴容堰氓，我們需要重新申請內存空間挤渐，重新計算哈希位置，并且搬移數(shù)據(jù)双絮，所以時間復雜度是
浴麻。用攤還分析法，均攤情況下囤攀，時間復雜度接近最好情況软免，就是
。
最后
在學習了哈希表后焚挠，我們認識到哈希表是一個非常高效的數(shù)據(jù)結構膏萧，設計良好的哈希表各個操作的時間復雜度能達到 級別。但在編程領域蝌衔，總是在空間換時間榛泛、時間換空間以及各種 trade-off。所以噩斟，一個數(shù)據(jù)結構或算法在某些方面有良好的表現(xiàn)曹锨，通常也在其他方面做出一定的犧牲。哈希表就是一個典型的空間換時間剃允，組合了不同的數(shù)據(jù)結構沛简，并且犧牲了順序性，換來了
的時間復雜度斥废，這前提還得是設計良好椒楣。
不知道你有沒有發(fā)現(xiàn)，在本文中我們實現(xiàn)的哈希表實際上有一個小 bug牡肉，為了簡化流程只專注于哈希表本身的實現(xiàn)捧灰，我們是直接使用 TreeMap 來存儲數(shù)據(jù)，而 TreeMap 底層是紅黑樹统锤，要求 key 是具有可比較性的凤壁。但在我們的實現(xiàn)中沒有對 key 要求實現(xiàn) Comparable 接口吩屹，所以當存入的 key 是沒有實現(xiàn) Comparable 接口的對象時就會報錯跪另。
你可以嘗試一下解決這個問題拧抖，例如選擇將 TreeMap 替換成 LinkedList，或者傳入一個 Comparator 給 TreeMap 免绿，甚至可以實現(xiàn)自己的鏈表或紅黑樹來替換掉 TreeMap 唧席。
