描述

哈希表容量的大小在一开始是不确定的。如果哈希表存储的元素太多（如超过容量的十分之一），我们应该将哈希表容量扩大一倍，并将所有的哈希值重新安排。
假设你有如下一哈希表：
size=3, capacity=4

 [null, 21, 14, null]
        ↓    ↓
        9   null
        ↓
      null

哈希函数为：

 int hashcode(int key, int capacity) {
      return key % capacity;
 }

这里有三个数字9，14，21，其中21和9共享同一个位置因为它们有相同的哈希值1
(21 % 4 = 9 % 4 = 1)。我们将它们存储在同一个链表中。
重建哈希表，将容量扩大一倍，我们将会得到：
size=3, capacity=8
index: 0 1 2 3 4 5 6 7
hash : [null, 9, null, null, null, 21, 14, null]
给定一个哈希表，返回重哈希后的哈希表。

注意事项

哈希表中负整数的下标位置可以通过下列方式计算：
C++/Java：如果你直接计算-4 % 3，你会得到-1，你可以应用函数：
a % b = (a % b + b) % b得到一个非负整数。
正整数套用公式，值和直接模上hashTable是一样的
Python：你可以直接用-1 % 3，你可以自动得到2。

样例

给出 [null, 21->9->null, 14->null, null]
返回 [null, 9->null, null, null, null, 21->null, 14->null, null]

题目描述的是 Open Hashing，是多个关键字对一个值，还有一种叫 Close Hashing，是一对一形式，如果当前 key 对应的 hash 表位置已经存在一个 key了，则把当前 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 表里，计算新的下标
                 * (防止负数下标出现)
                 */
                int newindex
                 = (hashTable[i].val % newcapacity + newcapacity) % newcapacity;
                if (newTable[newindex] == null) {
                    // copy 原来 hash 表的值
                    newTable[newindex] = new ListNode(hashTable[i].val);
                   /* newTable[newindex].next = null;
                    * 计算得到的 newindex 是在新建的 hash 表中的 index,
                    * 如果新建的表中的这个 index 不为空，
                    * 也就是已经有结点存在的情况下，
                    * 要将这个结点加在已经存在的链表的末尾
                    */
                } else {
                    ListNode dummy = newTable[newindex];
                    while (dummy.next != null) {
                        dummy = dummy.next;
                    }
                    dummy.next = new ListNode(hashTable[i].val);
                }
                // 移到原 hashTable[i] 处链表的下一个结点
                hashTable[i] = hashTable[i].next;
            }
        }
        return newTable;
    }
}