Eine Karte kann mithilfe von Hashing implementiert werden. Jetzt verstehen Sie das Konzept des Hashings. Sie wissen, wie Sie eine gute Hash-Funktion entwerfen, um einen Schlüssel einem Index in einer Hash-Tabelle zuzuordnen, wie Sie die Leistung anhand des Auslastungsfaktors messen und wie Sie die Tabellengröße erhöhen und erneut aufbereiten, um die Leistung aufrechtzuerhalten. In diesem Abschnitt wird gezeigt, wie Sie eine Karte mithilfe separater Verkettung implementieren.
Wir entwerfen unsere benutzerdefinierte Map-Schnittstelle, um java.util.Map zu spiegeln, und benennen die Schnittstelle MyMap und eine konkrete Klasse MyHashMap , wie in der Abbildung unten gezeigt.
Wie implementieren Sie MyHashMap? Wenn Sie eine ArrayList verwenden und einen neuen Eintrag am Ende der Liste speichern, beträgt die Suchzeit O(n). Wenn Sie MyHashMap mithilfe eines Binärbaums implementieren, beträgt die Suchzeit O(log n), wenn der Baum gut ausbalanciert ist. Dennoch können Sie MyHashMap mithilfe von Hashing implementieren, um einen O(1)-Zeit-Suchalgorithmus zu erhalten. Der folgende Code zeigt die MyMap-Schnittstelle.
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 + "]";
}
}
}
Nach dem Login kopieren
Der folgende Code implementiert MyHashMap mithilfe einer separaten Verkettung.
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();
}
}
Nach dem Login kopieren
Die Klasse MyHashMap implementiert die Schnittstelle MyMap mithilfe einer separaten Verkettung. Die Parameter, die die Größe und Auslastungsfaktoren der Hash-Tabelle bestimmen, werden in der Klasse definiert. Die standardmäßige Anfangskapazität beträgt 4 (Zeile 5) und die maximale Kapazität beträgt 2^30 (Zeile 8). Die aktuelle Hash-Tabelle
Die Kapazität ist als Wert der Potenz von 2 ausgelegt (Zeile 11). Der Standardlastfaktorschwellenwert beträgt 0,75f (Zeile 14). Sie können beim Erstellen einer Karte einen benutzerdefinierten Lastfaktorschwellenwert angeben. Der benutzerdefinierte Lastfaktor-Schwellenwert wird in loadFactorThreshold (Zeile 17) gespeichert. Das Datenfeld size gibt die Anzahl der Einträge in der Karte an (Zeile 20). Die Hash-Tabelle ist ein Array. Jede Zelle im Array ist eine verknüpfte Liste (Zeile 23).
Zum Erstellen einer Karte stehen drei Konstruktoren zur Verfügung. Sie können eine Standardkarte mit der Standardkapazität und dem Lastfaktorschwellenwert erstellen, indem Sie den No-Arg-Konstruktor (Zeilen 26–28), eine Karte mit der angegebenen Kapazität und einem Standardlastfaktorschwellenwert (Zeilen 32–34) und a verwenden Karte mit der angegebenen Kapazität und dem Lastfaktor-Schwellenwert (Zeilen 38–46).
Die Methode clear entfernt alle Einträge aus der Karte (Zeilen 49–52). Es ruft removeEntries() auf, das alle Einträge in den Buckets löscht (Zeilen 221–227). Die Methode removeEntries() benötigt O(Kapazität) Zeit, um alle Einträge in der Tabelle zu löschen.
Die Methode containsKey(key) prüft, ob der angegebene Schlüssel in der Karte vorhanden ist, indem sie die Methode get aufruft (Zeilen 55–60). Da die Methode get O(1) Zeit benötigt, benötigt die Methode containsKey(key) O(1) Zeit.
Die Methode containsValue(value) prüft, ob der Wert in der Karte vorhanden ist (Zeilen 63–74). Diese Methode benötigt O(Kapazität + Größe) Zeit. Es ist tatsächlich O (Kapazität), da Kapazität 7 Größe.
Die Methode entrySet() gibt einen Satz zurück, der alle Einträge in der Karte enthält (Zeilen 77–90). Diese Methode benötigt O(Kapazität)-Zeit.
Die Methode get(key) gibt den Wert des ersten Eintrags mit dem angegebenen Schlüssel zurück (Zeilen 93–103). Diese Methode benötigt O(1) Zeit.
Die Methode isEmpty() gibt einfach „true“ zurück, wenn die Karte leer ist (Zeilen 106–108). Diese Methode benötigt O(1) Zeit.
Die Methode keySet() gibt alle Schlüssel in der Karte als Satz zurück. Die Methode findet die Schlüssel aus jedem Bucket und fügt sie einem Satz hinzu (Zeilen 111–123). Diese Methode benötigt O(Kapazität)-Zeit.
Die Methode put(key, value) fügt der Karte einen neuen Eintrag hinzu. Die Methode testet zunächst, ob der Schlüssel bereits in der Karte vorhanden ist (Zeile 127), wenn ja, findet sie den Eintrag und ersetzt den alten Wert durch den neuen Wert im Eintrag für den Schlüssel (Zeile 134) und der alte Wert wird zurückgegeben ( Zeile 136). Wenn der Schlüssel neu in der Karte ist, wird der neue Eintrag in der Karte erstellt (Zeile 156). Vor dem Einfügen des neuen Eintrags prüft die Methode, ob die Größe den Lastfaktor-Schwellenwert überschreitet (Zeile 141). Wenn ja, ruft das Programm rehash() (Zeile 145) auf, um die Kapazität zu erhöhen und Einträge in der neuen größeren Hash-Tabelle zu speichern.
Die Methode rehash() kopiert zunächst alle Einträge in einem Satz (Zeile 231), verdoppelt die Kapazität (Zeile 232), erstellt eine neue Hash-Tabelle (Zeile 233) und setzt die Größe auf 0 (Zeile 234). Anschließend kopiert die Methode die Einträge in die neue Hash-Tabelle (Zeilen 236–238). Die Rehash-Methode benötigt O(Kapazitäts)-Zeit. Wenn keine erneute Aufbereitung durchgeführt wird, benötigt die Methode put O(1) Zeit, um einen neuen Eintrag hinzuzufügen.
Die Methode remove(key) entfernt den Eintrag mit dem angegebenen Schlüssel in der Karte (Zeilen 164–177). Diese Methode benötigt O(1) Zeit.
Die Methode size() gibt einfach die Größe der Karte zurück (Zeilen 180–182). Diese Methode benötigt O(1) Zeit.
Die Methode values() gibt alle Werte in der Karte zurück. Die Methode untersucht jeden Eintrag aus allen Buckets und fügt ihn einer Menge hinzu (Zeilen 185–197). Diese Methode benötigt O(Kapazität)-Zeit.
Die Methode hash() ruft den supplementalHash auf, um sicherzustellen, dass das Hashing gleichmäßig verteilt wird, um einen Index für die Hash-Tabelle zu erstellen (Zeilen 200–208). Diese Methode benötigt O(1) Zeit.
Die folgende Tabelle fasst die zeitliche Komplexität der Methoden in MyHashMap zusammen.
Da das erneute Aufwärmen nicht sehr oft vorkommt, beträgt die Zeitkomplexität für die Methode put O(1). Beachten Sie, dass die Komplexität der Methoden clear, entrySet, keySet, values und rehash von Kapazität. Um eine schlechte Leistung dieser Methoden zu vermeiden, sollten Sie eine anfängliche Kapazität sorgfältig auswählen.
Der folgende Code gibt ein Testprogramm an, das
MyHashMap verwendet.
Das Programm erstellt eine Karte mit
MyHashMap (Zeile 7) und fügt der Karte fünf Einträge hinzu (Zeilen 8–12). Zeile 5 fügt den Schlüssel Smith mit dem Wert 30 hinzu und Zeile 9 fügt Smith mit dem Wert 65 hinzu. Der letztere Wert ersetzt den früheren Wert. Die Karte hat eigentlich nur vier Einträge. Das Programm zeigt die Einträge in der Map an (Zeile 14), holt einen Wert für einen Schlüssel (Zeile 16), prüft, ob die Map den Schlüssel (Zeile 18) und einen Wert enthält (Zeile 19), entfernt einen Eintrag mit dem Schlüssel Smith (Zeile 21) und zeigt die Einträge in der Karte erneut an (Zeile 22). Abschließend löscht das Programm die Karte (Zeile 24) und zeigt eine leere Karte an (Zeile 25).
Das obige ist der detaillierte Inhalt vonImplementieren einer Karte mithilfe von Hashing. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
