哈希表容量的大小在一開(kāi)始是不確定的米丘。如果哈希表存儲(chǔ)的元素太多（如超過(guò)容量的十分之一）蚕甥，我們應(yīng)該將哈希表容量擴(kuò)大一倍，并將所有的哈希值重新安排炕舵。
假設(shè)你有如下一哈希表：
size=3, capacity=4
[null, 21, 14, null]
↓ ↓
9 null
↓
null
哈希函數(shù)為：
int hashcode(int key, int capacity) {
return key % capacity;
}
這里有三個(gè)數(shù)字9何之，14，21咽筋，其中21和9共享同一個(gè)位置因?yàn)樗鼈冇邢嗤墓Ｖ?
(21 % 4 = 9 % 4 = 1)溶推。我們將它們存儲(chǔ)在同一個(gè)鏈表中。
重建哈希表奸攻，將容量擴(kuò)大一倍蒜危，我們將會(huì)得到：
size=3, capacity=8
index: 0 1 2 3 4 5 6 7
hash : [null, 9, null, null, null, 21, 14, null]
給定一個(gè)哈希表，返回重哈希后的哈希表睹耐。
注意事項(xiàng)
哈希表中負(fù)整數(shù)的下標(biāo)位置可以通過(guò)下列方式計(jì)算：
C++/Java：如果你直接計(jì)算-4 % 3辐赞，你會(huì)得到-1，你可以應(yīng)用函數(shù)：
a % b = (a % b + b) % b得到一個(gè)非負(fù)整數(shù)硝训。
正整數(shù)套用公式响委，值和直接模上hashTable是一樣的
Python：你可以直接用-1 % 3，你可以自動(dòng)得到2窖梁。
樣例
給出 [null, 21->9->null, 14->null, null]
返回 [null, 9->null, null, null, null, 21->null, 14->null, null]
題目描述的是 Open Hashing赘风，是多個(gè)關(guān)鍵字對(duì)一個(gè)值，還有一種叫 Close Hashing窄绒，是一對(duì)一形式贝次，如果當(dāng)前 key 對(duì)應(yīng)的 hash 表位置已經(jīng)存在一個(gè) key了，則把當(dāng)前 key 存到旁邊空位
代碼
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param hashTable: A list of The first node of linked list
* @return: A list of The first node of linked list which have twice size
*/
public ListNode[] rehashing(ListNode[] hashTable) {
if (hashTable.length <= 0) {
return hashTable;
}
int newcapacity = 2 * hashTable.length;
ListNode[] newTable = new ListNode[newcapacity];
for (int i = 0; i < hashTable.length; i++) {
while (hashTable[i] != null) {
/* 將 hash 表中原本的值映射到新的 hash 表里彰导，計(jì)算新的下標(biāo)
* (防止負(fù)數(shù)下標(biāo)出現(xiàn))
*/
int newindex
= (hashTable[i].val % newcapacity + newcapacity) % newcapacity;
if (newTable[newindex] == null) {
// copy 原來(lái) hash 表的值
newTable[newindex] = new ListNode(hashTable[i].val);
/* newTable[newindex].next = null;
* 計(jì)算得到的 newindex 是在新建的 hash 表中的 index,
* 如果新建的表中的這個(gè) index 不為空蛔翅，
* 也就是已經(jīng)有結(jié)點(diǎn)存在的情況下，
* 要將這個(gè)結(jié)點(diǎn)加在已經(jīng)存在的鏈表的末尾
*/
} else {
ListNode dummy = newTable[newindex];
while (dummy.next != null) {
dummy = dummy.next;
}
dummy.next = new ListNode(hashTable[i].val);
}
// 移到原 hashTable[i] 處鏈表的下一個(gè)結(jié)點(diǎn)
hashTable[i] = hashTable[i].next;
}
}
return newTable;
}
}
