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


data structure


//node data
type tableData struct {
    data int

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


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

Hash table


type hashTable struct {
    table [17]tableNode
    length int


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")


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