package main
import "fmt"
// Entry 鍵值對鏈表節(jié)點
type Entry struct {
    Key   string
    Value interface{}
    Next  *Entry
}
// HashMap 哈希表結構
type HashMap struct {
    buckets    []*Entry // 桶數(shù)組
    capacity   int      // 初始容量
    size       int      // 元素數(shù)量
    loadFactor float64  // 負載因子
}
// NewHashMap 初始化哈希表
func NewHashMap(capacity int) *HashMap {
    return &HashMap{
        buckets:    make([]*Entry, capacity),
        capacity:   capacity,
        loadFactor: 0.75,
    }
}
// hash 哈希函數(shù)（FNV-1a算法）
func (h *HashMap) hash(key string) int {
    const (
        offset = 2166136261
        prime  = 16777619
    )
    hash := offset
    for _, c := range key {
        hash ^= int(c)
        hash *= prime
    }
    return hash
}
// getIndex 計算鍵對應的桶索引
func (h *HashMap) getIndex(key string) int {
    return h.hash(key) % h.capacity
}
// Put 插入鍵值對
func (h *HashMap) Put(key string, value interface{}) {
    if float64(h.size)/float64(h.capacity) >= h.loadFactor {
        h.resize()
    }
    index := h.getIndex(key)
    entry := h.buckets[index]
    // 遍歷鏈表查找鍵是否存在
    for entry != nil {
        if entry.Key == key {
            entry.Value = value // 存在則更新
            return
        }
        entry = entry.Next
    }
    // 不存在則插入鏈表頭部
    h.buckets[index] = &Entry{
        Key:   key,
        Value: value,
        Next:  h.buckets[index],
    }
    h.size++
}
// Get 獲取值
func (h *HashMap) Get(key string) (interface{}, bool) {
    index := h.getIndex(key)
    entry := h.buckets[index]
    for entry != nil {
        if entry.Key == key {
            return entry.Value, true
        }
        entry = entry.Next
    }
    return nil, false
}
// Delete 刪除鍵
func (h *HashMap) Delete(key string) bool {
    index := h.getIndex(key)
    entry := h.buckets[index]
    var prev *Entry
    for entry != nil {
        if entry.Key == key {
            if prev == nil {
                h.buckets[index] = entry.Next // 刪除頭節(jié)點
            } else {
                prev.Next = entry.Next // 中間或尾部節(jié)點
            }
            h.size--
            return true
        }
        prev = entry
        entry = entry.Next
    }
    return false
}
// resize 擴容哈希表
func (h *HashMap) resize() {
    newCapacity := h.capacity * 2
    newBuckets := make([]*Entry, newCapacity)
    for i := 0; i < h.capacity; i++ {
        entry := h.buckets[i]
        for entry != nil {
            next := entry.Next
            newIndex := h.hash(entry.Key) % newCapacity // 重新計算索引
            entry.Next = newBuckets[newIndex]          // 插入新桶頭部
            newBuckets[newIndex] = entry
            entry = next
        }
    }
    h.buckets = newBuckets
    h.capacity = newCapacity
}
func main() {
    hm := NewHashMap(2) // 初始容量設為2便于觸發(fā)擴容
    hm.Put("name", "Alice")
    hm.Put("age", 30)
    hm.Put("lang", "Go") // 觸發(fā)擴容
    if val, ok := hm.Get("name"); ok {
        fmt.Println("name:", val) // 輸出 Alice
    }
    hm.Delete("age")
    if _, ok := hm.Get("age"); !ok {
        fmt.Println("age deleted") // 輸出此句
    }
}