12 - go简单实现hashmap

欢乐毅城 · · 710 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

注意：还没有解决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)
}