使用哈希實現映射
- WBOY原創
- 2024-07-28 07:43:13510瀏覽
地圖可以使用散列來實現。現在您了解了哈希的概念。您知道如何設計良好的雜湊函數以將鍵映射到雜湊表中的索引，如何使用負載因子衡量效能，以及如何增加表大小和重新雜湊以維持效能。本節示範如何使用單獨的連結來實現映射。
我們設計自訂的Map 介面來鏡像java.util.Map 並將介面命名為MyMap 和一個特定類別MyHashMap ，如下圖所示。
如何實作MyHashMap？如果您使用 ArrayList 並將新條目儲存在清單末尾，則搜尋時間將為 O(n)。如果使用二元樹實作 MyHashMap，如果樹平衡良好，則搜尋時間將為 O(log n)。儘管如此，您可以使用雜湊來實作 MyHashMap 以獲得 O(1) 時間的搜尋演算法。下面的程式碼顯示了MyMap介面。
package demo;
public interface MyMap<K, V> {
/** Remove all of the entries from this map */
public void clear();
/** Return true if the specified key is in the map */
public boolean containsKey(K key);
/** Return true if this map contains the specified value */
public boolean containsValue(V value);
/** Return a set of entries in the map */
public java.util.Set<Entry<K, V>> entrySet();
/** Return the value that matches the specified key */
public V get(K key);
/** Return true if this map doesn't contain any entries */
public boolean isEmpty();
/** Return a set consisting of the keys in this map */
public java.util.Set<K> keySet();
/** Add an entry (key, value) into the map */
public V put(K key, V value);
/** Remove an entry for the specified key */
public void remove(K key);
/** Return the number of mappings in this map */
public int size();
/** Return a set consisting of the values in this map */
public java.util.Set<V> values();
/** Define an inner class for Entry */
public static class Entry<K, V> {
K key;
V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
@Override
public String toString() {
return "[" + key + ", " + value + "]";
}
}
}
下面的程式碼使用單獨的連結實作MyHashMap。
package demo;
import java.util.LinkedList;
public class MyHashMap<K, V> implements MyMap<K, V> {
// Define the default hash-table size. Must be a power of 2
private static int DEFAULT_INITIAL_CAPACITY = 4;
// Define the maximum hash-table size. 1 << 30 is same as 2^30
private static int MAXIMUM_CAPACITY = 1 << 30;
// Current hash-table capacity. Capacity is a power of 2
private int capacity;
// Define default load factor
private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
// Specify a load factor used in the hash table
private float loadFactorThreshold;
// The number of entries in the map
private int size = 0;
// Hash table is an array with each cell being a linked list
LinkedList<MyMap.Entry<K, V>>[] table;
/** Construct a map with the default capacity and load factor */
public MyHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a map with the specified initial capacity and
* default load factor */
public MyHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a map with the specified initial capacity
* and load factor */
public MyHashMap(int initialCapacity, float loadFactorThreshold) {
if(initialCapacity > MAXIMUM_CAPACITY)
this.capacity = MAXIMUM_CAPACITY;
else
this.capacity = trimToPowerOf2(initialCapacity);
this.loadFactorThreshold = loadFactorThreshold;
table = new LinkedList[capacity];
}
@Override /** Remove all of the entries from this map */
public void clear() {
size = 0;
removeEntries();
}
@Override /** Return true if the specified key is in the map */
public boolean containsKey(K key) {
if(get(key) != null)
return true;
else
return false;
}
@Override /** Return true if this map contains the value */
public boolean containsValue(V value) {
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K ,V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
if(entry.getValue().equals(value))
return true;
}
}
return false;
}
@Override /** Return a set of entries in the map */
public java.util.Set<MyMap.Entry<K, V>> entrySet() {
java.util.Set<MyMap.Entry<K, V>> set = new java.util.HashSet<>();
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry);
}
}
return set;
}
@Override /** Return the value that matches the specified key */
public V get(K key) {
int bucketIndex = hash(key.hashCode());
if(table[bucketIndex] != null) {
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key))
return entry.getValue();
}
return null;
}
@Override /** Return true if this map contains no entries */
public boolean isEmpty() {
return size == 0;
}
@Override /** Return a set consisting of the keys in this map */
public java.util.Set<K> keySet() {
java.util.Set<K> set = new java.util.HashSet<K>();
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry.getKey());
}
}
return set;
}
@Override /** Add an entry (key, value) into the map */
public V put(K key, V value) {
if(get(key) != null) { // The key is already in the map
int bucketIndex = hash(key.hashCode());
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key)) {
V oldValue = entry.getValue();
// Replace old value with new value
entry.value = value;
// Return the old value for the key
return oldValue;
}
}
// Check load factor
if(size >= capacity * loadFactorThreshold) {
if(capacity == MAXIMUM_CAPACITY)
throw new RuntimeException("Exceeding maximum capacity");
rehash();
}
int bucketIndex = hash(key.hashCode());
// Create a linked list for the bucket if not already created
if(table[bucketIndex] == null) {
table[bucketIndex] = new LinkedList<Entry<K, V>>();
}
// Add a new entry (key, value) to hashTable[index]
table[bucketIndex].add(new MyMap.Entry<K, V>(key, value));
size++; // Increase size
return value;
}
@Override /** Remove the entries for the specified key */
public void remove(K key) {
int bucketIndex = hash(key.hashCode());
// Remove the first entry that matches the key from a bucket
if(table[bucketIndex] != null) {
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key)) {
bucket.remove(entry);
size--; // Decrease size
break; // Remove just one entry that matches the key
}
}
}
@Override /** Return the number of entries in this map */
public int size() {
return size;
}
@Override /** Return a set consisting of the values in this map */
public java.util.Set<V> values() {
java.util.Set<V> set = new java.util.HashSet<>();
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry.getValue());
}
}
return set;
}
/** Hash function */
private int hash(int hashCode) {
return supplementalHash(hashCode) & (capacity - 1);
}
/** Ensure the hashing is evenly distributed */
private static int supplementalHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/** Return a power of 2 for initialCapacity */
private int trimToPowerOf2(int initialCapacity) {
int capacity = 1;
while(capacity < initialCapacity) {
capacity <<= 1; // Same as capacity *= 2. <= is more efficient
}
return capacity;
}
/** Remove all entries from each bucket */
private void removeEntries() {
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
table[i].clear();
}
}
}
/** Rehash the map */
private void rehash() {
java.util.Set<Entry<K, V>> set = entrySet(); // Get entries
capacity <<= 1; // Same as capacity *= 2. <= is more efficient
table = new LinkedList[capacity]; // Create a new hash table
size = 0; // Reset size to 0
for(Entry<K, V> entry: set) {
put(entry.getKey(), entry.getValue()); // Store to new table
}
}
@Override /** Return a string representation for this map */
public String toString() {
StringBuilder builder = new StringBuilder("[");
for(int i = 0; i < capacity; i++) {
if(table[i] != null && table[i].size() > 0)
for(Entry<K, V> entry: table[i])
builder.append(entry);
}
builder.append("]");
return builder.toString();
}
}
MyHashMap 類別使用單獨的連結實作 MyMap 介面。確定哈希表大小和負載因子的參數在類別中定義。預設初始容量為 4（第 5 行），最大容量為 2^30（第 8 行）。目前的哈希表
容量被設計為 2 的冪值（第 11 行）。預設負載因子閾值是 0.75f（第 14 行）。您可以在建立地圖時指定自訂負載因子閾值。自訂負載因子閾值儲存在 loadFactorThreshold（第 17 行）。資料欄位 size 表示映射中的條目數（第 20 行）。哈希表是一個數組。陣列中的每個單元格都是一個鍊錶（第 23 行）。
提供了三個建構子來建構地圖。您可以使用無參數建構函式建構一個具有預設容量和負載因子閾值的預設對映（第26-28 行），一個具有指定容量和預設負載因子閾值的對應（第32-34 行），以及一個具有指定容量和負載係數閾值的對應（第38-46 行）。
clear 方法從映射中刪除所有項目（第 49-52 行）。它呼叫 removeEntries()，刪除儲存桶中的所有項目（第 221-227 行）。 removeEntries() 方法需要 O(capacity) 時間來清除表中的所有項目。
containsKey(key) 方法透過呼叫 get 方法檢查指定的鍵是否在映射中（第 55-60 行）。由於 get 方法需要 O(1) 時間，因此 containsKey(key) 方法需要 O(1) 時間。
containsValue(value) 方法檢查值是否在地圖中（第 63-74 行）。此方法需要 O(容量 + 大小) 時間。它實際上是 O(容量)，因為容量為 7 大小。
entrySet() 方法傳回一個包含映射中所有項目的集合（第 77-90 行）。此方法需要 O(capacity) 時間。
get(key) 方法傳回具有指定鍵的第一個條目的值（第 93-103 行）。此方法需要 O(1) 時間。
如果地圖為空，isEmpty() 方法只會傳回 true（第 106-108 行）。此方法需要 O(1) 時間。
keySet() 方法將映射中的所有鍵作為一個集合傳回。此方法從每個儲存桶中尋找鍵並將它們新增至一個集合（第 111-123 行）。此方法需要 O(capacity) 時間。
put(key, value) 方法在映射中新增一個條目。此方法首先測試鍵是否已在映射中（第 127 行），如果是，則找到該條目並用該鍵條目中的新值取代舊值（第 134 行），然後傳回舊值（第 136 行）。如果映射中的鍵是新的，則會在映射中建立新條目（第 156 行）。在插入新條目之前，此方法檢查大小是否超過負載因子閾值（第 141 行）。如果是這樣，程式會呼叫 rehash() （第 145 行）來增加容量並將條目儲存到新的更大的雜湊表中。
rehash()方法首先複製集合中的所有條目（第231行），將容量加倍（第232行），建立一個新的哈希表（第233行），並將大小重置為0（第234 行）。然後該方法將條目複製到新的哈希表中（第 236-238 行）。 rehash 方法需要 O(capacity) 時間。如果不執行重新哈希，則 put 方法需要 O(1) 時間來新增條目。
remove(key) 方法刪除映射中具有指定鍵的條目（第 164-177 行）。此方法需要 O(1) 時間。
size() 方法只傳回地圖的大小（第 180-182 行）。此方法需要 O(1) 時間。
values() 方法傳回映射中的所有值。此方法檢查所有儲存桶中的每個條目並將其新增至一個集合（第 185-197 行）。此方法需要 O(capacity) 時間。
hash() 方法呼叫 supplementalHash 以確保散列均勻分佈以產生散列表的索引（第 200-208 行）。此方法需要 O(1) 時間。
下表總結了MyHashMap中方法的時間複雜度。
由於重新雜湊不會經常發生，因此 put 方法的時間複雜度為 O(1)。請注意，clear、entrySet、keySet、values 和rehash 方法的複雜性取決於容量，因此為了避免這些方法效能不佳，您應該仔細選擇初始容量。
下面的程式碼給了一個使用MyHashMap.的測試程序
MyHashMap 建立一個映射（第 7 行），並在映射中新增五個條目（第 8-12 行）。第 5 行新增鍵 Smith，值為 30，第 9 行增加 Smith，值為 65。後一個值替換前一個值。該地圖實際上只有四個條目。程式顯示映射中的條目（第14 行），取得鍵的值（第16 行），檢查映射是否包含該鍵（第18 行）和值（第19 行），刪除帶有鍵Smith（第21 行），並重新顯示地圖中的條目（第22 行）。最後，程式清除地圖（第 24 行）並顯示一個空地圖（第 25 行）。
以上是使用哈希實現映射的詳細內容。更多資訊請關注PHP中文網其他相關文章！