Go'da map[string]int yozganingizda, kalit orqali qiymatni deyarli bir zumda topasiz — ro'yxatni boshidan oxirigacha tekshirib chiqish shart emas. Bu sehr emas: mapning ichida Hash Table (xesh jadval) degan tuzilma yotibdi, va bu darsda uni o'zingiz quramiz.

Kutubxonadagi kataloglarni tasavvur qiling: har bir kitob o'zining nomiga qarab, aniq bir tortmachaga joylashtirilgan — "A" harfidan boshlangan kitoblar bitta tortmada, "B" — boshqasida. Kitob qidirganingizda, butun kutubxonani aylanib chiqmaysiz — to'g'ridan-to'g'ri kerakli tortmaga borasiz.

Hash table ham xuddi shunday ishlaydi: hash funksiyasi har bir kalitni (masalan matnni) songa aylantiradi, va shu son "qaysi tortmaga (bucket) borish kerak"ligini ko'rsatadi.

package main

import "fmt"

type entry struct {
	key   string
	value int
}

type HashTable struct {
	buckets [][]entry
	size    int
}

func NewHashTable(size int) *HashTable {
	return &HashTable{buckets: make([][]entry, size), size: size}
}

func (h *HashTable) hash(key string) int {
	sum := 0
	for _, ch := range key {
		sum += int(ch)
	}
	return sum % h.size
}

func (h *HashTable) Set(key string, value int) {
	idx := h.hash(key)
	h.buckets[idx] = append(h.buckets[idx], entry{key, value})
}

func main() {
	ht := NewHashTable(8)
	ht.Set("age", 21)
	fmt.Println(ht.hash("age"))
}

hash funksiyasi juda sodda: matndagi har bir harfning kod raqamini (int(ch)) qo'shib, natijani "tortmalar soni"ga (h.size) bo'lib, qoldiqni oladi (%). Bu qoldiq har doim 0 va size-1 orasida bo'ladi — aynan shuning uchun uni tortma indeksi sifatida ishlatish mumkin.

Lekin bitta muammo bor: ikkita boshqa-boshqa kalit (masalan "ab" va "ba") bir xil yig'indiga, demak bir xil tortmaga tushib qolishi mumkin — bu collision (to'qnashuv) deyiladi. Shuning uchun har bir tortma bitta qiymat emas, balki qiymatlar ro'yxati ([]entry) — agar to'qnashuv bo'lsa, ikkalasi ham shu ro'yxatga qo'shiladi, va qidirishda ro'yxat ichidan aniq kalitga mos kelganini topamiz.