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

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方法中，我们遍历链表以查找具有给定键的条目。