Double hashing is a computer programming technique used in conjunction with open addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs. Double hashing with open addressing is a classical data structure on a table .
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - Doppel-Hashing (de)
- Double hashing (en)
- 이중 해시 (ko)
- Double hashing (nl)
- 双散列 (zh)
|
rdfs:comment
| - 이중 해시법은 해시 충돌을 해결하기 위한 방법이다. 서로 다른 두 값들이 같은 해시 키를 갖게 되면 해시 충돌이 일어나게 된다. 충돌이 일어난 항목들을 따로 관리하지 않고 해시 테이블의 다른 주소 공간에 배열한다면 어디에 이것을 배열해야 하는지에 대한 문제가 생긴다. 이중 해시법은 다른 해시 함수로 값을 해시하여 그 값만큼을 현재 주소에 더하여 새 주소를 얻는다. 이렇게 되면 충돌시 건너뛰는 너비가 값에 따라 달라지기 때문에 한 해시 값에 뭉치는 경우가 줄어든다. 그리고 운이 나쁜 경우 계속 충돌이 일어나서 탐색 시간이 매우 오래 걸리게 되는 문제가 해결된다. (ko)
- In de informatica is double hashing een manier om collisies ('botsingen') bij het invoegen van een item in hashtabellen te verhelpen. Wanneer het invoegen op de positie die door de hashfunctie berekend is niet mogelijk is (doordat er al een item aanwezig is), wordt deze positie met een tweede hashfunctie verhoogd totdat een positie gevonden is. De berekende positie wordt modulo m berekend waarbij m de grootte van de hashtabel is. Hierdoor blijft de berekende waarde in het interval [0, m) van gehele getallen en dus binnen de hashtabel: mod m, met i = 0,1,2, ... (nl)
- 雙雜湊(Double hashing),是透過兩個雜湊函式來查詢位置。 例子: 假設; 沒有與第9格衝突,所以被安置到第9格 沒有與第8格衝突,所以被安置到第8格 與第9格衝突,所以需要 沒有與第6格衝突,所以被安置到第6格 與第8格衝突,所以需要 沒有與第3格衝突,所以被安置到第3格 與第9格衝突,所以需要 沒有與第0格衝突,所以被安置到第0格 (zh)
- Beim Doppelstreuwertverfahren oder Doppel-Hashing (englisch double hashing) handelt es sich um eine Methode zur Realisierung eines geschlossenen Hash-Verfahrens.In geschlossenen Hash-Verfahren wird versucht, Überläufer in der Hash-Tabelle unterzubringen, anstatt sie innerhalb der Zelle (z. B. als Liste) zu speichern. (Offene Hash-Verfahren können Einträge doppelt belegen und benötigen daher keine Sondierung.)Achtung: Wie es im Artikel Hashtabelle unter „Varianten des Hashverfahrens“ steht, werden die Bezeichnungen „offenes“ bzw. „geschlossenes Hashing“ auch in genau umgekehrter Bedeutung verwendet. (de)
- Double hashing is a computer programming technique used in conjunction with open addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs. Double hashing with open addressing is a classical data structure on a table . (en)
|
dct:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - Double hashing is a computer programming technique used in conjunction with open addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs. Double hashing with open addressing is a classical data structure on a table . The double hashing technique uses one hash value as an index into the table and then repeatedly steps forward an interval until the desired value is located, an empty location is reached, or the entire table has been searched; but this interval is set by a second, independent hash function. Unlike the alternative collision-resolution methods of linear probing and quadratic probing, the interval depends on the data, so that values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering. Given two random, uniform, and independent hash functions and , the th location in the bucket sequence for value in a hash table of buckets is: Generally, and are selected from a set of universal hash functions; is selected to have a range of and to have a range of . Double hashing approximates a random distribution; more precisely, pair-wise independent hash functions yield a probability of that any pair of keys will follow the same bucket sequence. (en)
- Beim Doppelstreuwertverfahren oder Doppel-Hashing (englisch double hashing) handelt es sich um eine Methode zur Realisierung eines geschlossenen Hash-Verfahrens.In geschlossenen Hash-Verfahren wird versucht, Überläufer in der Hash-Tabelle unterzubringen, anstatt sie innerhalb der Zelle (z. B. als Liste) zu speichern. (Offene Hash-Verfahren können Einträge doppelt belegen und benötigen daher keine Sondierung.)Achtung: Wie es im Artikel Hashtabelle unter „Varianten des Hashverfahrens“ steht, werden die Bezeichnungen „offenes“ bzw. „geschlossenes Hashing“ auch in genau umgekehrter Bedeutung verwendet. Um dies umzusetzen, verwendet man beim Doppel-Hashing eine Sondierungsfunktion, die eine sekundäre Hash-Funktion beinhaltet, z. B. , und die angewendet wird, falls der durch die primäre Hash-Funktion berechnete Index bereits besetzt ist. Die vollständige Hash-Funktion lautet dann: , wobei j die Anzahl bereits „ausprobierter“ Indizes ist, d. h., dass j jedes Mal um 1 erhöht wird, wenn ein Index bereits belegt ist. Die Sondierungsfunktion soll dabei eine Permutation der Indizes der Hash-Tabelle bilden. Die Folge von Hash-Funktionen, die nun mittels und gebildet werden, sieht so aus: Die Kosten für diese Methode sind nahe den Kosten für ein ideales Hashing. (de)
- 이중 해시법은 해시 충돌을 해결하기 위한 방법이다. 서로 다른 두 값들이 같은 해시 키를 갖게 되면 해시 충돌이 일어나게 된다. 충돌이 일어난 항목들을 따로 관리하지 않고 해시 테이블의 다른 주소 공간에 배열한다면 어디에 이것을 배열해야 하는지에 대한 문제가 생긴다. 이중 해시법은 다른 해시 함수로 값을 해시하여 그 값만큼을 현재 주소에 더하여 새 주소를 얻는다. 이렇게 되면 충돌시 건너뛰는 너비가 값에 따라 달라지기 때문에 한 해시 값에 뭉치는 경우가 줄어든다. 그리고 운이 나쁜 경우 계속 충돌이 일어나서 탐색 시간이 매우 오래 걸리게 되는 문제가 해결된다. (ko)
- In de informatica is double hashing een manier om collisies ('botsingen') bij het invoegen van een item in hashtabellen te verhelpen. Wanneer het invoegen op de positie die door de hashfunctie berekend is niet mogelijk is (doordat er al een item aanwezig is), wordt deze positie met een tweede hashfunctie verhoogd totdat een positie gevonden is. De berekende positie wordt modulo m berekend waarbij m de grootte van de hashtabel is. Hierdoor blijft de berekende waarde in het interval [0, m) van gehele getallen en dus binnen de hashtabel: mod m, met i = 0,1,2, ... (nl)
- 雙雜湊(Double hashing),是透過兩個雜湊函式來查詢位置。 例子: 假設; 沒有與第9格衝突,所以被安置到第9格 沒有與第8格衝突,所以被安置到第8格 與第9格衝突,所以需要 沒有與第6格衝突,所以被安置到第6格 與第8格衝突,所以需要 沒有與第3格衝突,所以被安置到第3格 與第9格衝突,所以需要 沒有與第0格衝突,所以被安置到第0格 (zh)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is known for
of | |
is known for
of | |
is foaf:primaryTopic
of | |