12 - go简单实现hashmap

注意:还没有解决hash冲突和hash倾斜的问题。

package main
import "fmt"
var nowCapacity = 10 //当前容量
const maxCapacity = 100 //最大容量
const loadFactor = 0.75 //负载因子(决定扩容因数)
type Entry struct {
 k string //key
 v interface{} //值
 next *Entry
}
type HashMap struct {
 size int //map的大小
 bucket []Entry //存放数据的桶,为slice
}
//创建一个CreateHashMap的函数,返回一个HashMap指针
func CreateHashMap() *HashMap {
 hm := &HashMap{0, make([]Entry, nowCapacity, maxCapacity)}
 return hm
}
//创建一个Put函数入参是key和value对HashMap进行插入操作
func (hm *HashMap) Put(k string, v interface{}) {
 entry := Entry{k, v, nil}
 //插入HashMap中
 hm.insert(entry)
 //如果比例大于负载因子就需要扩容
 if float64(hm.size)/float64(len(hm.bucket)) > loadFactor {
 if nowCapacity*2 > maxCapacity {
 nowCapacity = maxCapacity
 } else {
 nowCapacity = nowCapacity * 2
 }
 //创建一个新的HashMap
 newHm := HashMap{0, make([]Entry, nowCapacity, maxCapacity)}
 //遍历所有的entry,插入新的HashMap中(原来的数据迁移)
 for _, v := range hm.bucket {
 if v.k == "" {
 continue
 }
 for v.next != nil {
 newHm.insert(v)
 v = *v.next
 }
 newHm.insert(v)
 }
 newHm.size = hm.size
 //通过指针赋值新的Map
 *hm = newHm
 }
}
//真正的插入函数
func (hm *HashMap) insert(entry Entry) {
 //计算entry的插入位置
 index := hashCode(entry.k, nowCapacity)
 //根据计算出来的位置,获得当前位置第一个entry位置的指针
 e := &hm.bucket[index]
 //判断第一个位置entry的key是不是空字符串,
 //如果是空,直接插入;
 if e.k == "" {
 hm.size++
 *e = entry
 return
 } else {
 //循环当前位置上所有entry,
 //如果有entry的key和当前要插入的entry的key相等就进行覆盖
 for e.next != nil {
 if e.k == entry.k {
 *e = entry
 return
 }
 //直达最后一个entry
 e = e.next
 }
 //判断链表尾部entry的key和当前要插入的entry的key是否相等
 //相等就进行覆盖,没有就将新的entry插入到链表的末尾
 if e.k == entry.k {
 *e = entry
 return
 }
 hm.size++
 e.next = &entry
 }
}
//查询方法:Get
func (hm *HashMap) Get(k string) interface{} {
 //通过hash函数查询出k在slice存放的位置
 index := hashCode(k, nowCapacity)
 //或者计算位置的entry指针(或者说链表)
 e := &hm.bucket[index]
 //查询结果为空
 if e.k == "" {
 return nil
 } else {
 //遍历
 for e.next != nil {
 if e.k == k {
 return e.v
 }
 //直到链表最后
 e = e.next
 }
 //通过hash函数查询出k在slice存放的位置
 if e.k == k {
 return e.v
 }
 return nil
 }
}
//自定义散列函数(得出存放位置)
func hashCode(k string, length int) int {
 sum := 0
 b := []byte(k)
 for _, v := range b {
 sum += int(v)
 }
 return sum % length
}
func main() {
 hm := CreateHashMap()
 hm.Put("a", 1)
 hm.Put("b", 2)
 hm.Put("c", "c")
 hm.Put("d", "c")
 hm.Put("e", "c")
 hm.Put("f", "f")
 hm.Put("g", "g")
 hm.Put("h", "h")
 hm.Put("c", "kkkk")
 fmt.Println(hm.Get("a"))
 fmt.Println(hm.Get("b"))
 fmt.Println(hm.Get("c"))
 fmt.Println(hm.Get("g"))
 fmt.Println(hm.Get("h"))
 fmt.Println(hm)
}

参考:

1.go中map实现的原理

2. 理解Golang哈希表Map的元素

本文来自:简书

感谢作者:欢乐毅城

查看原文:12 - go简单实现hashmap

• 编辑
• 预览