Veri Yapısındaki Hash Tablosu: Python Örnek E-posta
Sarah Chen
Hashing nedir?
Karma, sabit uzunluğa sahip bir değerdir ve matematiksel bir formül kullanılarak oluşturulur. Hash değerleri, veri sıkıştırmada, kriptolojide vb. kullanılır. Veri indekslemede, hash değerleri, onları oluşturmak için kullanılan değerlerden bağımsız olarak sabit uzunluk boyutuna sahip oldukları için kullanılır. Hash değerlerinin, değişen uzunluklardaki diğer değerlerle karşılaştırıldığında minimum yer kaplamasını sağlar.
Karma işlevi, anahtarı karma haline dönüştürmek için matematiksel bir algoritma kullanır. Bir karma işlevi birden fazla anahtar için aynı karma değerini ürettiğinde çarpışma meydana gelir.
Hash Tablosu Nedir?
A KARMA TABLO bir çift anahtar ve değer kullanarak değerleri saklayan bir veri yapısıdır. Her değere, karma işlevi kullanılarak oluşturulan benzersiz bir anahtar atanır.
Anahtarın adı, ilişkili değerine erişmek için kullanılır. Bu, karma tablosundaki öğelerin sayısından bağımsız olarak karma tablosunda değerleri aramayı çok hızlı hale getirir.
Karma işlevleri
Örneğin, çalışan kayıtlarını saklamak istiyorsak ve her çalışan, bir çalışan numarası kullanılarak benzersiz bir şekilde tanımlanıyorsa.
Çalışan numarasını anahtar olarak kullanabilir ve değer olarak çalışan verilerini atayabiliriz.
Yukarıdaki yaklaşım, ekstra boş alan gerektirecektir. (m * n2) burada m değişkeni boyutudur dizin değişkeni ise çalışan numarasının hane sayısıdır. Bu yaklaşım depolama alanı problemini ortaya çıkarmaktadır.
Bir karma işlevi, çalışan numarasını alıp bunu bir karma tamsayı değeri, sabit rakamlar oluşturmak ve depolama alanını optimize etmek için kullanarak yukarıdaki sorunu çözer. Hash fonksiyonunun amacı saklamak istediğimiz değere referans vermek için kullanılacak bir anahtar oluşturmaktır. İşlev, kaydedilecek değeri kabul eder ve ardından anahtarın değerini hesaplamak için bir algoritma kullanır.
Aşağıda basit bir karma işlevine örnek verilmiştir
h(k) = k1 % m
İŞTE,
- h(k), k parametresini kabul eden karma işlevidir. k parametresi, anahtarını hesaplamak istediğimiz değerdir.
- k1 % m, karma fonksiyonumuzun algoritmasıdır; burada k1, depolamak istediğimiz değerdir ve m, listenin boyutudur. Anahtarı hesaplamak için modül operatörünü kullanırız.
Örnek E-posta
Sabit boyutu 3 olan bir listemiz olduğunu ve aşağıdaki değerlerin olduğunu varsayalım
[1,2,3]
Her bir değerin işgal etmesi gereken konumları hesaplamak için yukarıdaki formülü kullanabiliriz.
Aşağıdaki görselde hash tablomuzdaki mevcut indeksler gösterilmektedir.
) 1 Adım Bu şekilde ilk değerin kaplayacağı konumu hesaplayın
sa(1) = %1 3
= 1
Değer 1 işgal edecek üzerindeki boşluk dizin 1
) 2 Adım İkinci değerin kaplayacağı konumu hesaplayın
sa(2) = %2 3
= 2
Değer 2 işgal edecek üzerindeki boşluk dizin 2
) 3 Adım Üçüncü değerin kaplayacağı konumu hesaplayın.
sa(3) = %3 3
= 0
Değer 3 işgal edecek üzerindeki boşluk dizin 0
Nihai Sonucu
Doldurduğumuz hash tablomuz artık aşağıdaki gibi olacak.
İyi bir karma fonksiyonunun nitelikleri
İyi bir hash fonksiyonu aşağıdaki özelliklere sahip olmalıdır.
- Karma oluşturma formülü, algoritmada depolanacak veri değerini kullanmalıdır.
- Karma işlevi, aynı miktardaki giriş verileri için bile benzersiz karma değerleri üretmelidir.
- Fonksiyon çarpışma sayısını en aza indirmelidir. Birden fazla değer için aynı değer üretildiğinde çarpışma meydana gelir.
- Değerlerin tüm olası karmalara tutarlı bir şekilde dağıtılması gerekir.
Çarpışma
Algoritma birden fazla değer için aynı karma değeri ürettiğinde çarpışma meydana gelir.
Bir örneğe bakalım.
Aşağıdaki değerler listesine sahip olduğumuzu varsayalım
[3,2,9,11,7]
Hash tablosunun boyutunun 7 olduğunu varsayalım ve (k) formülünü kullanacağız.1 % m) burada m karma tablosunun boyutudur.
Aşağıdaki tabloda üretilecek hash değerleri gösterilmektedir.
| anahtar | Hash Algoritması (k1 % m) | Hash Değeri |
|---|---|---|
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Yukarıdaki sonuçlardan da görebileceğimiz gibi 2 ve 9 değerleri aynı hash değerine sahiptir ve her pozisyonda birden fazla değer saklayamayız.
Verilen problem zincirleme veya sondaj kullanılarak çözülebilir. Aşağıdaki bölümler zincirleme ve sondajı detaylı olarak ele almaktadır.
Zincirleme
Zincirleme, her biri benzersiz indekslere sahip bağlantılı listeler kullanılarak çarpışma sorununu çözmek için kullanılan bir tekniktir.
Aşağıdaki görsel, zincirlenmiş bir listenin nasıl göründüğünü göstermektedir
Hem 2 hem de 9 aynı dizini işgal eder, ancak bağlantılı listeler olarak saklanırlar. Her listenin benzersiz bir tanımlayıcısı vardır.
Zincirleme listelerin faydaları
Zincirli listelerin faydaları şunlardır:
- Ekleme sırası O(1) olduğundan zincirleme listeler veri eklerken daha iyi performansa sahiptir.
- Zincirleme liste kullanan bir karma tablosunu yeniden boyutlandırmak gerekli değildir.
- Boş alan olduğu sürece çok sayıda değeri kolaylıkla barındırabilir.
İnceleme
Çarpışmayı çözmek için kullanılan diğer teknik ise araştırmadır. Sondalama yöntemini kullanırken, bir çarpışma meydana gelirse, basitçe ilerleyebilir ve değerimizi saklayacak boş bir yuva bulabiliriz.
Aşağıdakiler sondaj yöntemleridir:
| Yöntem | Açıklama |
|---|---|
| Doğrusal problama | Adından da anlaşılacağı gibi bu yöntem, çarpışmanın meydana geldiği konumdan başlayarak ileriye doğru doğrusal olarak boş yuvaları arar. Listenin sonuna ulaşıldığında ve boş yuva bulunamazsa. İnceleme listenin başında başlar. |
| İkinci dereceden araştırma | Bu yöntem, bir sonraki kullanılabilir boş alanı bulmak için ikinci dereceden polinom ifadelerini kullanır. |
| Double Çırpı | Bu teknik, bir sonraki boş slotu bulmak için ikincil bir karma fonksiyonu algoritması kullanır. |
Yukarıdaki örneğimizi kullanırsak, problama kullanıldıktan sonraki karma tablosu aşağıdaki gibi görünecektir:
Karma tablo işlemleri
Burada OperaHash tabloları tarafından desteklenen işlemler:
- sokma - Bu Operakarma tablosuna bir öğe eklemek için kullanılır
- Arama - Bu Operaanahtarını kullanarak karma tablosundaki öğeleri aramak için kullanılır
- silme - Bu Operakarma tablosundaki öğeleri silmek için kullanılır
Veri işlemi ekleme
Ekleme işlemi, değerleri karma tablosunda saklamak için kullanılır. Hash tablosuna yeni bir değer kaydedildiğinde buna bir indeks numarası atanır. İndeks numarası hash fonksiyonu kullanılarak hesaplanır. Karma işlevi, dizin numarası hesaplanırken ortaya çıkan tüm çakışmaları çözer.
Veri işlemini arayın
Arama işlemi, indeks numarasını kullanarak karma tablosundaki değerleri aramak için kullanılır. Arama işlemi, arama indeks numarasına bağlı değeri döndürür. Örneğin 6 değerini indeks 2'de saklarsak indeks numarası 2 olan arama işlemi 6 değerini döndürecektir.
Veri işlemini silme
Silme işlemi, bir karma tablodan bir değeri kaldırmak için kullanılır. Silmek için OperaBu işlem dizin numarası kullanılarak yapılır. Bir değer silindiğinde, dizin numarası serbest bırakılır. Ekleme işlemi kullanılarak diğer değerleri depolamak için kullanılabilir.
Hash Table Uygulaması Python Örnek E-posta
Bir anahtarın hash değerini hesaplayan basit bir örneğe bakalım
def hash_key( key, m):
return key % m
m = 7
print(f'The hash value for 3 is {hash_key(3,m)}')
print(f'The hash value for 2 is {hash_key(2,m)}')
print(f'The hash value for 9 is {hash_key(9,m)}')
print(f'The hash value for 11 is {hash_key(11,m)}')
print(f'The hash value for 7 is {hash_key(7,m)}')
Hash Tablosu Kod Açıklaması
İŞTE,
- key ve m parametrelerini kabul eden hash_key işlevini tanımlar.
- Hash değerini belirlemek için basit bir modül işlemi kullanır
- 7 değerine başlatılan bir m değişkenini tanımlar. Bu, karma tablomuzun boyutudur
- 3'ün karma değerini hesaplar ve yazdırır
- 2'ün karma değerini hesaplar ve yazdırır
- 9'ün karma değerini hesaplar ve yazdırır
- 11'ün karma değerini hesaplar ve yazdırır
- 7'ün karma değerini hesaplar ve yazdırır
Yukarıdaki kodun çalıştırılması aşağıdaki sonuçları üretir.
The hash value for 3 is 3 The hash value for 2 is 2 The hash value for 9 is 2 The hash value for 11 is 4 The hash value for 7 is 0
Python Sözlük Örneği
Python Sözlük adı verilen yerleşik bir veri türüyle birlikte gelir. Sözlük, karma tablonun bir örneğidir. Değerleri bir çift anahtar ve değer kullanarak saklar. Karma değerleri bizim için otomatik olarak oluşturulur ve herhangi bir çarpışma bizim için arka planda çözümlenir.
Aşağıdaki örnek, bir sözlük veri türünün nasıl kullanılabileceğini gösterir python 3
employee = {
'name': 'John Doe',
'age': 36,
'position': 'Business Manager.'
}
print (f"The name of the employee is {employee['name']}")
employee['position'] = 'Software Engineer'
print (f"The position of {employee['name']} is {employee['position']}")
employee.clear()
print (employee)
İŞTE,
- Bir sözlük değişkeni çalışanını tanımlar. Anahtar adı, John Doe değerini, yaş depoları 36'yı ve konum, Business Manager değerini depolamak için kullanılır.
- Anahtar adının değerini alır ve terminalde yazdırır
- Anahtar konumun değerini Yazılım Mühendisi değerine günceller
- Tuşların adı ve konumunun değerlerini yazdırır
- Çalışan sözlük değişkenimizde saklanan tüm değerleri siler
- Çalışanın değerini yazdırır
Yukarıdaki kodu çalıştırdığınızda aşağıdaki sonuçlar elde edilir.
The name of the employee is John Doe.
The position of John Doe is a Software Engineer.
{}
Karmaşıklık Analizi
Karma tabloların en iyi senaryoda ortalama zaman karmaşıklığı O (1)'dir. En kötü durum zaman karmaşıklığı O(n)'dir. En kötü durum senaryosu, birçok değerin aynı karma anahtarını ürettiği ve çarpışmayı yoklayarak çözmemiz gerektiği zaman meydana gelir.
Gerçek Dünya Uygulamaları
Gerçek dünyada karma tablolar, verileri depolamak için kullanılır.
- veritabanları
- İlişkilendirilebilir diziler
- Setler
- Bellek önbellek
Hash tablolarının avantajları
Hash tablolarını kullanmanın artıları/yararları şunlardır:
- Hash tabloları veri ararken, mevcut değerleri eklerken ve silerken yüksek performansa sahiptir.
- Hash tabloları için zaman karmaşıklığı, tablodaki öğe sayısından bağımsız olarak sabittir.
- Büyük veri kümeleriyle çalışırken bile çok iyi performans gösterirler.
Hash tablolarının dezavantajları
Hash tablolarını kullanmanın dezavantajları şunlardır:
- Anahtar olarak boş bir değer kullanamazsınız.
- Anahtarları kullanarak oluştururken çarpışmalardan kaçınılamaz. karma işlevleri. Zaten kullanımda olan bir anahtar oluşturulduğunda çarpışmalar meydana gelir.
- Hashing fonksiyonunun çok sayıda çarpışması varsa bu durum performansın düşmesine neden olabilir.
ÖZET
- Hash tabloları, bir çift anahtar ve değer kullanarak verileri depolamak için kullanılır.
- Karma işlevi, karma değerini hesaplamak için matematiksel bir algoritma kullanır.
- Birden fazla değer için aynı hash değeri üretildiğinde çarpışma meydana gelir.
- Zincirleme, bağlantılı listeler oluşturarak çarpışmayı çözer.
- Problama, karma tablosundaki boş yuvaları bularak çarpışmayı çözer.
- Doğrusal problama, çarpışmanın meydana geldiği aralıktan başlayarak değeri depolamak için bir sonraki boş alanı arar.
- İkinci dereceden araştırma, bir çarpışma meydana geldiğinde bir sonraki boş slotu bulmak için polinom ifadelerini kullanır.
- Double Hashing, bir çarpışma meydana geldiğinde bir sonraki boş slotu bulmak için ikincil bir hash fonksiyonu algoritması kullanır.
- Hash tabloları diğer veri yapılarıyla karşılaştırıldığında daha iyi performansa sahiptir.
- Karma tabloların ortalama zaman karmaşıklığı O'dur (1)
- Python'daki sözlük veri türü karma tablosunun bir örneğidir.
- Hash tabloları ekleme, arama ve silme işlemlerini destekler.
- Boş bir değer dizin değeri olarak kullanılamaz.
- Hash fonksiyonlarında çarpışmalardan kaçınılamaz. İyi bir karma işlevi, performansı artırmak için meydana gelen çarpışmaların sayısını en aza indirir.
