# 129.Rehashing

## 1.Description(Medium)

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`

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

The hash function is:

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

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`

```
index:   0    1    2    3     4    5    6   7
hash : [null, 9, null, null, null, 21, 14, null]
```

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

### Notice

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.

**Example**

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

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

## 2.Code

此题的难度不大，只需要按照题目的要求实现代码就可以。不过需要注意的是：

1. C++/Java中，不能直接对负数使用取模运算，而需要用等式`a % b = (a % b + b) % b`，让所得到的hash值为非负数。
2. 所得到的新的HashTable中，可能依然存在碰撞，所以仍然需要在对应hashcode位置的ListNode tail上插入新的ListNode。

```
 public ListNode[] rehashing(ListNode[] hashTable) {
        if(hashTable==null || hashTable.length==0){
            return hashTable;
        }

        int capacity=hashTable.length;
        int newcapacity=capacity*2;
        ListNode[] rehashing=new ListNode[newcapacity];

        for(int i=0;i<capacity;i++){
            ListNode head=hashTable[i];
            while(head!=null){
                int index=gethashcode(head.val,newcapacity);
                insertToHashTable(rehashing,index,head.val);
                head=head.next;               
            }         
        }
        return rehashing;
    }

    public int gethashcode(int code,int capacity){
        int hashcode=0;
        if(code<0){
            hashcode=(code%capacity+capacity)%capacity;
        }else{
            hashcode=code%capacity;
        }
        return hashcode;
    }

    public void insertToHashTable(ListNode[] hashTable,int index,int value){
        if(index<hashTable.length){
            ListNode list=hashTable[index];
            if(list==null){
                //这里不能写成这样list=new ListNode(value);否则全部是Null
                hashTable[index]=new ListNode(value);               
            }else{
                while(list.next!=null){
                    list=list.next;
                }
                list.next=new ListNode(value);
            }
        }
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/8.data-structure/129rehashing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.