实现一个平滑迁移的hashmap?

实现一个平滑迁移（incremental rehashing）的HashMap涉及到在扩容时，将旧的HashMap中的元素逐步迁移到新的HashMap中，而不是一次性完成，这样可以避免扩容时性能的剧烈波动。下面是一个简单的Java实现示例： ```java import java.util.ArrayList; import java.util.List; public class SmoothMigrationHashMap<K, V> { private List<Node<K, V>>[] table; private List<Node<K, V>>[] newTable; private int capacity; private int size; private int rehashIndex; public SmoothMigrationHashMap(int initialCapacity) { this.capacity = initialCapacity; this.table = new ArrayList[capacity]; for (int i = 0; i < capacity; i++) { table[i] = new ArrayList<>(); } this.size = 0; this.rehashIndex = -1; } public V get(K key) { int hash = hash(key, capacity); for (Node<K, V> node : table[hash]) { if (node.key.equals(key)) { return node.value; } } if (newTable != null) { int newHash = hash(key, newTable.length); for (Node<K, V> node : newTable[newHash]) { if (node.key.equals(key)) { return node.value; } } } return null; } public void put(K key, V value) { if (size >= capacity * 0.75 && newTable == null) { startRehashing(); } int hash = hash(key, capacity); for (Node<K, V> node : table[hash]) { if (node.key.equals(key)) { node.value = value; return; } } table[hash].add(new Node<>(key, value)); size++; if (newTable != null) { rehash(); } } private void startRehashing() { newTable = new ArrayList[capacity * 2]; for (int i = 0; i < newTable.length; i++) { newTable[i] = new ArrayList<>(); } rehashIndex = 0; } private void rehash() { int steps = capacity / 10 + 1; // 控制每次迁移的步数，避免单次开销过大 while (steps > 0 && rehashIndex < capacity) { List<Node<K, V>> oldBucket = table[rehashIndex]; if (!oldBucket.isEmpty()) { for (Node<K, V> node : oldBucket) { int newHash = hash(node.key, newTable.length); newTable[newHash].add(node); } oldBucket.clear(); steps--; } rehashIndex++; } if (rehashIndex >= capacity) { table = newTable; newTable = null; capacity *= 2; rehashIndex = -1; } } private int hash(K key, int tableSize) { return Math.abs(key.hashCode() % tableSize); } private static class Node<K, V> { K key; V value; Node(K key, V value) { this.key = key; this.value = value; } } public static void main(String[] args) { SmoothMigrationHashMap<String, Integer> map = new SmoothMigrationHashMap<>(4); map.put("one", 1); map.put("two", 2); map.put("three", 3); map.put("four", 4); System.out.println(map.get("one")); // 1 System.out.println(map.get("two")); // 2 map.put("five", 5); // Trigger rehashing System.out.println(map.get("five")); // 5 System.out.println(map.get("three")); // 3 } } ``` ### 代码说明 1. **初始化**: 初始化时创建一个`ArrayList`数组，每个位置上存储一个链表（用于解决冲突）。 2. **`get`方法**: 首先在旧表中查找，如果没有找到且在迁移过程中，则在新表中查找。 3. **`put`方法**: 在插入时，如果负载因子超过75%，开始重新散列。每次插入新元素时也会触发一次迁移操作。 4. **开始重新散列**: 创建一个大小为原来两倍的新表，初始化迁移索引。 5. **迁移操作**: 在每次插入新元素时，迁移一个旧表中的非空链表中的所有元素到新表中，直至所有元素迁移完成。每次迁移一定数量的元素（步数控制）以避免单次开销过大。 这样实现的HashMap可以避免在扩容时一次性迁移所有元素，减轻性能波动。