golang之HashMap - 知乎 - 程序猿·D·安宇雨 DeepMind

golang之HashMap - 知乎

安宇雨 - 随手采集
2022-08-23 15:30:29
随手采集
0000-未整理-等待研究

HashMap是用来存储键值对的一种数据结构，这些键值分散存放在某一个地方，也就是HashMap的主干而已。

首先定义一个链表：

package main

type nodelist struct {
    key interface{}
    value interface{}
    next *nodelist
}

给他添加一点方法：

package main 
func NewNodeList(key interface{}, value interface{}) *nodelist {
    return &nodelist{key, value, nil}
}

func (l *nodelist) Add(key interface{}, value interface{}) {
    node := nodelist{key, value, nil}
    temp := l.next
    for temp != nil {
        temp = temp.next
    }
    node.key = key
    node.value = value
    node.next = nil
    temp.next = &node
}

func (l *nodelist) Del(key interface{}) {
    temp := l.next
    for temp != nil && temp.key == key {
        temp = temp.next
    }
    temp.next = temp.next.next
}

func (l *nodelist) Find(key interface{}) interface{} {
    temp := l.next
    for temp != nil && temp.key == key {
        temp = temp.next
    }
    return temp.value
}

上面就是增删改查的方式了。

然后HashMap是以hash值存储链表的，所以先写一个HashMap的结构：

package main

type HashMap struct {
    size    int
    element []*nodelist
}

然后新建一个HashMap：

package main
func NewHashMap(size int) *HashMap {
    if size == 0 {
        size = 16
    }
    return &HashMap{size, []*nodelist{{}}}
}

其中最复杂的是，创建一个hash值，存放链表：

func (h *HashMap) generateHash(key string) int {
    keylen := len(key)
    sum := 0
    for i := 0; i < keylen; i++ {
        sum += sum + int(key[i])
    }
    return sum % h.size
}

它的作用是以key作为主键，然后生成int结构，随后用size的值取模。写法如下：

func (h *HashMap) generateHash(key string) int {
    keylen := len(key)
    sum := 0
    for i := 0; i < keylen; i++ {
        sum += sum + int(key[i])
    }
    return sum % h.size
}

接着就是一顿增删查：

package main
func (h *HashMap) Put(key string, value interface{}) {
    index := h.generateHash(key)
    h.element[index].Add(key, value)
}

func (h *HashMap) Get(key string) interface{} {
    return h.element[h.generateHash(key)].Find(key)
}

func (h *HashMap) Del(key string) {
    h.element[h.generateHash(key)].Del(key)
}

原网址: 访问
创建于: 2022-08-23 15:30:29
目录: default
标签: 无

未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到

请先后发表评论