美团面试题： 哈希表是怎么扩容的？

今天咱们聊聊哈希表扩容的问题，顺便看看代码中是怎么实现的。别担心，这不是“计算机科学家”高谈阔论的时间，我会尽量用通俗的语言和实际例子帮你理解。

哈希表（Hash Table）的扩容是一个重要机制，它直接关系到性能。我们都知道，哈希表的核心思想是通过一个哈希函数，将键映射到一个数组中。但是，随着数据的增多，冲突难免增多，扩容就成了解决问题的办法。

哈希表的扩容流程

大部分哈希表实现（比如 Redis 的字典）在扩容时会经历以下三个步骤：

1. 给新哈希表分配更大的空间，通常是原哈希表容量的两倍。
2. 将旧哈希表中的数据迁移到新哈希表中。
3. 迁移完成后释放旧哈希表的内存，并用新的哈希表替代。

如果仅仅是这样，问题看起来似乎不大。但如果数据量非常大，迁移的过程会变得非常耗时，从而影响服务性能。

Redis 的渐进式 rehash 策略

Redis 采用了一种聪明的策略，称为“渐进式 rehash”，它的核心思想是将数据迁移的工作分摊到多个操作中，避免一次性大量数据拷贝导致的性能问题。

让我们分步骤看看这个过程：

1. 分配新哈希表的空间：当扩容触发时，Redis 为新的哈希表分配空间，但暂时不把所有数据一次性迁移过去。
2. 分摊迁移操作：在处理客户端请求（比如新增、查找、删除）时，每次操作都会顺便迁移部分数据到新的哈希表。这样，迁移工作和正常的服务请求并行进行。
3. 完成迁移：随着操作的增加，最终旧哈希表的数据会全部迁移到新哈希表中，旧哈希表的内存也会被释放。

这个策略巧妙地将迁移开销分摊到多个请求中，最大限度减少了对服务性能的影响。

下面，我们用 Java 的 HashMap 来模拟 Redis 渐进式 rehash 的过程。虽然 Java 中没有渐进式 rehash，但可以通过代码演示其原理。

import java.util.HashMap;
import java.util.Map;
public class ProgressiveRehashDemo {
    static class ProgressiveRehash<K, V> {
        private Map<K, V> currentTable = new HashMap<>();
        private Map<K, V> newTable = null;
        private int rehashIndex = 0;
        public void put(K key, V value) {
            if (newTable != null) {
                // 渐进式迁移
                migrate();
                newTable.put(key, value);
            } else {
                currentTable.put(key, value);
                // 模拟触发扩容
                if (currentTable.size() > 10) {
                    startRehash();
                }
            }
        }
        public V get(K key) {
            if (newTable != null) {
                migrate();
                if (newTable.containsKey(key)) {
                    return newTable.get(key);
                }
            }
            return currentTable.get(key);
        }
        private void startRehash() {
            newTable = new HashMap<>(currentTable.size() * 2);
            rehashIndex = 0;
        }
        private void migrate() {
            // 每次迁移一个键值对
            if (rehashIndex < currentTable.size()) {
                K key = (K) currentTable.keySet().toArray()[rehashIndex];
                newTable.put(key, currentTable.get(key));
                rehashIndex++;
                if (rehashIndex >= currentTable.size()) {
                    // 完成迁移
                    currentTable = newTable;
                    newTable = null;
                }
            }
        }
    }
    public static void main(String[] args) {
        ProgressiveRehash<String, String> rehashDemo = new ProgressiveRehash<>();
        for (int i = 0; i < 15; i++) {
            rehashDemo.put("key" + i, "value" + i);
            System.out.println("Added key" + i);
        }
        System.out.println("Get key5: " + rehashDemo.get("key5"));
    }
}

这段代码展示了渐进式 rehash 的思想。ProgressiveRehash 模拟了 Redis 渐进式 rehash 的关键步骤：在触发扩容时逐步迁移数据，避免一次性迁移。

在面试中，关于哈希表扩容的问题，你可以这样回答：

哈希表扩容通常涉及新表分配、数据迁移和释放旧表三步。但如果数据量大，一次性迁移会导致性能问题。为了解决这个问题，Redis 使用了“渐进式 rehash”，它通过将迁移工作分摊到多次操作中实现性能优化。

在迁移期间，新增的数据直接写入新表，查找和删除操作会在两个表中查找，最终旧表被清空并释放。这个设计有效地平衡了扩容对性能的影响。