size=3, capacity=4
[null, 21->9->null, 14->null, null]
The hash function is:
int hashcode(int key, int capacity) {
return key % capacity;
}
}
here we have three number, 9, 14 and 21, where 21 and 9 share the same position as they all have the same hashcode 1 (21 % 4 = 9 % 4 = 1). We store them in the hash table by linked list.
rehashing this hash table, double the capacity, you will get:
size=3, capacity=8
index: 0 1 2 3 4 5 6 7
hash table: [null, 9, null, null, null, 21, 14, null]
Given the original hash table, return the new hash table after rehashing .
Example
Given [null, 21->9->null, 14->null, null], return [null, 9->null, null, null, null, 21->null, 14->null, null]
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @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
*/
vector<ListNode*> rehashing(vector<ListNode*> hashTable) {
int n = hashTable.size();
int nn = 2*n;
vector<ListNode*> headTable(nn);
vector<ListNode*> tailTable(nn);
for(int i = 0; i < n; i++)
{
ListNode *list = hashTable[i];
while(list != NULL)
{
int indx = list->val%nn;
// important, list->val can be negative
if (indx < 0) indx += nn;
if (tailTable[indx])
tailTable[indx]->next = list;
tailTable[indx] = list;
if (!headTable[indx]) headTable[indx] = list;
ListNode *t = list;
list = t->next;
t->next = NULL;
}
}
return headTable;
}
};
No comments:
Post a Comment