If there is a case where you can map each element to a different slot for any set of elements, there will never be collisions.
This is called a perfect hash function, but only happens if the number of elements in the set and the value of the elements are determined. In other cases this perfect hash function does not exist.
So when two elements are placed in the same slot, a second element must be placed in the hash table through a systematic method called collision handling.
There are two broad categories of approaches to conflict management
There are two main ways to deal with conflicts:
- detection
- Link method
Suppose we use the division remainder function as a hash function and put the following elements 21, 15, 16, 17, 11, 20, 22, 33, 9 into the hash table with slot 11. Let’s look at the application of the following two conflict handling methods.
detection
One way is to find another empty slot in the hash table for the element causing the conflict.
Linear detection method
The simple way to do this is to start with the original hash value and iterate sequentially through the hash table until an empty slot is found. Note that in order to iterate over the hash table, you may need to check back to the first slot. This process, called open addressing, tries to find the next empty slot or address in a hash table. Because you access slots one by one, this is called linear probing.
The process of adding 21, 15, 16, 17, 11, 20, 22, 33, 9 to the hash table with slot number 11 is shown in the figure below:
When 22 is inserted, it should be inserted into slot 0, but slot 0 already has data, so find the next empty slot, namely slot 1.
When 33 is inserted, it should be put into slot 0, but the data already exists, so look for the next empty slot, namely slot 2.
When slot 9 is inserted, slot 9 should be inserted into slot 9. However, slot 9 already has data. Therefore, slot 10, slot 0, slot 1, and slot 2 are accessed successively until slot 3 is empty, so slot 9 is inserted into slot 3.
Final Location:
Extended linear detection method
However, the above linear detection method will cause elements to cluster and occupy the slots of other elements. For example, if the hashes of 11, 22, and 33 are 0, they should be placed in slot 0. However, only one element can be placed in a slot. As a result, slot 22 and 33 occupy slot 1 and slot 2. In this case, if 12 is inserted, its hash value is 1, but slot 1 is occupied, so all 12’s have to go into the next empty slot.
In order to solve the problem of element aggregation, we can use a step size greater than 1 to find the next empty slot, which is called extended linear detection method. For example, put 21, 15, 16, 17, 11, 20, 22, 33, 9 into a hash table with slot 11. Suppose we find the next empty slot with a step size of 3(i.e. skip two slots) when a conflict occurs. Then, when we insert 22 into the hash table, its hash value is 0. At this time, since the element 11 has been stored in slot 0, there is a conflict. Then, we use “add 3” to skip two slots and look for empty slot 3. The process is the same for 33 and 9. Final result:
Link method
Another way to handle collisions is to allow a slot to point to a set or linked list of multiple elements, called chaining. When a conflict occurs, the element is still inserted into the slot corresponding to its hash value. Using the above example as an example, the final result is shown below:
Golang implementation with division function as hash function and linear detection method as conflict handling method:
package main
import "fmt"
type HashTable struct {
ht []int
}
func (HT *HashTable) init(length int) {
// Create a hash table with slot number 11 to store unsigned integers
HT.ht = make([]int, length)
for i := 0; i <= 10; i++ {
// Initialize. -1 indicates that the slot is not in use
HT.ht[i] = - 1}}func (HT *HashTable) set(item int) {
mod := mod(item, len(HT.ht))
// If there is no conflict, the value is assigned directly
if HT.ht[mod] == - 1 {
HT.ht[mod] = item
} else {
// Otherwise, hash to get an empty slot
forHT.ht[mod] ! =- 1 {
mod = HT.rehash(mod)
// If the slot holds the same data as the element to be inserted, exit the loop
if HT.ht[mod] == item {
break
}
}
HT.ht[mod] = item
}
}
func (HT *HashTable) isExist(item int) bool {
mod := mod(item, len(HT.ht))
if HT.ht[mod] == item {
return true
} else {
// There may be conflicts between the storage and other slots
// We need to iterate over the other slots except the hash value itself
slot := mod
mod = HT.rehash(mod)
formod ! = slot {if HT.ht[mod] == item {
return true
} else {
mod = HT.rehash(mod)
}
}
return false}}func mod(item int, htLength int) int {
return item % htLength
}
func (HT *HashTable) rehash(mod int) int {
if mod == (len(HT.ht) - 1) {
return 0
} else {
return mod + 1}}func main(a) {
ht := HashTable{}
// Initialize to a hash table with 11 slots
ht.init(11)
// Write 10 to the hash table
ht.set(0)
// Hash search for whether 10 exists in the hash table
fmt.Println(ht.isExist(0))
// true
// Write 11 to the hash table
ht.set(11)
// Hash search to see if 11 exists in the hash table
fmt.Println(ht.isExist(11))
// true
// Write 22 to the hash table
ht.set(22)
// Hash search 22 to see if it exists in the hash table
fmt.Println(ht.isExist(22))
// true
// write 33 to the hash table
ht.set(33)
// Hash search to see if 33 exists in the hash table
fmt.Println(ht.isExist(33))
// true
// Write 33 to the hash again
ht.set(33)
// Hash search to see if 33 exists in the hash table
fmt.Println(ht.isExist(33))
// true
fmt.Println(ht.ht)
// [0 11 22 33-1-1-1-1-1]
}
Copy the code