跳轉至
紙質書（簡體中文版）已發行，詳情請見這裡

# 6.5 練習

## 6.5.1 知識鞏固

### 1. 發生雜湊衝突後怎樣查詢

一個雜湊表有 5 個桶，雜湊函式為 \(h(x)=x \bmod 5\)，衝突時把元素依次放進該桶的串列中。 依次插入 `[1, 6, 11, 7]`：

1. 寫出 0～4 號桶中的內容；
2. 查詢 6 時會先進入哪個桶，並依次檢查哪些元素？
3. 根據第 1 問寫出的桶內容，後插入的元素是否覆蓋了先插入的元素？結合這種衝突處理方式說明理由。

參考答案

1. 因為 \(1\bmod5=6\bmod5=11\bmod5=1\)，而 \(7\bmod5=2\)，各桶為：

       0: []
       1: [1, 6, 11]
       2: [7]
       3: []
       4: []

2. 查詢 6 時先進入 1 號桶，再依次比較 1、6，第二次比較時找到目標。

3. 雜湊值相同只表示它們落入同一個桶，並不表示這些元素相等。鏈式位址把衝突元素都儲存在桶內， 查詢時再逐個比較，因此 1、6、11 不會互相覆蓋。

### 2. 雜湊表擴容後元素去哪兒

一個使用鏈式位址的雜湊表原有 5 個桶，雜湊函式為 \(h(x)=x\bmod5\)。 鍵 `[1, 6, 11]` 都在 1 號桶中。

現在把雜湊表擴容為 7 個桶，雜湊函式相應變為 \(h(x)=x\bmod7\)：

1. 分別計算 1、6、11 的新桶號。
2. 擴容後哪些桶中有元素？
3. 擴容時能否把原來 1 號桶中的串列原樣複製到新的 1 號桶？結合第 1、2 問的結果說明理由。

參考答案

1. 新桶號分別為：

   - \(1\bmod7=1\)；
   - \(6\bmod7=6\)；
   - \(11\bmod7=4\)。

2. 1 號桶儲存 1，4 號桶儲存 11，6 號桶儲存 6。三個鍵不再擠在同一個桶中。

3. 不能原樣複製。桶號由“鍵對桶數取餘”得到。桶數從 5 變成 7 後，同一個鍵的新桶號可能改變， 因此必須重新計算每個鍵的位置。若把舊的 1 號桶原樣複製過去，之後按新公式查詢 6 和 11 時， 會分別前往 6 號桶和 4 號桶，從而找不到它們。

### 3. 刪除 6 後還能找到 11 嗎

一個雜湊表有 5 個位置，索引為 `0～4`，雜湊函式為 \(h(x)=x\bmod5\)。 發生衝突時，從雜湊函式算出的索引開始，向右尋找第一個空位。

依次插入 `[1, 6, 11]`：

1. 三個數最終分別放在哪個索引？
2. 查詢 11 時，會依次檢查哪些索引？
3. 如果刪除 6 時直接把它的位置改成“從未使用的空位”，而查詢遇到空位就停止， 再查詢 11 時會發生什麼？這個查詢結果是否正確？如果有問題，應怎樣避免？

參考答案

1. 1 放在索引 1。6 也對映到索引 1，發生衝突後放在索引 2。 11 同樣從索引 1 開始，依次跳過已佔用的索引 1、2，最終放在索引 3。

2. 查詢 11 時依次檢查索引 `1、2、3`，在索引 3 找到它。

3. 如果把索引 2 改成表示“從未使用”的空位，查詢 11 時檢查索引 1 後就會在索引 2 停止， 從而錯誤地認為 11 不存在。刪除時應留下“已刪除”標記： 查詢遇到該標記時繼續檢查下一個索引（越過索引 4 後回到索引 0），而以後的插入仍可重新使用這個位置。

## 6.5.2 程式設計練習

### 1. 比較兩個字串的字元組成

給定兩個只含小寫英文字母的字串 `s` 和 `t`。 可以任意調整 `s` 中字元的位置，但不能新增、刪除或替換字元。

請判斷調整後能否得到 `t`；可以則返回 `true`，否則返回 `false`。 請使用雜湊表記錄各字母的出現次數，不對字串中的字元排序。

解題提示

1. 兩個字串長度不同，它們的字元組成一定不同
2. 用雜湊表記錄每種字母的數量；掃描 s 時把對應計數加 1
3. 掃描 t 時把對應計數減 1；所有計數最終都為 0，字元組成才相同

LeetCode 題目解析

##### 歡迎在評論區留下你的見解、問題或建議