Hash Tabloları

OYUNLARDA YAPAY ZEKÂ · SEMBOL TABLOLARI

Hash Tabloları

Anahtarı doğrudan dizi indeksine çevir — ortalamada sabit zamanda arama

PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

Hash fonksiyonları — anahtardan sayıya hash function
Ayrı zincirleme — çakışanlar aynı kovada bir listede separate chaining
Doğrusal yoklama — çakışırsan yandaki boş yere linear probing
Gerçek dünyada — Python dict, C# Dictionary, hash saldırıları
Oyunda — uzaysal hash, Zobrist hash, Animator.StringToHash

🎮 Bu dersin sonunda…

…Python’daki dict’in, C#’taki Dictionary’nin içini bilecek; 10.000 parçacığın çarpışmasını “ızgara hash’i” ile nasıl hızlandıracağınızı ve satranç motorlarının aynı pozisyonu nasıl tanıdığını anlayacaksınız.

🤔 ISINMA: EŞYA VERİTABANI

Oyununuzda 100.000 eşya var. Oyuncu “Ejder Kılıcı”nı alınca eşyanın verisini bulmanız lazım.

Sıralı dizi + ikili arama / dengeli BST: ~lg 100.000 ≈ 17 karşılaştırma. Fena değil.
Eşyaların ID’si 0…99.999 ise: items[id] → 1 adım! Dizi indeksi en hızlı arama.
Ama anahtar bir isim (string), bir koordinat, bir oyun durumu olursa?

Fikir: her anahtarı bir dizi indeksine çeviren bir fonksiyon yaz → hash.

Mini sözlük

hash function	hash (özet) fonksiyonu	Anahtarı 0…M−1 arası bir tam sayıya çevirir
hash table	hash tablosu	Anahtarları hash değerine göre dizide tutan sembol tablosu
collision	çakışma	İki farklı anahtarın aynı indekse düşmesi
bucket	kova	Dizinin bir hücresi
separate chaining	ayrı zincirleme	Her kovada bir bağlı liste
open addressing · linear probing	açık adresleme · doğrusal yoklama	Çakışınca dizide bir sonraki boş yere bak
load factor α	doluluk oranı	N / M: tablo ne kadar dolu?
resize / rehash	büyütme / yeniden hash’leme	Tabloyu büyütüp herkesi yeni yerine taşımak

LEVEL 0

Hash fonksiyonları

anahtar → tam sayı → dizi indeksi

hash fonksiyonları
ayrı zincirleme
doğrusal yoklama
gerçek dünyada hash
oyunda hash

İyi bir hash fonksiyonu

Tutarlı deterministic: aynı anahtar → hep aynı sayı
Hızlı: aramanın kendisinden pahalı olmamalı
Düzgün dağıtır uniform: anahtarları kovalara eşit yayar

⚠️ Kötü örnekler

Telefon numarasının ilk 3 hanesi → herkes 0532’de 😅 (son 3 hane çok daha iyi)
Oyuncu adının ilk harfi → “A” ve “M” kovaları tıklım tıklım, “Ğ” boş
Koordinat için x + y → (1, 2) ve (2, 1) hep çakışır

Varsayım uniform hashing assumptionAnalizlerde, her anahtarın M kovadan birine eşit olasılıkla ve bağımsız düştüğünü varsayacağız. Gerçek fonksiyonlar buna “yeterince” yaklaşır.

🎒 Ön bilgi: mod alma `%` ve negatif sayılar

a % M = a’nın M’ye bölümünden kalan → her zaman 0…M−1 arası… mı?
⚠️ C#, Java, JavaScript: -7 % 3 == -1 → negatif indeks → dizi dışı hatası!
Python: -7 % 3 == 2 → hep pozitif ✔
Çözüm: işaret bitini sil: (h & 0x7fffffff) % M
& = bit düzeyinde VE; 0x7fffffff = en soldaki (işaret) biti 0, diğerleri 1 olan sayı

⚙️ Neden M asal sayı?M = 100 seçerseniz h % 100 sadece son 2 basamağa bakar; anahtarlarda bir düzen varsa (hep 0 ile biten skorlar!) kovalar dengesiz dolar. Asal M, h’nin tüm bitlerini işe katar.

Hızlı tablolar ise M’yi 2’nin kuvveti seçip h & (M − 1) yapar (bölmeden çok daha hızlı) ama o zaman hash fonksiyonunun iyi karıştırması şarttır.

String hash: her karakter işe karışsın

Horner yöntemi: stringi 31 tabanında bir “sayı” gibi oku:

$ h = s_0 \cdot 31^{L-1} + s_1 \cdot 31^{L-2} + \dots + s_{L-1} $

Her adımda: h = 31 · h + karakter_kodu. Java’nın String.hashCode()’u tam olarak budur.

📜 Java 1.1’in hatasıHız için uzun stringlerde sadece her 8. karakteri kullandılar. Web adresleri (hep “http://www…” ile başlar) korkunç çakıştı. Java 1.2’de düzeltildi: bütün karakterler.

String hash — kendiniz deneyin

Tek harf değiştirin (“iksir” → “iksır”): indeks tamamen değişir. İyi bir hash fonksiyonu benzer anahtarları dağıtır.

🎒 Ön bilgi: kendi sınıfınızı anahtar yapmak

Hash tablosu iki şey sorar: “hash’in ne?” ve “bu ikisi eşit mi?”

C#: GetHashCode() + Equals()
Python: __hash__ + __eq__
Kural: eşit iki nesnenin hash’i aynı olmalı. (Tersi gerekmez: farklı nesneler çakışabilir.)

⚠️ JavaScript tuzağıMap nesneleri kimliğe göre karşılaştırır: map.set([3,4], "ork") sonra map.get([3,4]) → undefined! (İki ayrı dizi.) Izgara koordinatları için anahtarı string yapın: `${x},${y}` ya da tek sayı: x * 100003 + y.

🔗 Başka gözle: etkileşimli anlatımlar ve yazılar

Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.

📊 Hash tabloları

VisuAlgo (NUS)

Doğrusal yoklama, ikinci derece yoklama ve zincirleme; çakışmaların nasıl çözüldüğünü hücre hücre gösterir.

📘 Spatial Partition

Game Programming Patterns (Robert Nystrom)

Izgara, quadtree ve BSP ile “yakınımdaki nesneler” sorusunu hızlandırmak.

🔗 Data Structure Visualizations

David Galles (USF)

Neredeyse her veri yapısı için bir oyun alanı: ekle, sil, ara düğmeleriyle yapının nasıl değiştiğini izleyin.

Çakışmalar kaçınılmaz: doğum günü problemi 🎂

23 kişilik bir sınıfta iki kişinin aynı gün doğmuş olma ihtimali %50’den fazla! M = 365 kovaya ~24 anahtar atınca ilk çakışma gelir. Sonuç: çakışmaları önlemeye çalışmak boşuna — onları idare etmeliyiz.

Quiz 1 · hash fonksiyonları

C#’ta int i = key.GetHashCode() % M; satırının gizli tehlikesi ne?

C# (ve Java, JS) negatif sayının modunu negatif verir. Çözüm: (key.GetHashCode() & 0x7fffffff) % M. (Python’da % hep pozitif döner.) Not: Math.Abs(h) % M da neredeyse çalışır ama int.MinValue için patlar!

LEVEL 1

Ayrı zincirleme

separate chaining — her kovada bir bağlı liste

hash fonksiyonları
ayrı zincirleme
doğrusal yoklama
gerçek dünyada hash
oyunda hash

Fikir: M tane bağlı liste

M kovalı bir dizi; her kova bir bağlı liste (Bağlı Listeler sunumu!)
put: i = hash(key) % M; i. listede ara; yoksa başına ekle
get: sadece i. listede ara
Çakışan anahtarlar aynı listede sorunsuz yaşar

🎮 Benzetme: posta kutularıApartmanda 7 posta kutusu var, 40 daire. Her mektup daire numarası % 7 kutusuna atılır. Mektubunu arayan sadece kendi kutusunu karıştırır: ortalama 40/7 ≈ 6 mektup.

Ayrı zincirleme — kendiniz deneyin

Bir eşya adı yazıp put / get deneyin. “40 eşya” ile zincir uzunluklarına bakın: hepsi N/M civarında mı? M’yi değiştirin.

Ayrı zincirleme — kod

🎒 [None] * M: M tane None’dan oluşan liste · int? (C#): “int ya da null” · for (x = baş; x != null; x = x.next): bağlı listede gezinmenin kısa yazımı.

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`hashStr(key, M)`	anahtar → kova numarası (0 … M − 1)	aynı anahtar hep aynı kovaya düşer
`for (x = table[i]; …)`	kovadaki zinciri baştan sona gez	zincir ortalama N / M uzunlukta
`x.val = val; return`	anahtar varsa değeri güncelle	aynı anahtar iki kez eklenmez
`new Node(key, val, table[i])`	zincirin başına ekle	başa eklemek sabit iş; sona gitmeye gerek yok
`M = 97`	asal sayı	hash’in yüksek bitleri kalana da yansır; çakışmalar daha düzgün dağılır

Analiz: zincirler ne kadar uzun?

ÖnermeDüzgün hash varsayımıyla, N anahtar ve M kovalı bir tabloda bir zincirdeki anahtar sayısı N/M’ye çok yakın olur (çok yüksek olasılıkla).

Arama maliyeti ≈ 1 + N/M. M ≈ N/4 seçersek → zincirler ~4 uzunlukta → sabit zaman!

M nasıl seçilir?

M çok büyük → boş kovalar, bellek israfı
M çok küçük → uzun zincirler, yavaş arama
Bilmiyorsak: büyüt! N/M belli bir sınırı aşınca M’yi 2 katına çıkar, herkesi yeniden hash’le (Yığınlar sunumundaki dinamik dizi gibi: ortalamada eleman başına sabit iş)

⚙️ Java’nın sigortasıJava’nın HashMap’i bir zincir 8’i geçerse o zinciri bir kırmızı-siyah ağaca çevirir (Dengeli Ağaçlar sunumu!) → en kötü durumda bile lg N.

Quiz 2 · ayrı zincirleme

10.000 eşya, M = 2.500 kovalı ayrı zincirlemeli bir tabloda. Bir get ortalama yaklaşık kaç anahtarla karşılaştırma yapar?

Ortalama zincir uzunluğu N/M = 10.000 / 2.500 = 4. Bulma: zincirin ortasına kadar (~2), bulamama: zincirin tamamı (~4). Dengeli BST’nin ~14’ünden iyi — ve N büyüdükçe M’yi de büyütürsek sabit kalır.

LEVEL 2

Doğrusal yoklama

linear probing — dolu mu? bir sağa bak

hash fonksiyonları
ayrı zincirleme
doğrusal yoklama
gerçek dünyada hash
oyunda hash

Açık adresleme: listeler olmadan

Tek bir dizi (M > N). Her hücrede en fazla bir anahtar.
put: i = hash % M. Dolu mu? → i + 1, i + 2… ilk boş hücreye koy (sona gelince başa sar)
get: aynı yoldan yürü. Anahtarı bulursan ✔; boş hücreye gelirsen → yok
Tablo asla dolmamalı (sonsuz döngü!) → doluluk ½’yi geçince büyüt

🎮 Benzetme: otoparkBilet numaranız hangi yeri gösteriyorsa oraya park edin; doluysa bir sonrakine… Arabanızı ararken de aynı yerden başlayıp boş yere gelene kadar yürürsünüz. (Knuth bunu gerçekten “park etme problemi” diye inceledi!)

Doğrusal yoklama — kendiniz deneyin

Aynı renkli bitişik bloklar = küme cluster. “⅞ dolu” ile tabloda olmayan bir anahtarı (ör. “pizza”) arayın: kaç yoklama? Sonra “α > ½ olunca büyüt”ü açıp put yapın.

Doğrusal yoklama — kod

İki paralel dizi: keys[] ve vals[]. Bağlantı yok, düğüm nesnesi yok.

⚙️ Önbellek kazancıYoklama yan yana hücrelere bakar → hepsi aynı önbellek satırında. Zincirleme ise her adımda bellekte başka yere atlar. Bu yüzden modern hızlı tablolar (Python dict, Google’ın “Swiss table”ı, Rust HashMap) açık adresleme kullanır.

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`keys` ve `vals`	iki paralel dizi, zincir yok	hepsi tek dizide: önbellek dostu
`while (keys[i] !== null)`	boş hücre bulana kadar ilerle	yol üstünde anahtar bulunursa güncelle
`i = (i + 1) % M`	bir sağa, sonda başa sar	dairesel tampondaki fikrin aynısı
`get`’te boş hücre	“yok” demek	anahtar olsaydı bu boşluktan önce dururdu
dikkat	doluluk ½’yi geçmemeli	kümeler uzar; tablo büyütülüp yeniden hash’lenir. Silme de özen ister (boşluk aramayı yarıda keser)

Kümelenme: zenginler daha da zenginleşir

Büyük bir kümeye düşen yeni anahtar kümenin sonuna kadar yürür ve kümeyi bir büyütür
Büyük küme → daha çok anahtar ona düşer → daha da büyür
İki küme arasındaki tek boş hücre dolunca iki küme birleşir

📜 1963 · Donald KnuthGenç Knuth doğrusal yoklamanın ortalama maliyetini hesapladı. Kendi anlattığına göre bu, onun “algoritma analizi” alanına girişiydi — ve bu alanın doğuşlarından biri.

Önerme (Knuth)Doluluk α = N/M iken ortalama yoklama sayısı:

bulma: $ \tfrac12\left(1 + \tfrac{1}{1-\alpha}\right) $ bulamama: $ \tfrac12\left(1 + \tfrac{1}{(1-\alpha)^2}\right) $

α = ½ → bulma ~1,5, bulamama ~2,5. α → 1 olunca patlar: α = 0,95’te bulamama ~200!

Deney: Knuth haklı mı?

Kural: doğrusal yoklamalı tabloyu en fazla yarı dolu tutun. Büyütme (resize) bunu otomatik sağlar.

⚠️ SİLME TUZAĞI

Doğrusal yoklamada bir anahtarı sadece keys[i] = None yaparak silemezsiniz!

Neden? Arama “boş hücreye gelince dur” diyor. Ortaya açılan delik, kümenin sağındaki anahtarları kayıp gösterir.

Çözümler: (1) Silinen hücreden sonra kümenin geri kalanını yeniden ekle. (2) Hücreye “mezar taşı” tombstone koy: “burada biri vardı, aramaya devam et”.

Quiz 3 · doğrusal yoklama

Doğrusal yoklamalı bir tabloda arama, aranan anahtarı bulamadan boş bir hücreye geldi. Bu ne demek?

put da aynı yoldan yürür ve ilk boş hücreye yerleştirir. Anahtar eklenmiş olsaydı, en geç bu boş hücreye konmuş olurdu. Bu yüzden boş hücre = “yok”. (Silmenin neden dikkat istediğinin sebebi de bu.)

LEVEL 3

Gerçek dünyada hash

diller ne kullanıyor, saldırılar, hash mi BST mi?

hash fonksiyonları
ayrı zincirleme
doğrusal yoklama
gerçek dünyada hash
oyunda hash

Dillerin hazır hash tabloları

dil	yapı	içeride
Python	`dict`, `set`	açık adresleme (karışık yoklama dizisiyle); 3.7’den beri ekleme sırasını korur
C#	`Dictionary<K,V>`, `HashSet<T>`	ayrı zincirleme — ama düğümler değil diziler içinde (kova dizisi + kayıt dizisi); M asal
Java	`HashMap`	ayrı zincirleme; uzun zincir → kırmızı-siyah ağaç
C++	`std::unordered_map`	ayrı zincirleme (standart bunu dolaylı olarak gerektirir)
JavaScript	`Map`, `Set`, nesneler	motorun işi (V8: ekleme sırasını koruyan hash tablosu)
Rust / Abseil	`HashMap` / Swiss table	açık adresleme + SIMD ile 16 hücreye birden bakma

Hepsi büyütmeyi otomatik yapar. Siz sadece map[key] = value yazarsınız — ama içeride bu derste gördüğünüz fikirler çalışır.

Hash taşkını saldırısı hash flooding 💣

Düzgün hash varsayımı = “anahtarlar rastgele gibi davranır”.
Peki saldırgan, hepsi aynı kovaya düşen binlerce anahtar gönderirse? → tek bir dev zincir → her işlem N → sunucu kilitlenir.
Java’nın string hash’i bilindiği için bu anahtarları üretmek kolay (ör. “Aa” ve “BB” aynı hash’e sahip!)

📜 2011 · 28C3Klink ve Wälde, PHP, Java, Python, Ruby… web sunucularını tek bir POST isteğiyle dakikalarca meşgul ettiler. Sonuç: diller hash fonksiyonuna rastgele bir tohum eklendi. Python 3.3’ten beri her çalıştırmada hash("iksir") farklı çıkar!

🎮 OyundaÇok oyunculu oyun sunucusu, oyuncudan gelen string’leri (sohbet, isim, eşya etiketi) hash tablosuna koyuyorsa aynı saldırıya açıktır. Bir de: Python’da hash() değerini kayıt dosyasına yazmayın — bir sonraki çalıştırmada farklı olacak!

Hash tablosu mu, dengeli BST mi?

yapı	arama (en kötü)	arama (ortalama)	sıralı işlemler
kırmızı-siyah BST	2 lg N	~lg N	✔ min, floor, rank, aralık
ayrı zincirleme	N *	~3–5	✘
doğrusal yoklama	N *	~3–5	✘

Hash tablosu seç……sadece “var mı / değeri ne?” soruyorsan: envanter, eşya veritabanı, oyuncu ID → oyuncu, önbellek.

Dengeli BST seç……sıra lazımsa (“en yüksek skor”, “şu andan sonraki ilk olay”, “1500–1600 MMR arası”) ya da en kötü durum garantisi şartsa.

* Düzgün hash varsayımı altında olasılığı çok çok düşük. Ama saldırgan varsa (önceki slayt)…

Quiz 4 · gerçek dünya

Hangi oyun özelliği için hash tablosu yerine dengeli BST (SortedDictionary) seçmek daha mantıklıdır?

Aralık sorgusu bir sıralı işlem: hash tablosu anahtarları rastgele dağıttığı için “1500 ile 1600 arası” sorusuna ancak hepsine bakarak cevap verebilir. Diğer üçü sadece “bu anahtar var mı / değeri ne?” → hash tablosu ideal.

LEVEL 4

Oyunda hash

uzaysal hash, Zobrist hash, StringToHash

hash fonksiyonları
ayrı zincirleme
doğrusal yoklama
gerçek dünyada hash
oyunda hash

Problem: “yakınımda kim var?” ve uzaysal hash fikri

Herkesi herkesle sınamak

Çarpışma, patlama alanı, “en yakın düşman”, sürü davranışı: hepsi aynı soruyu sorar: bu nesnenin yakınında kimler var?

En basit yol her çifti sınamak: N nesne için N · (N − 1) / 2 çift. 1.000 mermi ve düşman: 499.500 test, her karede. 10.000 nesne: 50 milyon.

Oysa bir nesnenin gerçekten yakınında olanlar bir avuç.

Fikir: dünyayı eşit karelere (hücrelere) böl. Her nesneyi içinde bulunduğu hücreye yaz.
Bir nesnenin komşularını ararken yalnızca kendi hücresine ve 8 komşu hücreye bak. Uzaktaki hücrelerin içindekiler hiç sınanmaz.
Hash tablosu nerede? Hücreleri dev bir 2B dizide tutmak yerine, anahtarı hücre koordinatı olan bir hash tablosunda: yalnızca dolu hücreler yer kaplar; dünya sonsuz olabilir.

Elle hesap: hücre boyu 50 piksel

nesne	konum (x, y)	hücre = (⌊x/50⌋, ⌊y/50⌋)	anahtar
A	(130, 75)	(2, 1)	“2,1”
B	(160, 90)	(3, 1)	“3,1”
C	(140, 60)	(2, 1)	“2,1”
D	(620, 410)	(12, 8)	“12,8”

Tablo: “2,1” → [A, C] · “3,1” → [B] · “12,8” → [D]

A’nın yakınında kim var? A’nın hücresi (2, 1). Bakılacak 9 hücre: (1…3, 0…2). Bunlardan dolu olanlar “2,1” ve “3,1” → adaylar C ve B.
D hiç sınanmadı: hücresi çok uzakta.
Adaylara gerçek uzaklık testi yapılır (aday olmak, çarpışmak demek değildir).

Dört nesnede kazanç küçük: 6 çift yerine 2 test. Demodaki 400 nesnede: 79.800 çift yerine birkaç yüz test.

🧭 DEMOYU OKUMA KILAVUZU (bir sonraki slayt)

Noktalar hareket eden nesneler; ince çizgiler hücre sınırları. Her karede tablo baştan kurulur: her nesne kendi hücresinin listesine eklenir.
Fareyi bir nesnenin üstüne getirin: sarı 3 × 3 alan, o nesne için bakılan hücreler. Yalnızca o alandaki nesneler adaydır.
Alttaki sayaçlar: uzaysal hash ile yapılan test sayısı ve aynı iş için kaba kuvvetin yapacağı test sayısı.
Hücre boyutunu büyütün: her hücrede çok nesne birikir, test sayısı artar (en uçta tek hücre = kaba kuvvet). Küçültün: testler azalır ama nesne çapından küçük hücrede komşular kaçırılmaya başlar.
Kural: hücre boyu ≈ en büyük nesnenin çapı (ya da sorgu yarıçapı).

🎮 Uzaysal hash ızgarası spatial hashing

Noktalar hareket eden nesneler; ince çizgiler hücre sınırları. Her karede tablo baştan kurulur: her nesne kendi hücresinin listesine eklenir.
Fareyi bir nesnenin üstüne getirin: sarı 3 × 3 alan, o nesne için bakılan hücreler. Yalnızca o alandaki nesneler adaydır.
Alttaki sayaçlar: uzaysal hash ile yapılan test sayısı ve aynı iş için kaba kuvvetin yapacağı test sayısı.
Hücre boyutunu büyütün: her hücrede çok nesne birikir, test sayısı artar (en uçta tek hücre = kaba kuvvet). Küçültün: testler azalır ama nesne çapından küçük hücrede komşular kaçırılmaya başlar.
Kural: hücre boyu ≈ en büyük nesnenin çapı (ya da sorgu yarıçapı).

Her nesne bulunduğu hücreye (anahtar = hücre koordinatı) konur. Bir nesne sadece kendi hücresi ve 8 komşusundakilerle test edilir. Fareyi bir parçacığın üstüne getirin: sarı 3×3 alan. Hücre boyutunu değiştirip test sayısına bakın.

🔗 Ayrıntısı: G2 · Uzaysal Bölümleme (ızgara, dörtlü ağaç ve BVH karşılaştırmasıyla) sunumunda.

Uzaysal hash — neden ızgara dizisi değil de hash?

Sonsuz (ya da çok büyük) dünya: 1 milyon × 1 milyon hücrelik dizi sığmaz
Ama dolu hücre sayısı en fazla N → sadece dolu hücreleri bir hash tablosunda tut
Anahtar: (hx, hy) → tek sayı: hx * 100003 + hy ya da string "hx,hy"
Hücre boyutu ≈ nesne çapı: daha küçükse nesne birçok hücreye taşar, daha büyükse hücre başına çok nesne

🎮 Nerede?

Parçacık sistemleri, sürü (boids) simülasyonları
MMO’da “çevremdeki oyunculara mesaj gönder” (ilgi alanı yönetimi)
Matthias Müller’in “Ten Minute Physics” videosu: binlerce topun çarpışması tam bu yöntemle (bir sonraki slayt)

BST’nin Geometrik Uygulamaları sunumundaki ızgara ↔ kd-ağacı tartışmasını hatırlayın: düzgün dağılımda ızgara/hash rakipsiz; kümelenmede ağaçlar.

🎬 Ara: binlerce top, tek hash tablosu

Finding collisions among thousands of objects blazing fast
Ten Minute Physics (Matthias Müller) · 11 dk · YouTube’da aç

Az önceki fikrin aynısı, tarayıcıda çalışan kodla: hücre koordinatından hash, sayarak sıralama ile “yoğun” tablo ve binlerce topun çarpışması.

🤔 İzlerkenVideoda hücre koordinatları tek bir sayıya nasıl çevriliyor? Tablonun boyu nesne sayısına göre nasıl seçiliyor? İki farklı hücre aynı tablo gözüne düşerse (çakışma) sonuç yanlış mı olur, yoksa yalnızca yavaş mı?

Devamı: G2 · Uzaysal Bölümleme (ızgara, quadtree, BVH; elle izleme, kod ve ölçümler).

♟️ Zobrist hash: oyun YZ’sinin hafızası

Satranç motoru aynı pozisyona farklı hamle sıralarıyla defalarca ulaşır. Her seferinde yeniden düşünmek israf → pozisyonların değerini bir hash tablosunda sakla: transpozisyon tablosu.

Her (taş, kare) çifti için bir rastgele 64 bit sayı üret (bir kez)
Pozisyonun hash’i = tahtadaki taşların sayılarının XOR’u
Hamle yapınca baştan hesaplama! Sadece: h ^= Z[taş][eski] ^ Z[taş][yeni] → 2 işlem

📜 Albert Zobrist, 1970 — aslında Go programı için. Bugün Stockfish dahil bütün satranç motorlarında.

🎒 Zobrist kodundaki yeni ifadeler

a ^ b · h ^= x	XOR (özel veya)	Bitler farklıysa 1. Sihirli özelliği: `x ^ x = 0` → aynı sayıyı iki kez XOR’lamak geri alır. Bu yüzden “çıkar” ve “koy” aynı işlem!
[[… for sq in …] for p in …]	iç içe liste üreteci	12 satır × 64 sütunluk tablo. Geleneksel: iki iç içe `for` ile boş listeye `append`
random.getrandbits(64)	64 bitlik rastgele sayı	0 … 2⁶⁴−1
ulong · BigInt · 32n	64 bit işaretsiz tam sayı	C#’ta `ulong`; JS’te normal sayılar 53 bitte hassasiyet kaybeder → `BigInt` (sayının sonuna `n`)
<< 32n · \|	bit kaydırma · bit VEYA	İki 32 bitlik parçayı yan yana yapıştırıp 64 bit yapmak

🎮 Unity: string yerine hash

Animator parametreleri isimle ayarlanır: animator.SetBool("isRunning", true). Her çağrıda string’in hash’i hesaplanır!

Unity’nin önerisi: hash’i bir kez hesapla, sakla, int ile çağır. Aynı fikir: Shader.PropertyToID.

⚙️ Neden hızlı?İki int’i karşılaştırmak tek işlemci komutu; iki string’i karşılaştırmak karakter karakter döngü. Saniyede 60 kare × 500 karakter × birkaç parametre…

Quiz 5 · oyunda

Zobrist hash’te bir taş hareket ettiğinde neden bütün tahtayı yeniden taramaya gerek yok?

x ^ x = 0: aynı sayıyı iki kez XOR’lamak etkisini siler. Hash, taşların sayılarının XOR’u olduğu için bir taşı “çıkarmak” ve “koymak” birer XOR. 64 kareyi gezmek yerine 2 işlem — saniyede milyonlarca pozisyon inceleyen motorlar için hayati.

🧪 Kod laboratuvarı: doğrusal yoklamada get

Bu kod çoğu zaman çalışır ama bazı testlerde yanlış sonuç verir. Hangi durumda? (İpucu: küme dizinin sonuna taşarsa nereden devam eder?) Bonus: döngü koşulunu keys[i] !== null yapsaydık ne olurdu?

🐍 Kod laboratuvarı — string hash (Python)

Bu kod sadece karakter kodlarını topluyor: “ok” ile “ko” aynı hash’i alır! Horner formülünü uygulayın (her adımda % M alarak). Sonra print(hash_str("ok", 97), hash_str("ko", 97)) ile farkı görün.

Derin hikâye: 28C3’ten sonra: “rastgele tohumlu” hash’ler

Aralık 2011, 28C3: Alexander Klink ve Julian Wälde, PHP, Java, Python, Ruby ve ASP.NET’in kullandığı hash fonksiyonları için çakışan anahtarlar üretmenin kolay olduğunu gösterdi. Web sunucuları her POST isteğindeki parametreleri bir hash tablosuna koyduğu için tek bir istek bir işlemciyi dakikalarca meşgul edebiliyordu.
Cevaplar: Python 3.3 hash rastgeleleştirmesini varsayılan yaptı; yetersiz kalınca Python 3.4 SipHash’e geçti (PEP 456). Java 8 kalabalık kovaları ağaca çevirdi (Dengeli Ağaçlar sunumu). .NET (Core/5+) string.GetHashCode değerini her süreçte farklı tohumla hesaplar.
Sonuç: aynı metnin hash kodu, programı her çalıştırdığınızda değişebilir.

DersGetHashCode’u asla kaydetmeyin ve ağ üzerinden göndermeyin. Kayıt dosyasında, ağda ya da “tohumdan dünya üretme”de (Y15) kalıcı ve platformdan bağımsız bir değer gerekiyorsa açıkça tanımlanmış bir hash (ör. xxHash, FNV-1a) kullanın. Hash tablosu ise girdi saldırgan olabiliyorsa (çok oyunculu sunucu) rastgele tohumlu hash ister.

Kaynak: oCERT-2011-003 · PEP 456

🧰 Kütüphaneler ve araçlar

ad	platform	ne yapar / sınırları	nasıl eklenir
Dictionary · HashSet	C# / Unity	Zincirleme (kova dizisi + giriş dizisi); ortalama O(1). Anahtar türü Equals ve GetHashCode’u tutarlı uygulamalı.	yerleşik
NativeHashMap · NativeParallelHashMap	Unity (Collections)	Burst/Jobs ile uyumlu, çöp üretmeyen hash tabloları.	Package Manager: Collections
dict · set	Python	Açık adresleme; 3.7’den beri ekleme sırasını korur. Metin hash’leri süreç başına rastgele (PYTHONHASHSEED).	yerleşik
Map · Set	JavaScript	Ekleme sırasını korur; nesne anahtarları kimliğe göre karşılaştırılır (iki ayrı {x:1} farklı anahtardır).	yerleşik
xxHash	C, C#, Python, JS…	Çok hızlı, kriptografik olmayan, deterministik hash: varlık kimlikleri, içerik kontrolü.	C#: NuGet `System.IO.Hashing` (XxHash64)

🧩 Oyunlarda hash tabloları

Uzaysal hash: Dictionary<Vector2Int, List<Unit>> ile “bu hücrede kimler var?” (Y7, Y18).
Kimlikten nesneye: ağ kimliği → varlık, eşya kodu → tanım.
Ziyaret edilenler: BFS/A* kapalı kümesi (HashSet).
Önbellek: pahalı hesap sonuçlarını anahtarlayıp saklamak (memoization).

Anahtar tuzakları

Equals’ı ezip GetHashCode’u ezmemek: eşit nesneler farklı kovalara düşer.
Değişen nesneyi anahtar yapmak: konumu değişince bir daha bulunamaz.
float/Vector3 anahtar: 0,1 + 0,2 ≠ 0,3; ızgara hücresine (int) yuvarlayın.
GetHashCode’u kaydetmek (yukarıdaki hikâye).

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin

GetHashCode’u kaydetmek ya da ağdan göndermek
Equals’ı ezip GetHashCode’u ezmemek
Değişen nesneyi anahtar yapmak
float koordinatı anahtar yapmak

İyi bir istek (prompt) örneği

“Unity 6, C#. Bir uzaysal hash ızgarası yaz: SpatialHash(float cellSize), Insert(T, Vector2), Remove, Move (hücre değişirse taşı), QueryRadius(Vector2 merkez, float r, List sonuç) — sonuç listesi dışarıdan verilsin (çöp üretmesin). Anahtar Vector2Int. 10.000 nesne ile kaba kuvvet aramaya karşı doğruluk ve hız testi ekle.”

Anahtar türünün Equals/GetHashCode’unu kontrol ettirin
Kalıcı kimlik için deterministik hash isteyin
Kapasiteyi baştan ayarlamayı sorun
Unity Jobs içinde NativeHashMap gerekip gerekmediğini sorun

🚀 Proje ve araştırma önerileri

[kolay] Uzaysal hash — Boids’i (Y7) uzaysal hash ile hızlandırıp kontrol sayısını ölçün.
[orta] Kendi hash tablonuz — Açık adresleme (doğrusal yoklama) ile yazıp yük faktörünün etkisini grafiğe dökün.
[orta] Deterministik kimlikler — Varlık adlarından xxHash ile kalıcı kimlik üretin; kayıt dosyasında kullanın, çakışmaları test edin.
[araştırma] Çakışma saldırısı — Kendi zayıf hash fonksiyonunuza karşı çakışan anahtarlar üretip tablonun nasıl yavaşladığını gösterin; rastgele tohumla düzeltin.

📄 Akademik okumalar ve kaynaklar

Klink & Wälde 2011 · Efficient Denial of Service Attacks on Web Application Platforms (28C3 / oCERT-2011-003)
Hash flooding.

Aumasson & Bernstein 2012 · SipHash: a fast short-input PRF (INDOCRYPT 2012)
Rastgele tohumlu güvenli hash.

Heimes 2013 · PEP 456 – Secure and interchangeable hash algorithm (Python Enhancement Proposal)
Python’un SipHash’e geçişi.

Neler öğrendik? 🎒

Hash fonksiyonu: tutarlı, hızlı, düzgün. String için Horner (31).
C#/JS’te % negatif olabilir → & 0x7fffffff.
Ayrı zincirleme: kova = bağlı liste; maliyet ~N/M.
Doğrusal yoklama: tek dizi, önbellek dostu; α ≤ ½ tut; silme dikkat.

Çakışma kaçınılmaz (doğum günü); büyütme ile sabit ortalama.
Hash taşkını → rastgele tohumlu hash.
Sıra lazımsa BST, değilse hash.
🎮 Uzaysal hash, Zobrist, StringToHash.

Alıştırmalar 🏋️

Kâğıt-kalem: M = 5, hash(k) = k % 5. 12, 7, 22, 3, 17 anahtarlarını (a) ayrı zincirlemeyle, (b) doğrusal yoklamayla (M = 10, k % 10) ekleyin.
Java’da "Aa".hashCode() == "BB".hashCode(). Neden? Bunu kullanarak aynı hash’e sahip 4 farklı 4 harfli string üretin.
p5.js’te 3.000 parçacıklı bir sürü (boids) simülasyonunda komşu aramayı uzaysal hash ile yazın; FPS’i kaba kuvvetle karşılaştırın.
Tic-tac-toe için Zobrist hash yazın (2 taş × 9 kare) ve minimax’ta tekrar eden pozisyonları sayın.
Python’da iki ayrı çalıştırmada print(hash("iksir")) yazdırın. Aynı mı? PYTHONHASHSEED=0 ile tekrar deneyin.
🤖 Bir YZ asistanına “C#’ta Vector2Int’i Dictionary anahtarı yapınca performans” sorun. GetHashCode’un nasıl yazıldığını inceleyin.