開放地址法

開放地址法是另一種（相對(duì)于分離鏈接法）解決散列沖突的方法。適用于裝填因子（散列表中元素個(gè)數(shù)和散列表長(zhǎng)度比）較小（小于0.5）的散列表。

開放地址法中索引的計(jì)算方法為$$h_{i}(x) = (Hash(X) + F(i)) % TableSize$$，其中：

• Hash(x)為索引的計(jì)算方法
• F(i)為沖突的解決函數(shù)，有F(0) = 0，i為已經(jīng)嘗試計(jì)算索引的次數(shù)

F(i)一般有：

• 線性探測(cè)法：$$F(i) = i$$，即每次沖突則向下尋找1個(gè)位置，直到找到不沖突的位置，容易產(chǎn)生“一次聚集”的現(xiàn)象（數(shù)據(jù)集中在某一個(gè)地址區(qū)域）
• 平方探測(cè)法：$$F(i)=i^{2}$$，每次沖突按平方尋找下一個(gè)位置，直到找到不沖突的位置
• 雙散列：$$F(i) = i\cdot hash_{2}(x)$$，即發(fā)生沖突后使用第二個(gè)散列函數(shù)計(jì)算下一個(gè)位置

代碼實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)

結(jié)構(gòu)體

// 節(jié)點(diǎn)數(shù)據(jù)
type tableData struct {
    data int
}

// 節(jié)點(diǎn)
type tableNode struct {
    flag bool       //是否已經(jīng)插入數(shù)據(jù)，用于沖突檢測(cè)
    key  string     //關(guān)鍵字
    data tableData  //節(jié)點(diǎn)數(shù)據(jù)
}

構(gòu)造函數(shù)

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

散列表

結(jié)構(gòu)體

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

方法

計(jì)算散列值

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

插入方法

func (h *hashTable) insert(key string, data tableData) error {
    hash, i := h.hashCompute(key), 0
  
    // 若發(fā)生沖突，則搜索下一個(gè)位置 
    for i = 0; h.table[(i+hash)%h.length].flag != false && h.table[(i+hash)%h.length].key != key; i++ {
        if i == h.length {
            // 若找不到，則表滿，返回錯(cuò)誤
            return errors.New("table full")
        }
    }
    hash = (i + hash) % h.length
    
    // 插入數(shù)據(jù)
    h.table[hash].data = data
    h.table[hash].flag = true
    h.table[hash].key = key
    return nil
}

訪問方法

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

構(gòu)造函數(shù)

func newHashTable() *hashTable {
    data := &hashTable{}
    data.length = 17
    for i := range data.table {
        data.table[i] = *newTableNode("", tableData{})
    }
    return data
}