扫码订阅《 Go语言算法与数据结构》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • 课程介绍

    • 《Go语言算法与数据结构》
  • 算法

    • 快速排序算法
    • 堆排序算法
    • 冒泡排序算法
    • 二分查找方法
    • 选择排序算法
    • 基数排序算法
    • 拓扑排序
    • 插入排序算法
    • 字符串匹配
    • 二叉搜索树
  • 数据结构

    • 图
    • 散列表
    • 堆
    • 链表
    • 跳跃表
    • 字典树

扫码订阅《 Go语言算法与数据结构》或入驻星球,即可阅读文章!

散列表


GOLANG ROADMAP

# 散列表

# 散列表分类

  • 线性探索散列表
  • 链表式散列表

# 时间复杂度

  • 修改(增删改)时间复杂度 O(1)
  • 查询时间复杂度O(1)
package hash

import (
    "bytes"
    "crypto/md5"
    "crypto/sha1"
    "encoding/binary"
    "fmt"
)

//无链表的散列表
type NoLinkHashTable struct {
    Buckets  []Bucket
    Capacity int32
    Used     int32
}

//桶
type Bucket struct {
    HKey string
    Data int
}

func NolinkHashTable(length int32) {
    //新建算列表
    ht := NoLinkHashTable{}
    ht.Capacity = length
    ht.Buckets = make([]Bucket, length)
    for i := 0; i < 5; i++ {
        ht.hSet("abc", i)
    }
    fmt.Println(ht)
    one := ht.hGet("abc")
    fmt.Println(one)
}

func (ht *NoLinkHashTable) hSet(key string, value int) {
    bucket := Bucket{key, value}
    hashCode := GetHashCode(key, 1)
    index := hashCode % (ht.Capacity - 1)
    ht.addBucket(index, key, bucket)
}

func (ht *NoLinkHashTable) hGet(key string) Bucket {
    hashCode := GetHashCode(key, 1)
    index := hashCode % (ht.Capacity - 1)
    return ht.findBucket(index, key)
}

func (ht *NoLinkHashTable) findBucket(index int32, key string) Bucket {
    var empty = Bucket{}
    if ok := ht.Buckets[index]; ok != empty {
        if ht.Buckets[index].HKey == key {
            return ht.Buckets[index]
        } else {
            index++
        }
        for {
            if ok := ht.Buckets[index]; ok != empty {
                if ht.Buckets[index].HKey == key {
                    return ht.Buckets[index]
                } else {
                    index++
                }
            } else {
                return empty
            }

        }
    }
    return empty
}

func (ht *NoLinkHashTable) addBucket(index int32, key string, bucket Bucket) {
    if ht.Capacity == ht.Used {
        panic("Table is full")
    }
    var empty = Bucket{}
    if ok := ht.Buckets[index]; ok != empty {
        if ok.HKey == key {
            ht.Buckets[index] = bucket
            return
        }
        //已经存在
        index++
        for {
            //fmt.Println(index)
            if index >= ht.Capacity {
                index = 0
            }
            if ok := ht.Buckets[index]; ok != empty {
                if ok.HKey == key {
                    ht.Buckets[index] = bucket
                    return
                }
                index++
            } else {
                ht.Buckets[index] = bucket
                ht.Used++
                break
            }
        }
    } else {
        ht.Buckets[index] = bucket
        ht.Used++
    }

}
func GetHashCode(key string, hashType int) int32 {
    var Result []byte
    switch hashType {
    case 1:
        Md5Inst := md5.New()
        Md5Inst.Write([]byte(key))
        Result = Md5Inst.Sum([]byte(""))
    case 2:
        Sha1Inst := sha1.New()
        Sha1Inst.Write([]byte(key))
        Result = Sha1Inst.Sum([]byte(""))
    }
    bin_buf := bytes.NewBuffer(Result)
    var x int32
    binary.Read(bin_buf, binary.BigEndian, &x)
    return x
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
  • 散列表
  • 散列表分类
  • 时间复杂度