Erstellen Sie eine Hash-Tabelle mit zwei Arrays

Question

Weiß jemand wie man das macht und wie der Pseudo-Code aussehen würde?

Wie wir alle wissen, speichert eine Hash-Tabelle Schlüssel, Wert-Paare und wenn ein Schlüssel aufgerufen wird, wird die Funktion den Wert zurückgeben, der diesem Schlüssel zugeordnet ist. Ich möchte die zugrunde liegende Struktur bei der Erstellung dieser Mapping-Funktion verstehen. Wenn wir beispielsweise in einer Welt leben, in der es keine zuvor definierten Funktionen außer Arrays gibt, wie können wir die Hashmaps replizieren, die wir heute haben?

Answer 1

Tatsächlich sind einige der heutigen HashMap implentations in der Tat aus Arrays hergestellt, wie Sie vorschlagen. Lassen Sie mich skizzieren, wie das funktioniert:

Hash-Funktion Eine Hash-Funktion wandelt Ihre Schlüssel in einen Index für das erste Array (Array K) um. Eine Hash-Funktion wie MD5 oder eine einfachere, die normalerweise einen Modulo-Operator enthält, kann dafür verwendet werden.

Buckets Eine einfache Array-basierte Hashmap-Implementierung könnte Buckets verwenden, um Kollisionen zu bewältigen. Jedes Element ("Bucket") in Array K enthält ein Array (Array P) von Paaren. Wenn Sie ein Element hinzufügen oder abfragen, verweist die Hash-Funktion auf den richtigen Bucket in K, der Ihr gewünschtes Array P enthält. Sie durchlaufen dann die Elemente in P, bis Sie einen passenden Schlüssel gefunden haben, oder Sie weisen ein neues Element zu Ende P.

Mapping Schlüssel zum Eimer mit dem Hash Sie sollten sicherstellen, dass die Anzahl der Schaufeln (dh die Größe von K) eine Potenz von 2 ist, lassen Sie uns sagen, 2^b. Um den richtigen Bucket-Index für einen Schlüssel zu finden, berechnen Sie Hash (Schlüssel), behalten aber nur die ersten b Bits. Dies ist Ihr Index, wenn er in eine ganze Zahl umgewandelt wird.

Neuskalierung Rechnen Sie den Hash eines Schlüssels und finden Sie den richtigen Eimer ist sehr schnell. Aber sobald ein Eimer voller wird, müssen Sie mehr und mehr Elemente iterieren, bevor Sie zu dem richtigen kommen. Daher ist es wichtig, genügend Buckets zu haben, um die Objekte richtig zu verteilen, oder Ihre Hashmap wird langsam.

Da Sie im Allgemeinen nicht wissen, wie viele Objekte Sie im Voraus in der Hashmap speichern möchten, ist es wünschenswert, die Karte dynamisch zu vergrößern oder zu verkleinern. Sie können die Anzahl der gespeicherten Objekte zählen und nach dem Überschreiten eines bestimmten Schwellenwerts die gesamte Struktur neu erstellen, diesmal jedoch mit einer größeren oder kleineren Größe für Array K.Auf diese Weise werden einige der Buckets in K, die sehr voll waren, nun ihre Elemente auf mehrere Buckets verteilt, so dass die Performance besser wird.

Alternativen Sie können auch anstelle eines Arrays-of-Arrays, die eine zweidimensionale Matrix verwenden, oder Sie können Array P für eine verkettete Liste austauschen. Anstatt eine Gesamtanzahl gespeicherter Objekte zu behalten, können Sie auch einfach die Hash-Map neu erstellen (d. H. Reskalieren), sobald einer der Buckets mehr als eine konfigurierte Anzahl von Elementen enthält.

Eine Variation von dem, was Sie fragen, wird als 'Array-Hash-Tabelle' in der Hash table Wikipedia entry beschrieben.

Code Für Codebeispiele, werfen Sie einen Blick auf here.

Hoffe, das hilft.

Answer 2

Können Sie genauer sein? Enthält ein Array die Schlüssel, der andere die Werte?

Wenn ja, hier ist ein Beispiel in Java (aber es gibt einige Besonderheiten dieser Sprache hier):

for (int i = 0; i < keysArray.length; i++) { 
    map.put(keysArray[i], valuesArray[i]); 
} 

Natürlich, werden Sie Ihre map Objekt instanziiert müssen (wenn Sie Java verwenden, Ich schlage vor, eine HashMap<Object, Object> anstelle einer veralteten HashTable zu verwenden, und auch Ihre Arrays zu testen, um null Objekte zu vermeiden und zu überprüfen, ob sie die gleiche Größe haben.

Answer 3

Sie meinen so?

Das Folgende ist mit Rubys irb als Illustration:

cities = ["LA", "SF", "NY"] 
=> ["LA", "SF", "NY"] 

items = ["Big Mac", "Hot Fudge Sundae"] 
=> ["Big Mac", "Hot Fudge Sundae"] 

price = {} 
=> {} 

price[[cities[0], items[1]]] = 1.29 
=> 1.29 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29} 

price[[cities[0], items[0]]] = 2.49 
=> 2.49 

price[[cities[1], items[0]]] = 2.99 
=> 2.99 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29, ["LA", "Big Mac"]=>2.49, ["SF", "Big Mac"]=>2.99} 

price[["LA", "Big Mac"]] 
=> 2.49 

Answer 4

Probe Erläuterung:

Am unten Quelle, im Grunde hat es zwei Dinge:

1. Karte Darstellung

• Einige (X Anzahl der List) von Listen
• X ist 2 Power N Anzahl der Listen ist schlecht. A (2 Potenz N) -1 oder (2 Potenz N) +1 oder eine Primzahl ist gut.

Beispiel:

List myhashmap [hash_table_size]; 
// an array of (short) lists 
// if its long lists, then there are more collisions 

HINWEIS: Das ist Array von Arrays, nicht zwei Arrays (Ich kann nicht eine mögliche generische hashmap, in einer guten Art und Weise mit nur zwei Arrays sehen)

Wenn Sie wissen, Algorithmen> Graphentheorie> Adjazenzliste, diese sieht genau gleich.

2.Hashfunktion

und die Hash-Funktion wandelt string (Eingang) zu einer Reihe (Hash-Wert), der Index eines Arrays ist

• den Hash-Wert zum ersten char initialisieren (nach int umgewandelt)
• für jede weitere char, Linksverschiebung 4 Bits, dann füge char

Beispiel,

int hash = input[0]; 
for (int i=1; i<input.length(); i++) { 
    hash = (hash << 4) + input[i] 
} 

hash = hash % list.size() 
// list.size() here represents 1st dimension of (list of lists) 
//  that is 1st dimension size of our map representation from point #1 
//  which is hash_table_size 

(nach dem in int umgewandelt)

sehen auf den ersten Link:

int HTable::hash (char const * str) const 

Quelle:
http://www.relisoft.com/book/lang/pointer/8hash.html
How does a hash table work?

aktualisieren
Dies ist die beste Quelle: http://algs4.cs.princeton.edu/34hash/