Brent hashing
Brent hashing (also double hashing with Brent's algorithm ) is a calculation method for a hash function that was developed by the Australian mathematician Richard P. Brent and published in 1973. Brent hashing uses only the space in the hash table to store new entries and is a closed hashing method. Brent hashing was originally developed to make double hashing more efficient, but it can be applied to any closed hashing with success. Brent hashing provides efficiency gains in practice, but is difficult to analyze with a theoretical approach.
With open hashing, a list is added to each position in the hash table, while with closed hashing (also known as "hashing with open addressing") a different position is sought in the hash table if the position sought is already occupied (collision case) . The order in which the algorithm searches the hash table for possible positions is known as the “probing sequence” (also known as the “probing chain”). The shorter the average probing sequence in the event of a collision, the more efficient the algorithm. In contrast to double hashing , the Brent algorithm selects whether the new entry or the colliding entry already in the table is to be moved. In this way long probing sequences can be avoided and the algorithm becomes more efficient.
Collision handling
The status is also saved for each cell in the hash table . The status is "free", "occupied" or "removed" (if an element was previously deleted from this cell). An element (new) is to be inserted and collides with an element (old) already in the table.
Case 1: h '(new) is free: The new element is saved on h' (new).
Case 2: h '(new) is occupied and h' (old) is free: The old element is moved to h '(old) and the new element takes the place of the old element.
Case 3: h '(new) is assigned and h' (old) is assigned: The function is called recursively. Once again, a distinction must be made between the three cases. The next element (old) is the element on h '(new).
General implementation
Pseudocode:
funktion INSERT-BRENT-HASHING(hashtab,wert)
i := h(wert)
while hashtab[i].zustand = belegt
do
neufolgt := (i + h'(wert)) mod hashtablänge
altfolgt := (i + h'(hashtab[i].key)) mod hashtablänge
if hashtab[neufolgt].zustand = frei oder hashtab[altfolgt].zustand = belegt
then i := neufolgt
else hashtab[altfolgt].key := hashtab[i].key
hashtab[altfolgt].zustand := belegt
hashtab[i].zustand := entfernt
hashtab[i].key := wert
hashtab[i].zustand := belegt
example
The following modification of the pseudocode was used for the example:
neufolgt := (i - h'(wert)) mod hashtablänge altfolgt := (i - h'(hashtab[i].key)) mod hashtablänge
where the following hash functions were used:
h(wert) = wert mod 13 h'(wert) = 1 + wert mod 11
Sequence of the algorithm
insert 14 i := 14 mod 13 = 1 // keine Kollision hashtab[i].zustand = hashtab[1].zustand = frei
insert 21 i := 21 mod 13 = 8 // keine Kollision hashtab[i].zustand = hashtab[8].zustand = frei
insert 27 i := 27 mod 13 = 1 // 1. Kollision hashtab[i].zustand = hashtab[1].zustand = belegt // Indexneuberechnung neufolgt := (1 - (1 + 27 mod 11)) mod 13 = 8 altfolgt := (1 - (1 + 14 mod 11)) mod 13 = 10 // Prüfung auf freien Platz hashtab[neufolgt].zustand = belegt hashtab[altfolgt].zustand = frei // Vertauschen der Schlüssel hashtab[altfolgt].key = hashtab[10].key = hashtab[1].key := 14 hashtab[i].key = hashtab[1].key := 27
insert 28 i := 28 mod 13 = 2 // keine Kollision hashtab[i].zustand = hashtab[2].zustand = frei
insert 8 i := 8 mod 13 = 8 // 1. Kollision hashtab[i].zustand = hashtab[8].zustand = belegt // Indexneuberechnung neufolgt: (8 - (1 + 8 mod 11)) mod 13 = 12 altfolgt: (8 - (1 + 21 mod 11)) mod 13 = 10 // Prüfung auf freien Platz hashtab[neufolgt].zustand = frei hashtab[altfolgt].zustand = belegt // Einfügen des Schlüssels i := neufolgt = 12 hashtab[i].key = hashtab[12].key := 8
insert 18 i := 18 mod 13 = 5 // keine Kollision hashtab[i].zustand = hashtab[5].zustand = frei
insert 15 i := 15 mod 13 = 2 // 1. Kollision hashtab[i].zustand = hashtab[2].zustand = belegt // Indexneuberechnung neufolgt := (2 - (1 + 15 mod 11)) mod 13 = 10 altfolgt := (2 - (1 + 28 mod 11)) mod 13 = 8 // Prüfung auf freien Platz hashtab[neufolgt].zustand = belegt hashtab[altfolgt].zustand = belegt // 2. Kollision i := neufolgt = 10 hashtab[i].zustand = hashtab[10].zustand = belegt // Indexneuberechnung neufolgt: (10 - (1 + 15 mod 11)) mod 13 = 5 altfolgt: (10 - (1 + 14 mod 11)) mod 13 = 6 // Prüfung auf freien Platz hashtab[neufolgt].zustand = belegt hashtab[altfolgt].zustand = frei // Vertauschen der Schlüssel hashtab[altfolgt].key = hashtab[6]:= hashtab[i].key = hashtab[10] = 14 hashtab[i].key = hashtab[10]:= 15
insert 36 i := 36 mod 13 = 10 // 1. Kollision hashtab[i].zustand = hashtab[10].zustand = belegt // Indexneuberechnung neufolgt := (10 - (1 + 36 mod 11)) mod 13 = 6 altfolgt := (10 - (1 + 15 mod 11)) mod 13 = 5 // Prüfung auf freien Platz hashtab[neufolgt].zustand = belegt hashtab[altfolgt].zustand = belegt // 2. Kollision i := neufolgt = 6 hashtab[i].zustand = hashtab[6].zustand = belegt // Indexneuberechnung neufolgt := (6 - (1 + 36 mod 11)) mod 13 = 2 altfolgt := (6 - (1 + 14 mod 11)) mod 13 = 2 // Prüfung auf freien Platz hashtab[neufolgt].zustand = belegt hashtab[altfolgt].zustand = belegt // 3. Kollision i := neufolgt = 2 hashtab[i].zustand = hashtab[2].zustand = belegt // Indexneuberechnung neufolgt := (2 - (1 + 36 mod 11)) mod 13 = 11 altfolgt := (2 - (1 + 28 mod 11)) mod 13 = 8 // Prüfung auf freien Platz hashtab[neufolgt].zustand = frei hashtab[altfolgt].zustand = belegt // Einfügen des Schlüssels i := neufolgt = 11 hashtab[i].key = hashtab[11].key:= 36
insert 5 i := 5 mod 13 = 5 // 1. Kollision hashtab[i].zustand = hashtab[5].zustand = belegt // Indexneuberechnung neufolgt := (5 - (1 + 5 mod 11)) mod 13 = 12 altfolgt := (5 - (1 + 18 mod 11)) mod 13 = 10 // Prüfung auf freien Platz hashtab[neufolgt].zustand = belegt hashtab[altfolgt].zustand = belegt // 2. Kollision i := neufolgt = 12 hashtab[i].zustand = hashtab[12].zustand = belegt // Indexneuberechnung neufolgt := (12 - (1 + 5 mod 11)) mod 13 = 6 altfolgt := (12 - (1 + 8 mod 11)) mod 13 = 3 // Prüfung auf freien Platz hashtab[neufolgt].zustand = belegt hashtab[altfolgt].zustand = frei // Vertauschen der Schlüssel hashtab[altfolgt].key = hashtab[3].key:= hashtab[i].key = hashtab[12].key = 8 hashtab[i].key = hashtab[12].key:= 5
insert 2 i := 2 mod 13 = 2 // 1. Kollision hashtab[i].zustand = hashtab[2].zustand = belegt // Indexneuberechnung neufolgt := (2 - (1 + 2 mod 11)) mod 13 = 12 altfolgt := (2 - (1 + 28 mod 11)) mod 13 = 8 // Prüfung auf freien Platz hashtab[neufolgt].zustand = belegt hashtab[altfolgt].zustand = belegt // 2. Kollision i := neufolgt = 12 hashtab[i].zustand = hashtab[12].zustand = belegt // Indexneuberechnung neufolgt := (12 - (1 + 2 mod 11)) mod 13 = 9 altfolgt := (12 - (1 + 8 mod 11)) mod 13 = 3 // Prüfung auf freien Platz hashtab[neufolgt].zustand = frei hashtab[altfolgt].zustand = belegt // Einfügen des Schlüssels i := neufolgt = 9 hashtab[i].key = hashtab[9].key:= 2
Resulting table
| insert | 14th | 21st | 27 | 28 | 8th | 18th | 15th | 36 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | ||||||||||
| 1 | 14th | 14th | 27 | 27 | 27 | 27 | 27 | 27 | 27 | 27 |
| 2 | 28 | 28 | 28 | 28 | 28 | 28 | 28 | |||
| 3 | 8th | 8th | ||||||||
| 4th | ||||||||||
| 5 | 18th | 18th | 18th | 18th | 18th | |||||
| 6th | 14th | 14th | 14th | 14th | ||||||
| 7th | ||||||||||
| 8th | 21st | 21st | 21st | 21st | 21st | 21st | 21st | 21st | 21st | |
| 9 | 2 | |||||||||
| 10 | 14th | 14th | 14th | 14th | 15th | 15th | 15th | 15th | ||
| 11 | 36 | 36 | 36 | |||||||
| 12 | 8th | 8th | 8th | 8th | 5 | 5 |
Individual evidence
- ^ Richard P. Brent: Reducing the retrieval time of scatter storage techniques. In: Communications of the ACM. Volume 16, Issue 2, 1973, pp. 105-109.
- ^ Dinesh P. Mehta, Sartaj Sahni: Handbook of data structures and applications. CRC Press, 2004, ISBN 1-58488-435-5 , pp. 9-9 to 9-13.