Bilgisayarda "Karma Tabloları" (Hash Tables) Nasıl Çalışır?

Karma tabloları (hash tables), bir anahtar-değer (key-value) çiftini verimli bir şekilde depolamak ve bu değere anahtarını kullanarak çok hızlı bir şekilde erişmek için kullanılan bir veri yapısıdır. Ortalama olarak, ekleme, silme ve arama işlemlerini sabit zamanda (O(1)) gerçekleştirebilmesiyle ünlüdür.

Çalışma prensibi, bir "karma fonksiyonu"na (hash function) dayanır. Bir anahtar-değer çifti eklemek istediğinizde, karma fonksiyonu, anahtarı (örneğin bir kullanıcı adı) alır ve onu, bir dizinin (array) indeksi olarak kullanılabilecek bir sayıya dönüştürür. Değer (örneğin kullanıcı bilgileri), bu hesaplanan indeksteki konuma yerleştirilir. Daha sonra, aynı anahtara sahip değeri aradığınızda, karma fonksiyonu anahtarı tekrar aynı indekse dönüştürür ve doğrudan o konuma bakarak değeri anında bulur. Bu, tüm listeyi baştan sona aramak yerine, doğrudan doğru "çekmeceye" bakmak gibidir. Bazen farklı anahtarlar aynı indeksi üretebilir; bu duruma "çakışma" (collision) denir. Çakışmaları çözmek için "zincirleme" (her indekste bir bağlı liste tutma) gibi çeşitli teknikler kullanılır.

Kelimeler: karma tablosu, hash table, karma fonksiyonu, hash function, veri yapıları, bilgisayar bilimi, algoritma