Hash-Tabellen VS assoziative Arrays

Lesezeit: 6 Minuten

Benutzer-Avatar
Bachtiyor

Kürzlich habe ich darüber gelesen Hash-Tabellen in einem sehr berühmten Buch “Einführung in Algorithmen“. Ich habe sie noch nicht in echten Anwendungen verwendet, möchte es aber tun. Aber ich weiß nicht, wie ich anfangen soll.
Kann mir jemand Beispiele für die Verwendung geben, zum Beispiel, wie man eine Wörterbuchanwendung (wie ABBYY Lingvo) mit Hash-Tabellen realisiert?
Und schließlich würde ich gerne wissen, was der Unterschied zwischen Hash-Tabellen und assoziativen Arrays in PHP ist, ich meine, welche Technologie sollte ich verwenden und in welchen Situationen?
Wenn ich falsch liege (ich bitte um Verzeihung), korrigieren Sie mich bitte, denn eigentlich beginne ich mit Hash-Tabellen und habe nur grundlegende (theoretische) Kenntnisse darüber.
Danke vielmals.

  • siehe stackoverflow.com/questions/2350361/…

    – Artefakt

    28. Juni 2010 um 16:53 Uhr

Benutzer-Avatar
Nocken

In PHP werden assoziative Arrays als Hashtables implementiert, mit ein wenig zusätzlicher Funktionalität.

Technisch gesehen ist ein assoziatives Array jedoch nicht identisch mit einer Hashtabelle – es ist einfach umgesetzt teilweise mit einem Hashtable hinter den Kulissen. Da der größte Teil seiner Implementierung eine Hash-Tabelle ist, kann es alles tun, was eine Hash-Tabelle kann – aber es kann noch mehr.

Beispielsweise können Sie ein assoziatives Array mit einer for-Schleife durchlaufen, was mit einer Hashtabelle nicht möglich ist.

Obwohl sie ähnlich sind, kann ein assoziatives Array tatsächlich Folgendes tun Obermenge was eine Hashtabelle kann – sie sind also nicht genau dasselbe. Betrachten Sie es als Hashtabellen plus zusätzliche Funktionalität.

Codebeispiele:

Verwenden eines assoziativen Arrays als Hashtabelle:

$favoriteColor = array();
$favoriteColor['bob']='blue';
$favoriteColor['Peter']='red';
$favoriteColor['Sally']='pink';
echo 'bob likes: '.$favoriteColor['bob']."\n";
echo 'Sally likes: '.$favoriteColor['Sally']."\n";
//output: bob likes blue
//        Sally likes pink

Durchlaufen eines assoziativen Arrays:

$idTable=array();
$idTable['Tyler']=1;
$idTable['Bill']=20;
$idTable['Marc']=4;
//up until here, we're using the array as a hashtable.

//now we loop through the array - you can't do this with a hashtable:
foreach($idTable as $person=>$id)
    echo 'id: '.$id.' | person: '.$person."\n";

//output: id: 1 | person: Tyler
//        id: 20 | person: Bill
//        id: 4 | person: Marc

Beachten Sie insbesondere, wie im zweiten Beispiel die Reihenfolge der einzelnen Elemente beibehalten wird (Tyler, Bill Marc), basierend auf der Reihenfolge, in der sie in das Array eingegeben wurden. Dies ist ein wesentlicher Unterschied zwischen assoziativen Arrays und Hashtables. Eine Hashtabelle behält keine Verbindung zwischen den Elementen bei, die sie enthält, während ein assoziatives PHP-Array dies tut (Sie können sogar ein assoziatives PHP-Array sortieren).

  • Hmm, so eine kurze Erklärung. Also sind sie UNBEDINGT das gleiche?

    – Bachtijor

    28. Juni 2010 um 16:43 Uhr


  • @Bak Sie sind im Allgemeinen nicht, aber sie sind in PHP, das mit Datenstrukturen etwas schnell und locker spielt, da die Leistung weniger wichtig ist

    – Michael Mrozek

    28. Juni 2010 um 16:45 Uhr


  • @Michael du lässt es wie einen Nachteil klingen? Es macht PHP anders, aber ich denke, es ist ein guter Unterschied.

    Lösch mich

    28. Juni 2010 um 16:52 Uhr

  • @Bakhityor: Dein letzter Satz ist perfekt. Sie müssen Hashtables jedoch nicht „vergessen“ – es ist tatsächlich großartig, dass Sie bereits Hashtables verstehen, denn jetzt können Sie dieses Wissen auf assoziative Arrays anwenden. Ich füge meiner Antwort einige Beispiele hinzu, um die Sache für Sie weiter zu verdeutlichen.

    – Kamera

    28. Juni 2010 um 17:12 Uhr

  • Gute Antwort. Ich möchte es um die Tatsache erweitern, dass nicht nur die zugrunde liegende Implementierung von Arrays in PHP Hash-Tabellen sind, sie werden auch verwendet, um fast alles andere zu speichern: Eigenschaften und Methoden von Objekten, Funktionen, Variablen. usw.

    – Victor Iglesias Castán

    30. Oktober 2021 um 9:19 Uhr

PHP-Arrays SIND grundsätzlich Hash-Tabellen

  • Bearbeiten: Ah – schlagen Sie mich zu 🙂 +1.

    – Kamera

    28. Juni 2010 um 16:41 Uhr

  • das habe ich gesucht 🙂

    – Faizan

    6. Januar 2013 um 16:29 Uhr

  • auf keinen Fall. Eine Hash-Tabelle würde eine Art Kollisionsauflösung erfordern, die PHP-Arrays nicht haben. Ihre Kollisionsauflösungsstrategie ersetzt nur den alten Wert, und das ist per Definition keine Hash-Tabelle.

    – Juan

    21. März 2015 um 13:23 Uhr

  • Soweit ich mich erinnere, ist die Kollisionsauflösung in Hash-Tabellen für die gehasht Schlüssel, nicht der Originalschlüssel (Wie soll das überhaupt funktionieren?)

    – Emanuel Oster

    30. Januar 2017 um 15:34 Uhr

  • per Juans Kommentar: Ein Array kann als Hash-Tabelle implementiert werden, bedeutet aber nicht, dass es eine Hash-Tabelle ist. Arrays benötigen keine Kollisionserkennung, sodass jede zugrunde liegende Implementierung Kollisionen ignorieren kann (ersetzen Sie einfach Werte durch Zuweisung).

    – NeoH4x0r

    6. Februar 2021 um 23:04 Uhr

Der Unterschied zwischen einem assoziativen Array und einer Hash-Tabelle besteht darin, dass ein assoziatives Array ein Datentyp ist, während eine Hash-Tabelle eine Datenimplementierung ist. Offensichtlich ist der assoziative Array-Typ in vielen aktuellen Programmiersprachen sehr wichtig: Perl, Python, PHP usw. Eine Hash-Tabelle ist die wichtigste Möglichkeit, ein assoziatives Array zu implementieren, aber nicht ganz die einzige Möglichkeit. Und assoziative Arrays sind die Hauptverwendung von Hash-Tabellen, aber nicht ganz die einzige Verwendung. Es ist also nicht so, dass sie gleich sind, aber wenn Sie bereits assoziative Arrays haben, sollten Sie sich normalerweise keine Gedanken über den Unterschied machen.

Aus Leistungsgründen kann es wichtig sein zu wissen, dass Ihre assoziativen Arrays in Ihrer bevorzugten Sprache als Hashes implementiert sind. Und es kann wichtig sein, eine Vorstellung von den Gemeinkosten dieser Implementierung zu haben. Hash-Tabellen sind langsamer und benötigen mehr Speicher als lineare Arrays, wie Sie sie in C sehen.

Perl wirft die beiden Konzepte zusammen, indem es assoziative Arrays “Hashes” nennt. Wie eine Reihe von Features von Perl ist es nicht ganz falsch, aber schlampig.

  • Können Sie ein Beispiel für ein assoziatives Array geben, das nicht mit einer Hashtabelle implementiert ist?

    – gberth

    16. August um 19:59 Uhr

  • Sie könnten beispielsweise ein assoziatives Array mit dem einen oder anderen inkrementellen Sortieralgorithmus implementieren, ohne eine Hash-Funktion für die Schlüssel zu verwenden.

    – Greg Kuperberg

    17. August um 21:50 Uhr

Ein Array in PHP ist eigentlich eine geordnete Karte, keine Hashtabelle. Der Hauptunterschied zwischen Map und Hashtable besteht in der Unfähigkeit, sich an die Reihenfolge zu erinnern, in der Elemente hinzugefügt wurden. Andererseits sind Hashtables viel schneller als Karten. Die Komplexität des Abrufens eines Elements aus der Karte beträgt O (nlogn) und aus der Hashtabelle O (1).

Ein assoziatives Array ist ein Array, bei dem Sie nicht über einen Index, sondern über einen Schlüssel auf Elemente zugreifen. Wie dies intern funktioniert, ist implementierungsspezifisch (es gibt keine Regel, wie es funktionieren muss). Ein assoziatives Array könnte durch eine Hash-Tabelle implementiert werden (die meisten Implementierungen tun dies), aber es könnte auch durch eine Art Baumstruktur oder eine Skip-Liste implementiert werden, oder der Algorithmus iteriert einfach über alle Elemente im Array und sucht nach einem Schlüssel das passt (das wäre furchtbar langsam, aber es funktioniert).

Eine Hash-Tabelle ist eine Möglichkeit, Daten zu speichern, in denen Werte mit Schlüsseln verknüpft sind und in der Sie beabsichtigen, Werte für Schlüssel innerhalb einer (normalerweise fast) konstanten Zeit zu finden. Das klingt genau so, wie Sie es von einem assoziativen Array erwarten, deshalb werden die meiste Zeit Hash-Tabellen zur Implementierung dieser Arrays verwendet, aber das ist nicht zwingend erforderlich.

1352790cookie-checkHash-Tabellen VS assoziative Arrays

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy