マップはハッシュを使用して実装できます。これで、ハッシュの概念が理解できました。キーをハッシュ テーブル内のインデックスにマップする適切なハッシュ関数を設計する方法、負荷係数を使用してパフォーマンスを測定する方法、パフォーマンスを維持するためにテーブル サイズを増やして再ハッシュする方法を理解しています。このセクションでは、個別のチェーンを使用してマップを実装する方法を説明します。
java.util.Map をミラーリングするカスタム 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 行目)。
マップを構築するために 3 つのコンストラクターが提供されています。引数なしのコンストラクター (26 ～ 28 行目) を使用して、デフォルトの容量と負荷率のしきい値を使用したデフォルト マップ、指定された容量とデフォルトの負荷率のしきい値を使用したマップ (32 ～ 34 行目)、および指定された容量と負荷率のしきい値をマップします (38 ～ 46 行目)。
clear メソッドは、マップからすべてのエントリを削除します (行 49 ～ 52)。 removeEntries() を呼び出し、バケット内のすべてのエントリを削除します (行 221 ～ 227)。 removeEntries() メソッドは、テーブル内のすべてのエントリをクリアするのに O(容量) の時間を要します。
containsKey(key) メソッドは、get メソッド (55 ～ 60 行目) を呼び出して、指定されたキーがマップ内にあるかどうかを確認します。 get メソッドには O(1) 時間がかかるため、containsKey(key) メソッドには O(1) 時間がかかります。
containsValue(value) メソッドは、値がマップ内にあるかどうかをチェックします (行 63 ～ 74)。この方法では O(容量 + サイズ) の時間がかかります。容量7サイズなので実際はO(容量)です。
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 行目)、容量を 2 倍にし (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 行目)、マップに 5 つのエントリを追加します (8 ～ 12 行目)。 5 行目では、値 30 を持つキー Smith を追加し、9 行目では値 65 を持つ Smith を追加します。後の値は前の値を置き換えます。実際には、マップには 4 つのエントリしかありません。プログラムは、マップ内のエントリを表示し (14 行目)、キーの値を取得し (16 行目)、マップにキーが含まれているかどうかを確認し (18 行目) と値 (19 行目)、キー Smith (21 行目)、マップ内のエントリを再表示します (22 行目)。最後に、プログラムはマップをクリアし (24 行目)、空のマップを表示します (25 行目)。
以上がハッシュを使用したマップの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
