# Open address law

Open address method is another method (as opposed to separate link method) to resolve hash conflicts. It is suitable for hash tables with a small filling factor (the ratio of the number of elements in the hash table to the length of the hash table) (less than 0.5).

The index calculation method in the open address method is $$h_{i}(x) = (Hash(X) + F(i))% TableSize$$, where:

• Hash(x) is the calculation method of the index
• F(i) is the conflict resolution function, F(0) = 0, i is the number of attempts to calculate the index

F(i) generally has:

• Linear detection method: $$F(i) = i$$, that is, look for a position downward for each conflict until a non-conflicting position is found, which is prone to "aggregate at one time" (the data is concentrated in a certain address area) )
• Square detection method: $$F(i)=i^{2}$$, find the next position by the square for each conflict until a non-conflicting position is found
• Double hash: $$F(i) = i\cdot hash_{2}(x)$$, that is, use the second hash function to calculate the next position after a conflict occurs

# Code

## data structure

### Structure

//node data
type tableData struct {
data int
}

//node
type tableNode struct {
flag bool//Whether data has been inserted for conflict detection
key string//Keyword
data tableData//Node data
}

### Constructor

func newTableNode(key string, data tableData) *tableNode {
return &tableNode{false, key, data}
}

## Hash table

### Structure

type hashTable struct {
table [17]tableNode
length int
}

### method

#### Calculate the hash value

func (h *hashTable) hashCompute(key string) int {
hash := 0
for i := range key {
hash = hash + int(key[i])*32
}
return hash% h.length
}

#### Insert method

func (h *hashTable) insert(key string, data tableData) error {
hash, i := h.hashCompute(key), 0

//If there is a conflict, search for the next location
for i = 0; h.table[(i+hash)%h.length].flag != false && h.table[(i+hash)%h.length].key != key; i++ {
if i == h.length {
//If it is not found, the table is full and an error is returned
return errors.New("table full")
}
}
hash = (i + hash)% h.length

//insert data
h.table[hash].data = data
h.table[hash].flag = true
h.table[hash].key = key
return nil
}

#### Access method

func (h *hashTable) visit(key string) (tableData, error) {
hash := h.hashCompute(key)
for index := 0; h.table[(index+hash)%h.length].flag == true; index++ {
if h.table[(index+hash)%h.length].key == key {
return h.table[(index+hash)%h.length].data, nil
}
}
return tableData{}, errors.New("not find")
}

### Constructor

func newHashTable() *hashTable {
data := &hashTable{}
data.length = 17
for i := range data.table {
data.table[i] = *newTableNode("", tableData{})
}
return data
}
Reference: https://cloud.tencent.com/developer/article/1110777 Open Address Method Hashing Open Address Method Code Implementation-Cloud + Community-Tencent Cloud