分离链接的散列散列代码实现

散列

散列为一种用于以常数平均时间执行插入,删除和查找的技术。一般的实现方法是使通过数据的关键字可以计算出该数据所在散列中的位置,类似于Python中的字典。关于散列需要解决以下问题:

  • 散列的关键字如何映射为一个数(索引)——散列函数
  • 当两个关键字的散列函数结果相同时,如何解决——冲突

散列函数

散列函数为关键字->索引的函数,常用的关键字为字符串,则需要一个字符串->整数的映射关系,常见的三种散列函数为:

  • ASCII码累加(简单)
  • 计算前三个字符的加权和$\sum key[i] * 27^{i}$ (不太好,3个字母的常用组合远远小于可能组合)
  • 计算所有字符加权和并对散列长度取余$(\sum key[i] * 32^{i}) % tablesize$(较好)
// 累加
func (n *node) hashSum() int {
    hash := 0
    for i := range n.key {
        hash += int(n.key[i])
    }
    return hash
}
// 前三个字符和
func (n *node) hashTop3() int {
    hash := 0
    time := utf8.RuneCountInString(n.key)
    if time > 3 {
        time = 3
    }
    for i := 0; i < time; i++ {
        hash += int(n.key[i])
    }
    return hash
}
// 所有字符和取余
func (n *node) hashMod(lenght int) int {
    hash := 0
    for i := range n.key {
        hash += int(n.key[i]) * 32
    }
    return hash % lenght
}

冲突

当不同关键字计算出的散列值相同时,发生冲突,本次使用分离链接法解决:

  • 每个散列中的数据结构有一个指针可以指向下一个数据,因此散列表可以看成链表头的集合
  • 当插入时,将数据插入在对应散列值的链表中
  • 访问时,遍历对应散列值的链表,直到找到关键字

代码实现

散列节点

结构体

type nodeData struct {
    data int
}

type node struct {
    key  string
    hash int
    data nodeData
    next *node
}

散列值计算(使用第三种)

func (n *node) HashCompute(lenght int) {
    n.hash = n.hashMod(lenght)
    // fmt.Println("key:", n.key, "hash:", n.hash)
}

构造函数

func newNode(data nodeData, key string) *node {
    temp := &node{key, 0, data, nil}
    return temp
}

散列表

结构体

type hashTable struct {
    table [17]node
}

插入方法

func (h *hashTable) insert(data nodeData, key string) {
    temp := newNode(data, key)
    temp.HashCompute(len(h.table))
    temp.next = h.table[temp.hash].next
    h.table[temp.hash].next = temp
}

访问方法

func (h *hashTable) visit(key string) (nodeData, error) {
    temp := newNode(nodeData{}, key)
    temp.HashCompute(len(h.table))
    //设计失误,仅有节点有计算散列值的方法,因此需要定义一个散列节点用于计算散列值
    point := h.table[temp.hash].next
    for point != nil {
        if point.key == key {
            return point.data, nil
        }
        point = point.next
    } //遍历链表,搜索关键字
    return temp.data, errors.New("not exsist")
    // 失败退出
}

构造函数

func newHashTable() *hashTable {
    temp := &hashTable{}
    for i := range temp.table {
        temp.table[i] = *newNode(nodeData{}, "")
    }
    return temp
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序猿DD

《JS正则表达式教程》汇总

正则表达式,又称规则表达式。(英语:Regular Expression,在代码中常简写为regex、regexp或RE),计算机科学的一个概念。正则表通常被用...

3496
来自专栏python3

习题21:函数可以返回东西

注释:上面例子,创建了加减乘除数学函数:add,subtract,multiply,以及divide 重要的是函数的最后一行,例如add的最后一

782
来自专栏木东居士的专栏

Counting Bloom Filter 的原理和实现

2954
来自专栏灯塔大数据

每周学点大数据 | No.23 外排序(二)

No.23期 外排序(二) Mr. 王:接下来我们用一个例子对磁盘归并排序进行说明。先来约定讨论的参数:N=24,M=8,B=2。 小可:嗯,一共有2...

3476
来自专栏小白的技术客栈

Python基础语法-流程控制

今天讲解Python的流程控制,流程控制也比较简单,小白不想整的很复杂,以免让大家看了有一种望“文”生怯的想法。 程序控制结构 通常的程序设计语言有三种控制结构...

3066
来自专栏Golang语言社区

使用 Go 语言学会 Tensorflow

Tensorflow 并不是一个专门用于机器学习的库,相反的,它是一个通用的用于图计算的库。它的核心部分是用 C++ 实现的,同时还有其它语言的接口库。Go 语...

4942
来自专栏光变

你所不知道的Java之Switch

??? Enum,String,Character,Byte,Short,Integer

1630
来自专栏JavaEdge

亿万级数据处理的高效解决方案简介从set/map到hashtable/hashmap/hashset秘技一:分而治之/Hash映射 + HashMap统计 + 堆/快速/归并排序堆秘技二:双层桶划分秘

1.2K7
来自专栏Java架构沉思录

从节省Redis内存空间说开去

上周部门会议上讨论的一个议题是如何节省Redis内存空间,其中有个小伙伴提到可以从压缩字符串入手,我觉得这是一个可以尝试的思路。因为有时候我们存在Redis中的...

1432
来自专栏阮一峰的网络日志

Pointfree 编程风格指南

本文要回答一个很重要的问题:函数式编程有什么用? 目前,主流的编程语言都不是函数式的,已经能够满足需求。为何还要学函数式编程呢,只为了多理解一些新奇的概念? ?...

3617

扫码关注云+社区

领取腾讯云代金券