深入理解Go HashMap緩存的哈希函數(shù)

Go中的HashMap是一種基于哈希表實現(xiàn)的鍵值對存儲結(jié)構(gòu)。它允許我們通過鍵來快速查找對應(yīng)的值。為了實現(xiàn)高效的查找，HashMap需要一個哈希函數(shù)，將鍵轉(zhuǎn)換為數(shù)組索引。Go的hash/fnv包提供了一個名為New32a的哈希函數(shù)，它是一個快速且可靠的哈希函數(shù)，適用于大多數(shù)場景。

以下是Go HashMap緩存中哈希函數(shù)的實現(xiàn)：

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
}

在這個實現(xiàn)中，我們首先使用hash/fnv包中的New32a函數(shù)創(chuàng)建一個哈希函數(shù)。然后，在Put方法中，我們使用這個哈希函數(shù)將鍵轉(zhuǎn)換為數(shù)組索引。接下來，我們在相應(yīng)的位置插入或更新鍵值對。如果緩存已滿，我們會調(diào)用resize方法來擴大緩存的容量。

這個實現(xiàn)使用了鏈地址法來解決哈希沖突。當(dāng)兩個不同的鍵具有相同的哈希值時，它們會被存儲在同一個索引位置的鏈表中。在Get方法中，我們遍歷鏈表以查找具有給定鍵的條目。