温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

深入理解Go HashMap缓存的哈希函数

发布时间:2024-11-08 19:41:33 来源:亿速云 阅读:78 作者:小樊 栏目:编程语言

Go中的HashMap是一种基于哈希表实现的键值对存储结构。它允许我们通过键来快速查找对应的值。为了实现高效的查找,HashMap需要一个哈希函数,将键转换为数组索引。Go的hash/fnv包提供了一个名为New32a的哈希函数,它是一个快速且可靠的哈希函数,适用于大多数场景。

以下是Go HashMap缓存中哈希函数的实现:

package main

import (
	"fmt"
	"hash/fnv"
)

type Cache struct {
	capacity int
	size     int
	buckets  []*entry
}

type entry struct {
	key   string
	value interface{}
}

func NewCache(capacity int) *Cache {
	return &Cache{
		capacity: capacity,
		buckets:  make([]*entry, capacity),
	}
}

func (c *Cache) hash(key string) int {
	h := fnv.New32a()
	h.Write([]byte(key))
	return int(h.Sum32()) % c.capacity
}

func (c *Cache) Put(key string, value interface{}) {
	index := c.hash(key)
	if c.buckets[index] == nil {
		c.buckets[index] = &entry{key: key, value: value}
		c.size++
		if float64(c.size) > float64(c.capacity) {
			c.resize()
		}
	} else {
		for c.buckets[index] != nil {
			if c.buckets[index].key == key {
				c.buckets[index].value = value
				return
			}
			if c.buckets[index].next == nil {
				break
			}
			index = c.hash(c.buckets[index].next.key)
		}
		c.buckets[index] = &entry{key: key, value: value}
		c.size++
		if float64(c.size) > float64(c.capacity) {
			c.resize()
		}
	}
}

func (c *Cache) Get(key string) interface{} {
	index := c.hash(key)
	for c.buckets[index] != nil {
		if c.buckets[index].key == key {
			return c.buckets[index].value
		}
		if c.buckets[index].next == nil {
			break
		}
		index = c.hash(c.buckets[index].next.key)
	}
	return nil
}

func (c *Cache) resize() {
	oldBuckets := c.buckets
	c.capacity *= 2
	c.buckets = make([]*entry, c.capacity)
	c.size = 0
	for _, e := range oldBuckets {
		if e != nil {
			c.Put(e.key, e.value)
		}
	}
}

func main() {
	cache := NewCache(2)
	cache.Put("key1", "value1")
	cache.Put("key2", "value2")
	fmt.Println(cache.Get("key1")) // 输出:value1
	cache.Put("key3", "value3")
	fmt.Println(cache.Get("key2")) // 输出:nil
	fmt.Println(cache.Get("key3")) // 输出:value3
}

在这个实现中,我们首先使用hash/fnv包中的New32a函数创建一个哈希函数。然后,在Put方法中,我们使用这个哈希函数将键转换为数组索引。接下来,我们在相应的位置插入或更新键值对。如果缓存已满,我们会调用resize方法来扩大缓存的容量。

这个实现使用了链地址法来解决哈希冲突。当两个不同的键具有相同的哈希值时,它们会被存储在同一个索引位置的链表中。在Get方法中,我们遍历链表以查找具有给定键的条目。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

go
AI