文章目录1 题目2 解决方案2.1 思路2.3 时间复杂度2.4 空间复杂度3 源码1 题目题目重哈希Rehashing描述哈希表容量的大小在一开始是不确定的。如果哈希表存储的元素太多如超过容量的十分之一我们应该将哈希表容量扩大一倍并将所有的哈希值重新安排。给定一个哈希表返回重哈希后的哈希表。// 哈希函数 int hashcode(int key, int capacity) { return key % capacity; }lintcode题号——129难度——medium样例1输入有如下一哈希表 size3, capacity4 [null, 21, 14, null] ↓ ↓ 9 null ↓ null 输出重建哈希表将容量扩大一倍我们将会得到 size3, capacity8 index: 0 1 2 3 4 5 6 7 hash : [null, 9, null, null, null, 21, 14, null] 解释 原哈希表中有三个数字91421其中21和9共享同一个位置因为它们有相同的哈希值1(21 % 4 9 % 4 1)。我们将它们存储在同一个链表中。新哈希表中没有冲突它们被放在了不同的位置。2 解决方案2.1 思路哈希表的扩容容器大小不够用的时候新建一个容量翻倍的新容器对原容器的所有数据重新按照哈希函数这里是按照open hashing的方式进行在哈希表的元素位置上放置链表需要逐个找到原哈希表内的数值一一处理。closed hashing一个位置只放一个元素冲突的元素向后寻找空位放下。缺点由于find时有些元素被当作寻找正确元素的桥梁所以在元素删除时候不能直接置空而改为标记为delete依然充当桥梁多次操作后可能产生很多delete位置影响性能open hashing一个位置存放一个链表新元素插入时从表头插入find时不需要向后寻找只需要遍历该位置的链表即可。哈希表容量哈希表的空间通常远大于需要存储的序列的元素个数哈希size 数组size通常大一个数量级当哈希表的饱和度大于1/10的时候则需要rehash。2.3 时间复杂度遍历原哈希表中的所有元素所以时间复杂度为O(n)。2.4 空间复杂度空间复杂度为O(1)。3 源码细节新建一个哈希表并resize为原哈希表size的两倍遍历原表的所有数值按照哈希函数重新放入新表。向新表中添加的节点最好重新new出来不要使用原来的。C版本/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this-val val; * this-next NULL; * } * } */ /** * 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 */ vectorListNode* rehashing(vectorListNode* hashTable) { // write your code here vectorListNode * result; result.resize(hashTable.size() * 2, nullptr); for (auto it : hashTable) { while (it ! nullptr) { addNodeToNew(result, it-val); it it-next; } } return result; } // 向新哈希表插入值 void addNodeToNew(vectorListNode * hashTable, int val) { int capacity hashTable.size(); int position hashcode(val, capacity); // 根据哈希函数计算位置 if (hashTable.at(position) nullptr) { hashTable.at(position) new ListNode(val); } else { addListNodeToNew(hashTable.at(position), val); // 在链表尾部插入节点 //ListNode * curNew new ListNode(val); // 也可以直接在链表头部插入节点 //ListNode * temp hashTable.at(position); //curNew-next temp; //hashTable.at(position) curNew; } } // 在当前链表尾部插入新节点 void addListNodeToNew(ListNode * cur, int val) { if (cur-next nullptr) // 如果没有后续节点 { cur-next new ListNode(val); // 直接插入 } else { addListNodeToNew(cur-next, val); // 递归找到最后一个位置再插入 } } // 哈希函数 int hashcode(int key, int capacity) { int result key % capacity; if (result 0) { result capacity; } return result; }
)
