İçeriğe geç

Hash tablosu temelleri

Ders 1 / 8 · 4 dk

Hash tablosu temelleri

Adım 1/6

Hash tablosu numaralı kutulardır. Hangi kutu olduğuna anahtarın kendisi karar verir: raf raf gezmek yok, sıralama yok.

Fikir

Hash tablosu her anahtarı, bir bucket numarası döndüren bir hash fonksiyonundan geçirir. Hem saklama hem okuma (lookup) doğrudan o bucket'a atlar; bu yüzden içeride kaç anahtar olursa olsun ortalama maliyet O(1) kalır. Bedeli şu: anahtarlar hashable olmalı ve sıra hiçbir zaman garanti edilmez.

Gerçek hayattan örnek

Bir eczane, hazır reçeteleri sipariş numarasının son iki basamağına göre numaralı kutulara koyar. Kimse rafları dolaşıp etiket okumaz — fişindeki numara zaten kutunun numarasıdır. Bekleyen iki yüz poşette de beş poşette de erişim maliyeti aynıdır.

Kod

Sıra sende

Bu kod ne yazdırır?

shelf = {"a": 1, "b": 2}
shelf["c"] = 3
shelf["a"] = 9
print(len(shelf), shelf["a"])

Mini quiz

1 / 3

Hash fonksiyonu bir anahtardan ne üretir?