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

开放地址法

开放地址法是另一种(相对于分离链接法)解决散列冲突的方法。适用于装填因子(散列表中元素个数和散列表长度比)较小(小于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)$$,即发生冲突后使用第二个散列函数计算下一个位置

代码实现

数据结构

结构体

// 节点数据
type tableData struct {
    data int
}

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

构造函数

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

散列表

结构体

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

方法

计算散列值

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
  
    // 若发生冲突,则搜索下一个位置 
    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
}

访问方法

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
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 替换空格

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

1681
来自专栏JavaEdge

UML 类图1 类

在UML 2.0的13种图形中,类图是使用频率最高的UML图之一。Martin Fowler在其著作《UML Distilled: A Brief Guide ...

3721
来自专栏mini188

java中的锁

java中有哪些锁 这个问题在我看了一遍<java并发编程>后尽然无法回答,说明自己对于锁的概念了解的不够。于是再次翻看了一下书里的内容,突然有点打开脑门的感觉...

4399
来自专栏祝威廉

ElasticSearch Aggregations GroupBy 实现源码分析

也就是按newtype 字段进行group by,然后对num求平均值。在我们实际的业务系统中,这种统计需求也是最多的。

3933
来自专栏机器学习算法与Python学习

pandas入门教程

pandas是一个Python语言的软件包,在我们使用Python语言进行机器学习编程的时候,这是一个非常常用的基础编程库。本文是对它的一个入门教程。

2382
来自专栏TechBox

一份走心的iOS开发规范前言约定(一)命名规范(二)编码规范2.14 内存管理规范本文参考文章其他有价值的文章

5698
来自专栏对角另一面

lodash源码分析之数组的差集

外部世界那些破旧与贫困的样子,可以使我内心世界得到平衡。 ——卡尔维诺《烟云》 本文为读 lodash 源码的第十七篇,后续文章会更新到这个仓库中,欢迎 s...

42114
来自专栏FreeBuf

浅析ReDoS的原理与实践

*本文原创作者:MyKings,本文属FreeBuf原创奖励计划,未经许可禁止转载 ReDoS(Regular expression Denial of Ser...

7315
来自专栏nimomeng的自我进阶

Collection官方文档

a) Keys必须实现NSCopying协议。添加成员的方法并不将每一个key直接进行添加,而是将每一个key进行copy并将copy后对象添加...

1564
来自专栏用户2442861的专栏

如何给10^7个数据量的磁盘文件排序

第一节、如何给磁盘文件排序 问题描述: 输入:一个最多含有n个不重复的正整数(也就是说可能含有少于n个不重复正整数)的文件,其中每个数都小于等于n,且n=...

652

扫码关注云+社区

领取腾讯云代金券