5. Design HashMap

package hashmap

const (
    stateEmpty uint8 = iota
    stateOccupied
    stateTombstone
)

// entry представляет ячейку таблицы.
type entry struct {
    key   int
    value int
    state uint8
}

// HashMap реализует хеш-таблицу с открытой адресацией и линейным зондированием.
type HashMap struct {
    buckets    []entry
    size       int     // количество активных элементов
    capacity   int     // размер массива buckets (всегда степень 2)
    mask       int     // capacity - 1 для быстрого взятия модуля
    loadFactor float64 // порог рехаширования (обычно 0.70)
}

// NewHashMap создает новую таблицу с заданной начальной емкостью.
func NewHashMap(initialCap int, loadFactor float64) *HashMap {
    if initialCap < 8 {
        initialCap = 8
    }
    if loadFactor <= 0.1 || loadFactor >= 0.9 {
        loadFactor = 0.70
    }

    // Округляем емкость до ближайшей степени двойки
    cap := 1
    for cap < initialCap {
        cap <<= 1
    }

    return &HashMap{
        buckets:    make([]entry, cap),
        size:       0,
        capacity:   cap,
        mask:       cap - 1,
        loadFactor: loadFactor,
    }
}

// hash возвращает перемешанный 32-битный хеш целого числа (хэш Томаса Ванга).
func (m *HashMap) hash(key int) int {
    k := uint64(key)
    k = (^k) + (k << 21) // k = (k << 21) - k - 1
    k = k ^ (k >> 24)
    k = (k + (k << 3)) + (k << 8) // k * 265
    k = k ^ (k >> 14)
    k = (k + (k << 2)) + (k << 4) // k * 21
    k = k ^ (k >> 28)
    k = k + (k << 31)
    return int(k)
}

// Put вставляет или перезаписывает значение ключа.
func (m *HashMap) Put(key, val int) {
    // Проверка коэффициента заполнения перед вставкой
    if float64(m.size+1) > float64(m.capacity)*m.loadFactor {
        m.resize(m.capacity * 2)
    }

    idx := m.hash(key) & m.mask
    firstTombstone := -1

    for i := 0; i < m.capacity; i++ {
        slot := (idx + i) & m.mask
        curr := &m.buckets[slot]

        if curr.state == stateOccupied {
            if curr.key == key {
                curr.value = val // Ключ найден — обновляем значение
                return
            }
            continue
        }

        if curr.state == stateTombstone {
            if firstTombstone == -1 {
                firstTombstone = slot
            }
            continue
        }

        // Достигли пустого слота (stateEmpty)
        targetSlot := slot
        if firstTombstone != -1 {
            targetSlot = firstTombstone // Переиспользуем могильный маркер
        }

        m.buckets[targetSlot] = entry{
            key:   key,
            value: val,
            state: stateOccupied,
        }
        m.size++
        return
    }

    // Если дошли сюда — все слоты заняты tombstones
    if firstTombstone != -1 {
        m.buckets[firstTombstone] = entry{
            key:   key,
            value: val,
            state: stateOccupied,
        }
        m.size++
    }
}

// Get ищет значение по ключу, возвращая значение и флаг наличия.
func (m *HashMap) Get(key int) (int, bool) {
    idx := m.hash(key) & m.mask

    for i := 0; i < m.capacity; i++ {
        slot := (idx + i) & m.mask
        curr := &m.buckets[slot]

        if curr.state == stateEmpty {
            // Цепочка зондирования прервалась — ключ гарантированно отсутствует
            return 0, false
        }

        if curr.state == stateOccupied && curr.key == key {
            return curr.value, true
        }
        // При встрече stateTombstone продолжаем поиск дальше
    }

    return 0, false
}

// Delete помечает ячейку маркером удаления (Tombstone).
func (m *HashMap) Delete(key int) bool {
    idx := m.hash(key) & m.mask

    for i := 0; i < m.capacity; i++ {
        slot := (idx + i) & m.mask
        curr := &m.buckets[slot]

        if curr.state == stateEmpty {
            return false
        }

        if curr.state == stateOccupied && curr.key == key {
            curr.state = stateTombstone
            m.size--
            return true
        }
    }

    return false
}

// resize переаллоцирует массив и переносит только активные элементы.
func (m *HashMap) resize(newCap int) {
    oldBuckets := m.buckets

    m.buckets = make([]entry, newCap)
    m.capacity = newCap
    m.mask = newCap - 1
    m.size = 0 // Пересчитается в Put

    for _, e := range oldBuckets {
        if e.state == stateOccupied {
            m.Put(e.key, e.value)
        }
    }
}

type ShardedHashMap struct {
    shards    []*ConcurrentShard
    numShards int
    mask      int
}

type ConcurrentShard struct {
    mu sync.RWMutex
    m  *HashMap
}