package main

import (
    "fmt"
    "hash/fnv"
)

type HashMap struct {
    buckets [][]KeyValue
    size    int
    count   int
}

type KeyValue struct {
    key   string
    value interface{}
}

func NewHashMap(size int) *HashMap {
    return &HashMap{
        buckets: make([][]KeyValue, size),
        size:    size,
    }
}

func (h *HashMap) hashFunction(key string) int {
    hf := fnv.New32a()
    hf.Write([]byte(key))
    return int(hf.Sum32()) % h.size
}

func (h *HashMap) Insert(key string, value interface{}) {
    if float64(h.count)/float64(h.size) >= 0.75 {
        h.resize()
    }

    index := h.hashFunction(key)
    for i, kv := range h.buckets[index] {
        if kv.key == key {
            h.buckets[index][i].value = value
            return
        }
    }

    h.buckets[index] = append(h.buckets[index], KeyValue{key, value})
    h.count++
}

func (h *HashMap) Get(key string) (interface{}, bool) {
    index := h.hashFunction(key)
    for _, kv := range h.buckets[index] {
        if kv.key == key {
            return kv.value, true
        }
    }
    return nil, false
}

func (h *HashMap) resize() {
    newSize := h.size * 2
    newBuckets := make([][]KeyValue, newSize)
    oldBuckets := h.buckets
    h.buckets = newBuckets
    h.size = newSize
    h.count = 0

    for _, bucket := range oldBuckets {
        for _, kv := range bucket {
            h.Insert(kv.key, kv.value)
        }
    }
}

func main() {
    hm := NewHashMap(16)
    hm.Insert("key1", "value1")
    hm.Insert("key2", 100)
    hm.Insert("key3", true)

    if value, found := hm.Get("key2"); found {
        fmt.Printf("Found key2 with value %v\n", value)
    }
}