LintCode 129. Rehashing 原创Java参考解答

LintCode 129. Rehashing 原创Java参考解答


The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys. Say you have a hash table looks like below:

size=3, capacity=4

The hash function is:

here we have three numbers, 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

Given the original hash table, return the new hash table after rehashing .


For negative integer in hash table, the position can be calculated as follow:

  • C++/Java: if you directly calculate -4 % 3 you will get -1. You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
  • Python: you can directly use -1 % 3, you will get 2 automatically.


Given [null, 21->9->null, 14->null, null],

return [null, 9->null, null, null, null, 21->null, 14->null, null]






LintCode All in One 原创题目讲解汇总


电子邮件地址不会被公开。 必填项已用*标注