-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRehashing.java
More file actions
39 lines (36 loc) · 1.13 KB
/
Rehashing.java
File metadata and controls
39 lines (36 loc) · 1.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Rehashing {
/**
* @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 == null || hashTable.length == 0) {
return hashTable;
}
int newCap = hashTable.length * 2;
ListNode[] newHashTable = new ListNode[newCap];
for (ListNode head: hashTable) {
ListNode cur = head;
while (cur != null) {
add(newHashTable, hashcode(cur.val, newCap), cur.val);
cur = cur.next;
}
}
return newHashTable;
}
private void add(ListNode[] tbl, int idx, int val) {
if (tbl[idx] == null) {
tbl[idx] = new ListNode(val);
return;
}
ListNode cur = tbl[idx];
while (cur.next != null) {
cur = cur.next;
}
cur.next = new ListNode(val);
return;
}
private int hashcode(int key, int cap) {
return (key % cap + cap) % cap; // to handle negative number
}
}