前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >开放地址法散列开放地址法代码实现

开放地址法散列开放地址法代码实现

作者头像
月见樽
发布2018-04-27 12:10:54
1.4K0
发布2018-04-27 12:10:54
举报

开放地址法

开放地址法是另一种(相对于分离链接法)解决散列冲突的方法。适用于装填因子(散列表中元素个数和散列表长度比)较小(小于0.5)的散列表。

开放地址法中索引的计算方法为$$h_{i}(x) = (Hash(X) + F(i)) % TableSize$$,其中:

  • Hash(x)为索引的计算方法
  • F(i)为冲突的解决函数,有F(0) = 0,i为已经尝试计算索引的次数

F(i)一般有:

  • 线性探测法:$$F(i) = i$$,即每次冲突则向下寻找1个位置,直到找到不冲突的位置,容易产生“一次聚集”的现象(数据集中在某一个地址区域)
  • 平方探测法:$$F(i)=i^{2}$$,每次冲突按平方寻找下一个位置,直到找到不冲突的位置
  • 双散列:$$F(i) = i\cdot hash_{2}(x)$$,即发生冲突后使用第二个散列函数计算下一个位置

代码实现

数据结构

结构体

代码语言:javascript
复制
// 节点数据
type tableData struct {
    data int
}

// 节点
type tableNode struct {
    flag bool       //是否已经插入数据,用于冲突检测
    key  string     //关键字
    data tableData  //节点数据
}

构造函数

代码语言:javascript
复制
func newTableNode(key string, data tableData) *tableNode {
    return &tableNode{false, key, data}
}

散列表

结构体

代码语言:javascript
复制
type hashTable struct {
    table  [17]tableNode
    length int
}

方法

计算散列值
代码语言:javascript
复制
func (h *hashTable) hashCompute(key string) int {
    hash := 0
    for i := range key {
        hash = hash + int(key[i])*32
    }
    return hash % h.length
}
插入方法
代码语言:javascript
复制
func (h *hashTable) insert(key string, data tableData) error {
    hash, i := h.hashCompute(key), 0
  
    // 若发生冲突,则搜索下一个位置 
    for i = 0; h.table[(i+hash)%h.length].flag != false && h.table[(i+hash)%h.length].key != key; i++ {
        if i == h.length {
            // 若找不到,则表满,返回错误
            return errors.New("table full")
        }
    }
    hash = (i + hash) % h.length
    
    // 插入数据
    h.table[hash].data = data
    h.table[hash].flag = true
    h.table[hash].key = key
    return nil
}
访问方法
代码语言:javascript
复制
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")
}

构造函数

代码语言:javascript
复制
func newHashTable() *hashTable {
    data := &hashTable{}
    data.length = 17
    for i := range data.table {
        data.table[i] = *newTableNode("", tableData{})
    }
    return data
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.01.23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 开放地址法
  • 代码实现
    • 数据结构
      • 结构体
      • 构造函数
    • 散列表
      • 结构体
      • 方法
      • 构造函数
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档