Hash Tabloları

package main

import (
	"fmt"
	"hash/fnv"
)

// badHash: yalnızca uzunluğa bakar — felaket bir dağılım
func badHash(s string, buckets int) int {
	return len(s) % buckets
}

// simpleHash: her baytı katlayarak toplar (djb2 benzeri)
func simpleHash(s string, buckets int) int {
	h := 5381
	for i := range len(s) {
		h = h*33 + int(s[i])
	}
	if h < 0 {
		h = -h
	}
	return h % buckets
}

// fnvHash: standart kütüphanenin FNV-1a uygulaması
func fnvHash(s string, buckets int) int {
	h := fnv.New32a()
	h.Write([]byte(s))
	return int(h.Sum32()) % buckets
}

func distribution(name string, fn func(string, int) int, keys []string, buckets int) {
	counts := make([]int, buckets)
	for _, k := range keys {
		counts[fn(k, buckets)]++
	}
	empty, maxLoad := 0, 0
	for _, c := range counts {
		if c == 0 {
			empty++
		}
		maxLoad = max(maxLoad, c)
	}
	fmt.Printf("%-12s dağılım=%v boş kova=%d en dolu kova=%d\n", name, counts, empty, maxLoad)
}

func main() {
	keys := []string{
		"elma", "armut", "kiraz", "üzüm", "muz", "incir",
		"kavun", "karpuz", "erik", "şeftali", "ayva", "nar",
	}
	const buckets = 8

	distribution("kötü", badHash, keys, buckets)
	distribution("basit", simpleHash, keys, buckets)
	distribution("FNV-1a", fnvHash, keys, buckets)
}

package main

import (
	"fmt"
	"hash/fnv"
	"strings"
)

type chainEntry struct {
	key   string
	value int
	next  *chainEntry
}

type ChainedMap struct {
	buckets []*chainEntry
	size    int
}

func NewChainedMap(buckets int) *ChainedMap {
	return &ChainedMap{buckets: make([]*chainEntry, max(1, buckets))}
}

func (m *ChainedMap) index(key string) int {
	h := fnv.New32a()
	h.Write([]byte(key))
	return int(h.Sum32() % uint32(len(m.buckets)))
}

func (m *ChainedMap) Put(key string, value int) {
	i := m.index(key)
	for e := m.buckets[i]; e != nil; e = e.next {
		if e.key == key {
			e.value = value // var olan anahtarı güncelle
			return
		}
	}
	m.buckets[i] = &chainEntry{key: key, value: value, next: m.buckets[i]}
	m.size++
}

func (m *ChainedMap) Get(key string) (int, bool) {
	for e := m.buckets[m.index(key)]; e != nil; e = e.next {
		if e.key == key {
			return e.value, true
		}
	}
	return 0, false
}

func (m *ChainedMap) Delete(key string) bool {
	i := m.index(key)
	var prev *chainEntry
	for e := m.buckets[i]; e != nil; e = e.next {
		if e.key != key {
			prev = e
			continue
		}
		if prev == nil {
			m.buckets[i] = e.next
		} else {
			prev.next = e.next
		}
		m.size--
		return true
	}
	return false
}

// stats, zincir uzunluklarını raporlar: tablonun sağlığını gösterir
func (m *ChainedMap) stats() (longest int, empty int) {
	for _, head := range m.buckets {
		n := 0
		for e := head; e != nil; e = e.next {
			n++
		}
		if n == 0 {
			empty++
		}
		longest = max(longest, n)
	}
	return longest, empty
}

func main() {
	m := NewChainedMap(8)

	words := strings.Fields("go dilim harita ağaç graf yığın kuyruk heap trie hash")
	for i, w := range words {
		m.Put(w, i+1)
	}

	fmt.Println("eleman sayısı:", m.size)
	longest, empty := m.stats()
	fmt.Printf("en uzun zincir: %d | boş kova: %d | yük faktörü: %.2f\n",
		longest, empty, float64(m.size)/float64(len(m.buckets)))

	v, ok := m.Get("harita")
	fmt.Println("harita →", v, ok)

	m.Put("harita", 99) // güncelleme
	v, _ = m.Get("harita")
	fmt.Println("güncellendi →", v, "eleman sayısı:", m.size)

	fmt.Println("trie silindi mi:", m.Delete("trie"))
	_, ok = m.Get("trie")
	fmt.Println("trie hâlâ var mı:", ok, "| eleman sayısı:", m.size)
	fmt.Println("olmayan anahtarı silme:", m.Delete("yok"))
}

package main

import (
	"fmt"
	"hash/fnv"
)

type slotState uint8

const (
	empty slotState = iota
	occupied
	tombstone // silinmiş: arama buradan devam etmeli
)

type slot struct {
	key   string
	value int
	state slotState
}

type OpenAddressMap struct {
	slots []slot
	size  int
}

func NewOpenAddressMap(capacity int) *OpenAddressMap {
	return &OpenAddressMap{slots: make([]slot, max(2, capacity))}
}

func (m *OpenAddressMap) hash(key string) int {
	h := fnv.New32a()
	h.Write([]byte(key))
	return int(h.Sum32() % uint32(len(m.slots)))
}

// Put: doğrusal yoklama ile ilk uygun yeri bulur, yoklama sayısını döndürür
func (m *OpenAddressMap) Put(key string, value int) int {
	start := m.hash(key)
	firstTomb := -1

	for i := range len(m.slots) {
		idx := (start + i) % len(m.slots)
		switch m.slots[idx].state {
		case empty:
			if firstTomb != -1 {
				idx = firstTomb // mezar taşını yeniden kullan
			}
			m.slots[idx] = slot{key: key, value: value, state: occupied}
			m.size++
			return i + 1
		case tombstone:
			if firstTomb == -1 {
				firstTomb = idx
			}
		case occupied:
			if m.slots[idx].key == key {
				m.slots[idx].value = value
				return i + 1
			}
		}
	}
	return -1 // tablo dolu
}

func (m *OpenAddressMap) Get(key string) (int, int, bool) {
	start := m.hash(key)
	for i := range len(m.slots) {
		idx := (start + i) % len(m.slots)
		switch m.slots[idx].state {
		case empty:
			return 0, i + 1, false // boş hücre: anahtar yok
		case occupied:
			if m.slots[idx].key == key {
				return m.slots[idx].value, i + 1, true
			}
		}
		// tombstone: aramaya devam
	}
	return 0, len(m.slots), false
}

func (m *OpenAddressMap) Delete(key string) bool {
	start := m.hash(key)
	for i := range len(m.slots) {
		idx := (start + i) % len(m.slots)
		if m.slots[idx].state == empty {
			return false
		}
		if m.slots[idx].state == occupied && m.slots[idx].key == key {
			m.slots[idx] = slot{state: tombstone} // mezar taşı bırak
			m.size--
			return true
		}
	}
	return false
}

func main() {
	m := NewOpenAddressMap(8)

	for i, k := range []string{"go", "rust", "zig", "elm", "lua", "c"} {
		probes := m.Put(k, i+1)
		fmt.Printf("put %-5s yoklama=%d\n", k, probes)
	}

	fmt.Println()
	for _, k := range []string{"zig", "lua", "yok"} {
		v, probes, ok := m.Get(k)
		fmt.Printf("get %-5s → değer=%d yoklama=%d bulundu=%t\n", k, v, probes, ok)
	}

	fmt.Println()
	fmt.Println("rust silindi mi:", m.Delete("rust"))

	// Mezar taşı sayesinde diğer anahtarlar hâlâ bulunabilir
	for _, k := range []string{"zig", "lua", "c"} {
		_, _, ok := m.Get(k)
		fmt.Printf("silme sonrası %-4s bulunuyor mu: %t\n", k, ok)
	}
	fmt.Println("eleman sayısı:", m.size)
}

package main

import (
	"fmt"
	"hash/fnv"
)

type entry[V any] struct {
	key   string
	value V
	next  *entry[V]
}

type HashMap[V any] struct {
	buckets   []*entry[V]
	size      int
	maxLoad   float64
	rehashes  int
	totalMove int
}

func NewHashMap[V any]() *HashMap[V] {
	return &HashMap[V]{buckets: make([]*entry[V], 8), maxLoad: 0.75}
}

func (m *HashMap[V]) index(key string, n int) int {
	h := fnv.New32a()
	h.Write([]byte(key))
	return int(h.Sum32() % uint32(n))
}

func (m *HashMap[V]) Load() float64 {
	return float64(m.size) / float64(len(m.buckets))
}

// grow: kova sayısını ikiye katlar ve tüm elemanları yeniden yerleştirir
func (m *HashMap[V]) grow() {
	newBuckets := make([]*entry[V], len(m.buckets)*2)
	for _, head := range m.buckets {
		for e := head; e != nil; {
			next := e.next
			i := m.index(e.key, len(newBuckets))
			e.next = newBuckets[i]
			newBuckets[i] = e
			m.totalMove++
			e = next
		}
	}
	m.buckets = newBuckets
	m.rehashes++
}

func (m *HashMap[V]) Put(key string, value V) {
	i := m.index(key, len(m.buckets))
	for e := m.buckets[i]; e != nil; e = e.next {
		if e.key == key {
			e.value = value
			return
		}
	}
	m.buckets[i] = &entry[V]{key: key, value: value, next: m.buckets[i]}
	m.size++

	if m.Load() > m.maxLoad {
		m.grow()
	}
}

func (m *HashMap[V]) Get(key string) (V, bool) {
	var zero V
	for e := m.buckets[m.index(key, len(m.buckets))]; e != nil; e = e.next {
		if e.key == key {
			return e.value, true
		}
	}
	return zero, false
}

func (m *HashMap[V]) Len() int { return m.size }

func main() {
	m := NewHashMap[int]()

	fmt.Printf("%6s %6s %6s %6s\n", "eleman", "kova", "yük", "rehash")
	for i := 1; i <= 200; i++ {
		m.Put(fmt.Sprintf("anahtar-%d", i), i)
		if i == 1 || i%50 == 0 {
			fmt.Printf("%6d %6d %6.2f %6d\n", m.Len(), len(m.buckets), m.Load(), m.rehashes)
		}
	}

	fmt.Println()
	fmt.Println("toplam taşınan eleman:", m.totalMove)
	fmt.Println("eleman başına ortalama taşıma:", float64(m.totalMove)/float64(m.Len()))

	v, ok := m.Get("anahtar-137")
	fmt.Println("anahtar-137 →", v, ok)
	_, ok = m.Get("anahtar-999")
	fmt.Println("anahtar-999 bulundu mu:", ok)
}

package main

import (
	"fmt"
	"maps"
	"slices"
)

type Point struct{ X, Y int }

func main() {
	// Karşılaştırılabilir her tip anahtar olabilir
	grid := map[Point]string{
		{0, 0}: "başlangıç",
		{2, 3}: "hedef",
	}
	fmt.Println("struct anahtar:", grid[Point{2, 3}])

	// Virgül-ok deyimi: yok mu, yoksa sıfır değer mi?
	scores := map[string]int{"ali": 0}
	v, ok := scores["ali"]
	_, missing := scores["veli"]
	fmt.Printf("ali=%d var=%t | veli var=%t\n", v, ok, missing)

	// nil map: okuma güvenli, yazma panik
	var nilMap map[string]int
	fmt.Println("nil map'ten okuma:", nilMap["herhangi"], "uzunluk:", len(nilMap))

	// Kapasite ipucu vermek rehash sayısını azaltır
	sized := make(map[int]int, 1000)
	for i := range 1000 {
		sized[i] = i * i
	}
	fmt.Println("önceden boyutlandırılmış map:", len(sized), "| 999²:", sized[999])

	// Deterministik gezinme
	stock := map[string]int{"kiraz": 30, "elma": 12, "armut": 7}
	for _, k := range slices.Sorted(maps.Keys(stock)) {
		fmt.Printf("%s=%d ", k, stock[k])
	}
	fmt.Println()

	// clear ve maps.Clone
	clone := maps.Clone(stock)
	clear(stock)
	fmt.Println("temizlenen:", len(stock), "| klon:", len(clone))
}

package main

import (
	"fmt"
	"maps"
	"slices"
	"strings"
)

// wordFrequency: O(n) — her kelime bir kez işlenir
func wordFrequency(text string) map[string]int {
	counts := make(map[string]int)
	for word := range strings.FieldsSeq(strings.ToLower(text)) {
		word = strings.Trim(word, ".,!?;:")
		if word != "" {
			counts[word]++
		}
	}
	return counts
}

// twoSum: hedef toplamı veren iki indeksi O(n) sürede bulur.
// Kaba kuvvet çözümü O(n²) olurdu.
func twoSum(nums []int, target int) (int, int, bool) {
	seen := make(map[int]int, len(nums)) // değer → indeks
	for i, v := range nums {
		if j, ok := seen[target-v]; ok {
			return j, i, true
		}
		seen[v] = i
	}
	return 0, 0, false
}

// groupAnagrams: harfleri sıralanmış hâli anahtar olarak kullanır
func groupAnagrams(words []string) map[string][]string {
	groups := make(map[string][]string)
	for _, w := range words {
		letters := []rune(strings.ToLower(w))
		slices.Sort(letters)
		key := string(letters)
		groups[key] = append(groups[key], w)
	}
	return groups
}

// firstUnique: ilk tekrar etmeyen karakteri bulur
func firstUnique(s string) (rune, bool) {
	counts := make(map[rune]int)
	for _, r := range s {
		counts[r]++
	}
	for _, r := range s {
		if counts[r] == 1 {
			return r, true
		}
	}
	return 0, false
}

func main() {
	text := "Go basit bir dildir. Go hızlıdır, Go güçlüdür!"
	freq := wordFrequency(text)
	for _, w := range slices.Sorted(maps.Keys(freq)) {
		fmt.Printf("%s=%d ", w, freq[w])
	}
	fmt.Println()

	nums := []int{2, 7, 11, 15, 3}
	i, j, ok := twoSum(nums, 18)
	fmt.Printf("twoSum(18) → indeks %d ve %d (%d+%d) bulundu=%t\n", i, j, nums[i], nums[j], ok)
	_, _, ok = twoSum(nums, 100)
	fmt.Println("twoSum(100) bulundu mu:", ok)

	groups := groupAnagrams([]string{"kale", "kela", "elak", "masa", "sama", "kitap"})
	for _, k := range slices.Sorted(maps.Keys(groups)) {
		fmt.Printf("%s → %v\n", k, groups[k])
	}

	r, found := firstUnique("aabbcdeedc f")
	fmt.Printf("ilk tekrarsız karakter: %q (bulundu=%t)\n", r, found)
}