HashMap 中的鏈表刪除操作主要涉及到以下幾個步驟:
以下是一個簡化的 Java 代碼示例,展示了如何實現 HashMap 中鏈表的刪除操作:
public class HashMap<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private Node<K, V>[] table;
private int size;
public HashMap() {
table = new Node[DEFAULT_CAPACITY];
}
// 其他方法,如 put、get 等
public V remove(K key) {
int hash = hash(key);
int index = indexFor(hash, table.length);
Node<K, V> prev = null;
Node<K, V> current = table[index];
while (current != null) {
if (current.key.equals(key)) {
break;
}
prev = current;
current = current.next;
}
if (current == null) {
return null; // 未找到目標節點,不需要刪除
}
if (prev == null) {
table[index] = current.next; // 刪除的是鏈表頭節點
} else {
prev.next = current.next; // 刪除的是鏈表中間節點
}
size--;
return current.value;
}
private int hash(K key) {
return key.hashCode();
}
private int indexFor(int h, int length) {
return h & (length - 1);
}
private static class Node<K, V> {
K key;
V value;
Node<K, V> next;
Node(K key, V value, Node<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
}
這個示例中,remove
方法實現了 HashMap 中鏈表的刪除操作。首先計算哈希值和桶索引,然后遍歷鏈表找到目標節點并從鏈表中移除。最后更新 HashMap 的元素數量。