Unterschied zwischen Internen Hash-und Externen Hash
Aus dem Buch " Fundamentals of Database Systems:
Interne Hash -
Für interne Dateien, Hash-Regel implementiert als hash-Tabelle durch den Einsatz
der ein array von Datensätzen. Angenommen, der array-index reicht von 0 bis M – 1, als
in Abbildung 17.8(a); dann haben wir M-Steckplätze, deren Adressen entsprechen den
array-Indizes. Wir wählen eine hash-Funktion, die wandelt hash-Wert in Feld
eine Ganzzahl zwischen 0 und M − 1. Eine gemeinsame hash-Funktion ist h(K) = K mod
M-Funktion, die liefert den Rest einer integer-hash-Feld mit dem Wert K nach divi-
sion von M; dieser Wert wird dann verwendet, um den Datensatz Adresse. [...]Einer Kollision tritt auf, wenn die hash-Feld-Wert, der einen Datensatz, der eingefügt wird hashes
eine Adresse enthält bereits ein anderer Rekord.
Externen Hash -
Hash für Dateien auf der Festplatte wird als externe hashing. Passen die Merkmale der Festplatte
Lagerung, den Ziel-Adressbereich aus Eimern, die jeweils mehrere
Aufzeichnungen. Ein Eimer ist entweder ein disk-block oder ein cluster zusammenhängender disk-Blöcke. Die
Hash-Funktion ordnet einem Schlüssel in eine relative bucket Zahl, sondern als Zuweisung einer
absolute block-Adresse, um den Eimer. Eine Tabelle gepflegt, in der header-Datei konvertiert
die bucket-Nummer in das entsprechende disk-block-Adresse, wie in dargestellt
Abbildung 17.9.
Die Kollision problem ist weniger schwerwiegend mit Eimer, denn wie viele Aufnahmen passen
in einem bucket können hash an den gleichen Eimer ohne Probleme.
Ich habe folgende Frage:
1) Ein record ist immer aufgezeichnet innerhalb eines Blocks, also nicht die interne hash-Rückkehr der block-Adresse und die position des Datensatzes innerhalb des Blocks?
2) Warum ist die Kollision problem ist weniger schwerwiegend mit externen hash? Ich meine, nehmen wir an, dass jeder block speichern können 10 Datensätze; ich spekulieren, dass die Datei, die ich speichern kann, enthält 100 Datensätze, dann mit externen hash, ich zuordnen, vielleicht 11-12 Eimer(ich gehe davon aus, dass ein Eimer=1 block), so dass die hash-Funktion zurückgeben 10-12-Adresse, an die Eimer.
Wenn ich einen internen Hashwert, weil die hash-Funktion liefert eine direkte Adresse, die ich benutzen würde-Funktionen, die Rückkehr zu mir über 100-120-Adressen.
Also, was ist der Unterschied? Auf diese Weise ich denke, ich habe die gleiche Wahrscheinlichkeit der Kollision mit den beiden Methoden.
- Bitte benennen Sie das Buch. 1) Die Umsetzung wählen kann, oder sogar durchführen sekundären hashing 2) es scheint mir Ihr Recht. Ich sehe keinen Unterschied gibt.
- Ich habe das Buch-Titel. Was meinst du mit "Die Implementierung wählen kann, oder sogar durchführen sekundäre Vermischung"?
- Es war eine Antwort auf "Ein Rekord ist immer aufgezeichnet innerhalb eines Blocks, also nicht die interne hash-Rückkehr der block-Adresse und die position des Datensatzes innerhalb des Blocks?" Die Implementierung der hashtable können wählen, um zu berechnen, nur block-Adresse und führen Sie eine lineare Suche innerhalb des Blocks, oder berechnen eine Adresse innerhalb des Blocks zu.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Soweit ich das verstanden habe, kann man sich bei 'externen hashing' wie 'open hashing'. In offenen hashing, was wir tun, ist, jedes Element in der hash-Tabelle verweist auf eine eindeutige Liste für das speichern mehrerer Schlüssel. Also wenn die Kollision Auftritt, die Schlüssel sind eingetragen in der Liste hingewiesen, die durch die hash-table-element. Auf diese Weise gibt es weniger chance der Kollision( es hängt von der Größe der Liste). Ich fand diese Folie sehr hilfreich, einen Blick (Folie Nummer 30 & 32) - http://www.slideshare.net/gourab87/chapter13-8045092
Die interne Hash ist ein array, das die Adresse enthält, der die Raute-Taste. Deshalb ist jedes array-index kann nur enthalten eine Adresse in der hash-Schlüssel so, wenn ein anderer hash-Schlüssel weist auf den gleichen index des Arrays dies führt zu einer Kollision. Auf der anderen Seite, externes hashing ist vor allem Eimer M. Und jeden bucket können, besetzen mehr als eine hash-Schlüssel. Daher Kollision geschehen wird, wenn der Eimer voll ist.