Open address method hash open address method code implementation

Open address method hash open address method code implementation

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