在 Java 中從 HashMap 中選擇一個隨機鍵
1. 概述
Maps是我們日常程式碼中可能用到的基本資料結構。然而，它的主要優勢——恆定時間訪問——在某些情況下，當我們嘗試將其與訪問映射中的隨機元素結合時，可能會產生問題。這種情況相對少見；但即便如此，當我們確實需要實現這一點時，如何有效率地完成卻並不明確。
在本教程中，我們將回顧幾種從映射表中獲取隨機元素的方法，並討論它們的優缺點。根據這些權衡，我們可以選擇最適合我們的方法。
2. 使用隨機數
如果我們在簡單的ArrayList環境中考慮這項任務，就不會遇到任何問題。因此，我們可以考慮幾種方案，其中隨機產生一個數字是關鍵步驟之一。
2.1. 轉換為ArrayList
最直接的解決方案是透過將鍵集轉換為ArrayList並使用隨機索引存取元素來獲取隨機鍵：
public <K, V> V getRandomValueUsingList(Map<K, V> map) {
if (map == null || map.isEmpty()) {
return null;
}
List<K> keys = new ArrayList<>(map.keySet());
K randomKey = keys.get(ThreadLocalRandom.current().nextInt(keys.size()));
return map.get(randomKey);
}雖然這個方案看似簡單， rrayList A的隨機元素是恆定的，仍然存在隱藏的時間複雜度。時間複雜度不可能小於空間複雜度。我們需要n迭代才能將長度為 n 的集合複製或轉換為陣列。然而，如果我們可以多次重複使用同一個數組，並且原始集合的變化不大，那麼這個方案可能整體表現良好。
要使用此函數，我們需要傳入一個原始映射，然後可以從中檢索一個隨機值：
private final RandomNumberMap randomNumberMap = new RandomNumberMap();
@Test
public void whenGettingRandomValue_thenValueExistsInMap() {
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
map.put("date", 4);
map.put("elderberry", 5);
Integer randomValue = randomNumberMap.getRandomValueUsingList(map);
assertNotNull(randomValue);
assertTrue(map.containsValue(randomValue));
}由於我們的目標是使結果隨機化，因此我們不能對得到的值做任何假設。但是，程式碼應該只傳回原始映射中存在的值。
2.2. 使用迭代
如果很少需要執行此操作，或者原始集合經常變化，我們可以直接對集合進行迭代。雖然這樣無法透過索引存取元素，但我們可以跳過特定數量的元素：
public <K, V> V getRandomValueUsingOffset(Map<K, V> map) {
if (map == null || map.isEmpty()) {
return null;
}
int randomOffset = ThreadLocalRandom.current().nextInt(map.size());
Iterator<Entry<K, V>> iterator = map.entrySet().iterator();
for (int i = 0; i < randomOffset; i++) {
iterator.next();
}
return iterator.next().getValue();
}雖然這個方案看起來不如第一個方案，但實際上對於一次性操作來說效果更好。因此，我們應該考慮這段程式碼的使用頻率和使用場景，以及元素數量的限制。使用範例與先前的實作非常相似。
3. 洗牌
另一種方法（可能有點過度）是將整個陣列打亂順序，然後選擇第一個元素。這種方法仍然需要將集合轉換為有序集合：
public <K, V> K getRandomKeyUsingShuffle(Map<K, V> map) {
if (map == null || map.isEmpty()) {
return null;
}
List<K> keys = new ArrayList<>(map.keySet());
Collections.shuffle(keys);
return keys.get(0);
}這種方法的時間複雜度比之前的方案要高。但是，它有一個非常好的優點：我們可以將打亂的集合清空。在這種情況下，我們可以將該集合用作隨機值的來源。然而，這樣做會阻止相同的值出現在同一次隨機化過程中，因此它可能並不適用於所有情況。
此外，雖然我們沒有將ThreadLocalRandom或Random傳遞給shuffle()函數，但它們會在內部建立。因此，這種方法需要我們之前使用的所有功能，並且可能僅適用於特定情況和需求。
4. 客製化包裝
但是，如果我們需要一個即使在地圖頻繁更新的情況下也能高效運行，並且需要適當的隨機化方案的實現，我們可以建立一個自訂解決方案。我們將從一個簡單的封裝器開始，隻公開基本操作：
public class RandomKeyTrackingMap<K, V> {
private final Map<K, V> delegate = new HashMap<>();
private final List<K> keys = new ArrayList<>();
public void put(K key, V value) {
V previousValue = delegate.put(key, value);
if (previousValue == null) {
keys.add(key);
}
}
public V remove(K key) {
V removedValue = delegate.remove(key);
if (removedValue != null) {
int index = keys.indexOf(key);
if (index >= 0) {
keys.remove(index);
}
}
return removedValue;
}
public V getRandomValue() {
if (keys.isEmpty()) {
return null;
}
int randomIndex = ThreadLocalRandom.current().nextInt(keys.size());
K randomKey = keys.get(randomIndex);
return delegate.get(randomKey);
}
}主要問題在於remove()操作，因為我們需要同時從映射和清單中刪除值。然而，為了提高此操作的效能，我們應該添加另一個資料結構來追蹤鍵的索引：
private final Map<K, V> delegate = new HashMap<>();
private final List<K> keys = new ArrayList<>();
private final Map<K, Integer> keyToIndex = new HashMap<>();
public void put(K key, V value) {
V previousValue = delegate.put(key, value);
if (previousValue == null) {
keys.add(key);
keyToIndex.put(key, keys.size() - 1);
}
}我們可以改進解決方案，使用 swap 取代 remove，這樣就可以不斷刪除最後一個元素，讓操作變成常數：
public V remove(K key) {
V removedValue = delegate.remove(key);
if (removedValue != null) {
Integer index = keyToIndex.remove(key);
if (index != null) {
removeKeyAtIndex(index);
}
}
return removedValue;
}
private void removeKeyAtIndex(int index) {
int lastIndex = keys.size() - 1;
if (index == lastIndex) {
keys.remove(lastIndex);
return;
}
K lastKey = keys.get(lastIndex);
keys.set(index, lastKey);
keyToIndex.put(lastKey, index);
keys.remove(lastIndex);
}雖然這會增加一些程式碼，但它能使這種方法在攤銷後的線性時間內運作。實作之後，我們可以如下使用該映射：
@Test
public void whenGettingRandomValue_thenValueExistsInMap() {
OptimizedRandomKeyTrackingMap<String, Integer> map = new OptimizedRandomKeyTrackingMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
Integer randomValue = map.getRandomValue();
assertNotNull(randomValue);
assertTrue(Arrays.asList(1, 2, 3).contains(randomValue));
}此外，這種實作方式允許我們透過包裝器刪除值（先前的實作方式可以使用對原始映射的引用，但這可能會導致難以調試的問題）：
@Test
public void whenRemovingValue_thenRandomValueDoesNotContainRemovedEntry() {
OptimizedRandomKeyTrackingMap<String, Integer> map = new OptimizedRandomKeyTrackingMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
map.remove("banana");
Integer randomValue = map.getRandomValue();
assertNotNull(randomValue);
assertTrue(Arrays.asList(1, 3).contains(randomValue));
}我們可以根據需求和我們計劃使用此類的上下文，為包裝器添加額外的方法和功能。
5. 擴充HashMap
映射本身包含有關內部值和節點的資訊。然而， table是一個桶數組。雖然我們可以均勻地選擇桶，但我們不能對元素這樣做，因為某些桶可能為空或包含多個entrySet 。 entrySet 與Map有同樣的問題（它內部也使用了Map ），因此我們無法從無序集合中取得隨機值：
// Rest of HashMap implementation
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
// Rest of HashMap implementation同時，我們可以建立一個新的 Map 實作。這樣就可以將該類別無縫整合到程式碼的其餘部分。然而，這種方法需要編寫更多程式碼，因為我們需要滿足所有Map方法的要求，並確保不會破壞任何現有功能：
public class RandomizedMap<K, V> extends HashMap<K, V> {
private final Map<Integer, K> numberToKey = new HashMap<>();
private final Map<K, Integer> keyToNumber = new HashMap<>();
@Override
public V put(K key, V value) {
V oldValue = super.put(key, value);
if (oldValue == null) {
int number = this.size() - 1;
numberToKey.put(number, key);
keyToNumber.put(key, number);
}
return oldValue;
}
@Override
public V remove(Object key) {
V removedValue = super.remove(key);
if (removedValue != null) {
removeFromTrackingMaps(key);
}
return removedValue;
}
public V getRandomValue() {
if (this.isEmpty()) {
return null;
}
int randomNumber = ThreadLocalRandom.current().nextInt(this.size());
K randomKey = numberToKey.get(randomNumber);
return this.get(randomKey);
}
// Other methods
}與先前的範例相比，刪除功能應該涵蓋更多情況：
private void removeFromTrackingMaps(Object key) {
@SuppressWarnings("unchecked")
K keyToRemove = (K) key;
Integer numberToRemove = keyToNumber.get(keyToRemove);
if (numberToRemove == null) {
return;
}
int mapSize = this.size();
int lastIndex = mapSize;
if (numberToRemove == lastIndex) {
numberToKey.remove(numberToRemove);
keyToNumber.remove(keyToRemove);
} else {
K lastKey = numberToKey.get(lastIndex);
if (lastKey == null) {
numberToKey.remove(numberToRemove);
keyToNumber.remove(keyToRemove);
return;
}
numberToKey.put(numberToRemove, lastKey);
keyToNumber.put(lastKey, numberToRemove);
numberToKey.remove(lastIndex);
keyToNumber.remove(keyToRemove);
}
}這是一個更複雜的解決方案，需要使其與Map介面保持一致。因此，當類別在程式碼的其他部分需要與Map介面保持一致時，它是最佳選擇。
6. 結論
物件導向程式語言（以及幾乎所有程式語言）允許我們為遇到的問題創建客製化的解決方案。不知何故，這項特性常常被忽略。當標準庫無法提供現成的解決方案或功能時，開發人員就會遇到問題。重要的是要記住，如果我們缺少某個特定功能，我們始終可以從頭開始建立它。
像往常一樣，本教程中的所有程式碼都可以在 GitHub 上找到。