Hashing nedir?
Karma, sabit bir uzunluğa sahip bir değerdir ve matematiksel bir formül kullanılarak oluşturulur. Karma değerler, veri sıkıştırmada, kriptolojide vb. Kullanılır. Veri indekslemede, karma değerler, onları oluşturmak için kullanılan değerlerden bağımsız olarak sabit uzunluk boyutuna sahip oldukları için kullanılır. Karma değerlerin, değişen uzunluklardaki diğer değerlere kıyasla minimum yer kaplamasını sağlar.
Karma işlevi, anahtarı karmaya dönüştürmek için matematiksel bir algoritma kullanır. Bir karma işlevi birden fazla anahtar için aynı karma değeri ürettiğinde bir çarpışma meydana gelir.
Bu Algoritma eğitiminde şunları öğreneceksiniz:
- Hashing nedir?
- Karma Tablo nedir?
- Hash fonksiyonları
- İyi bir hash fonksiyonunun nitelikleri
- Çarpışma
- Karma tablo işlemleri
- Karma Tablosu Python Örneği
- Karma Tablosu Kodu Açıklaması
- Python Sözlük Örneği
- Karmaşıklık Analizi
- Gerçek Dünya Uygulamaları
- Hash tablolarının avantajları
- Karma tabloların dezavantajları
Karma Tablo nedir?
Bir karma tablo depolar değerleri şifreler ve değerleri çifti kullanılarak bir veri yapısıdır. Her değere, bir 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 tablodaki öğelerin sayısına bakılmaksızın, bir karma tablodaki değerlerin aranmasını çok hızlı hale getirir.
Hash fonksiyonları
Örneğin, çalışan kayıtlarını saklamak istiyorsak ve her çalışan bir çalışan numarası kullanılarak benzersiz bir şekilde tanımlanır.
Çalışan numarasını anahtar olarak kullanabilir ve çalışan verilerini değer olarak atayabiliriz.
Yukarıdaki yaklaşım düzeninin ilave boş alan gerektirecektir (m * n 2 ) değişken m dizinin büyüklüğü ve değişken n çalışan sayıda basamak sayısıdır. Bu yaklaşım, bir depolama alanı sorunu ortaya çıkarır.
Bir karma işlevi, çalışan numarasını alarak ve bir karma tam sayı değeri, sabit rakamlar ve depolama alanını optimize etmek için kullanarak yukarıdaki sorunu çözer. Bir karma işlevin amacı, saklamak istediğimiz değere başvurmak 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 hash işlevi örneği verilmiştir
h(k) = k1 % m
İŞTE,
- h (k), k parametresini kabul eden karma işlevdir. K parametresi, anahtarını hesaplamak istediğimiz değerdir.
- k 1 % m, hash fonksiyonumuz için algoritmadır; burada k1 saklamak istediğimiz değerdir ve m, listenin boyutudur. Anahtarı hesaplamak için modül operatörünü kullanırız.
Misal
Sabit boyutlu 3 ve aşağıdaki değerlere sahip bir listemiz olduğunu varsayalım.
[1,2,3]
Her bir değerin kaplaması gereken konumları hesaplamak için yukarıdaki formülü kullanabiliriz.
Aşağıdaki resim, hash tablomuzdaki mevcut indeksleri göstermektedir.
Aşama 1)
İlk değerin işgal edeceği konumu şu şekilde hesaplayın
h (1) =% 1 3
= 1
1 değeri , dizin 1'deki alanı kaplar
Adım 2)
İkinci değerin işgal edeceği konumu hesaplayın
h (2) =% 2 3
= 2
2 değeri , dizin 2'deki alanı kaplar
Aşama 3)
Üçüncü değerin işgal edeceği konumu hesaplayın.
h (3) =% 3 3
= 0
3 değeri , 0 dizinindeki alanı kaplar
Son sonuç
Doldurulmuş hash tablomuz artık aşağıdaki gibi olacaktır.
İyi bir hash fonksiyonunun nitelikleri
İyi bir hash işlevi aşağıdaki niteliklere sahip olmalıdır.
- Karma oluşturma formülü, algoritmada depolanacak verilerin değerini kullanmalıdır.
- Hash fonksiyonu, aynı miktara sahip giriş verileri için bile benzersiz hash değerleri üretmelidir.
- İşlev, çarpışma sayısını en aza indirmelidir. Birden fazla değer için aynı değer üretildiğinde çarpışmalar meydana gelir.
- Değerler, tüm olası karmalar arasında tutarlı bir şekilde dağıtılmalıdır.
Çarpışma
Algoritma birden fazla değer için aynı hash ürettiğinde bir ç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 m'nin hash tablosunun boyutu olduğu (k % 1 m) formülünü kullanacağız .
Aşağıdaki tablo, oluşturulacak hash değerlerini göstermektedir.
| Anahtar | Hash Algoritması (k % 1 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 araştırma kullanılarak çözülebilir. Aşağıdaki bölümlerde zincirleme ve araştırma ayrıntılı olarak ele alınmaktadır.
Zincirleme
Zincirleme, her biri benzersiz dizinlere sahip bağlantılı listeler kullanarak çarpışma sorununu çözmek için kullanılan bir tekniktir.
Aşağıdaki resim, zincirleme listenin nasıl göründüğünü görselleştiriyor
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ı
Aşağıdakiler, zincirleme listelerin faydalarıdır:
- Zincirleme listeler, veri eklenirken daha iyi performansa sahiptir, çünkü ekleme sırası O (1) 'dir.
- Zincirleme liste kullanan bir karma tabloyu yeniden boyutlandırmak gerekli değildir.
- Boş alan olduğu sürece çok sayıda değeri kolayca barındırabilir.
İnceleme
Çarpışmayı çözmek için kullanılan diğer teknik araştırmadır. Araştırma yöntemini kullanırken, bir çarpışma meydana gelirse, değerimizi saklamak için basitçe devam edebilir ve boş bir yuva bulabiliriz.
Aşağıdakiler, araştırma yöntemleri:
| Yöntem | Açıklama |
| Doğrusal inceleme | Adından da anlaşılacağı gibi, bu yöntem, çarpışmanın meydana geldiği konumdan başlayıp ileriye doğru doğrusal olarak boş yuvaları arar. Listenin sonuna ulaşılırsa ve boş alan bulunmazsa. İnceleme, listenin başında başlar. |
| İkinci dereceden araştırma | Bu yöntem, bir sonraki kullanılabilir boş yuvayı bulmak için ikinci dereceden polinom ifadeleri kullanır. |
| Çift Hashing | Bu teknik, bir sonraki boş yuvayı bulmak için ikincil bir hash fonksiyonu algoritması kullanır. |
Yukarıdaki örneğimizi kullanarak, araştırmayı kullandıktan sonra hash tablosu aşağıdaki gibi görünecektir:
Karma tablo işlemleri
Hash tabloları tarafından desteklenen İşlemler şunlardır:
- Ekleme - bu İşlem, karma tabloya bir öğe eklemek için kullanılır
- Arama - bu İşlem, anahtarı kullanarak karma tablosundaki öğeleri aramak için kullanılır
- Silme - bu İşlem, öğeleri hash tablosundan silmek için kullanılır
Veri işlemi ekleme
Ekleme işlemi, değerleri hash tablosunda saklamak için kullanılır. Karma tablosunda yeni bir değer saklandığında, buna bir dizin numarası atanır. Dizin numarası, karma işlevi kullanılarak hesaplanır. Karma işlevi, dizin numarasını hesaplarken meydana gelen herhangi bir çarpışmayı çözer.
Veri operasyonu arayın
Arama işlemi, indeks numarasını kullanarak karma tablodaki değerleri aramak için kullanılır. Arama işlemi, arama indeksi numarasına bağlı değeri döndürür. Örneğin, 6 değerini dizin 2'de saklarsak, dizin numarası 2 olan arama işlemi 6 değerini döndürecektir.
Veri işlemini sil
Silme işlemi, karma tablodan bir değeri kaldırmak için kullanılır. İşlemi silmek için indeks numarası kullanılarak yapılır. Bir değer silindiğinde, dizin numarası serbest bırakılır. Ekleme işlemini kullanarak diğer değerleri saklamak için kullanılabilir.
Python Örneği ile Karma Tablo Uygulaması
Bir anahtarın hash değerini hesaplayan basit bir örneğe bakalım.
def hash_key( key, m):return key % mm = 7print(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)}')
Karma Tablosu Kodu Açıklaması
İŞTE,
- Hash_key işlevini tanımlar ve anahtar ve m parametrelerini kabul eder.
- Karma 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, hash tablomuzun boyutudur.
- 3'ün karma değerini hesaplar ve yazdırır
- 2'nin karma değerini hesaplar ve yazdırır
- 9'un karma değerini hesaplar ve yazdırır
- 11'in karma değerini hesaplar ve yazdırır
- 7'nin karma değerini hesaplar ve yazdırır
Yukarıdaki kodun yürütülmesi aşağıdaki sonuçları verir.
The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0
Python Sözlük Örneği
Python, Dictionary adı verilen yerleşik bir veri türüyle birlikte gelir. Sözlük, karma tablo örneğidir. Değerleri bir çift anahtar ve değer kullanarak depolar. Karma değerler bizim için otomatik olarak oluşturulur ve herhangi bir çarpışma arka planda bizim için çözülür.
Aşağıdaki örnek, python 3'te bir sözlük veri türünü nasıl kullanabileceğinizi gösterir
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şken çalışanı tanımlar. Anahtar adı, John Doe değerini saklamak için kullanılır, 36 yaş deposu ve konum, Business Manager değerini depolar.
- Anahtar adının değerini alır ve terminale yazdırır
- Anahtar konumun değerini Yazılım Mühendisi değerine günceller
- Anahtar adının ve konumunun değerlerini yazdırır
- Sözlüğümüzde saklanan tüm değerleri siler değişken
- Çalışanın değerini yazdırır
Yukarıdaki kodu çalıştırmak aşağıdaki sonuçları verir.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Karmaşıklık Analizi
Karma tablolar, en iyi durum senaryosunda O (1) ortalama zaman karmaşıklığına sahiptir. En kötü durum zaman karmaşıklığı O (n) 'dir. En kötü durum senaryosu, birçok değer aynı hash anahtarını oluşturduğunda ortaya çıkar ve çarpışmayı araştırarak çözmemiz gerekir.
Gerçek Dünya Uygulamaları
Gerçek dünyada, karma tablolar için verileri depolamak için kullanılır.
- Veritabanları
- İlişkilendirilebilir diziler
- Setleri
- Bellek önbelleği
Hash tablolarının avantajları
Karma tablo kullanmanın artıları / faydaları şunlardır:
- Karma tablolar veri ararken, mevcut değerleri eklerken ve silerken yüksek performansa sahiptir.
- Karma tablolar için zaman karmaşıklığı, tablodaki öğelerin sayısına bakılmaksızın sabittir.
- Büyük veri kümeleriyle çalışırken bile çok iyi performans gösterirler.
Karma tabloların dezavantajları
Karma tablo kullanmanın dezavantajları şunlardır:
- Anahtar olarak boş bir değer kullanamazsınız.
- Kullanarak anahtarlar oluştururken çarpışmalardan kaçınılamaz. karma işlevler. Çarpışmalar, halihazırda kullanımda olan bir anahtar üretildiğinde meydana gelir.
- Hashing işlevinde birçok çarpışma varsa, bu performans düşüşüne neden olabilir.
Özet:
- Karma tablolar, bir çift anahtar ve değer kullanarak verileri depolamak için kullanılır.
- Bir karma işlevi, karma değerini hesaplamak için matematiksel bir algoritma kullanır.
- Birden fazla değer için aynı karma değer üretildiğinde bir çarpışma meydana gelir.
- Zincirleme, bağlantılı listeler oluşturarak çarpışmayı çözer.
- İnceleme, hash tablosunda boş yuvalar bularak çarpışmayı çözer.
- Doğrusal inceleme, çarpışmanın meydana geldiği yuvadan başlayarak değeri saklamak için bir sonraki boş yuvayı arar.
- İkinci dereceden araştırma, bir çarpışma meydana geldiğinde bir sonraki boş yuvayı bulmak için polinom ifadeleri kullanır.
- Çift hashing, bir çarpışma meydana geldiğinde bir sonraki boş yuvayı bulmak için ikincil bir hash fonksiyonu algoritması kullanır.
- Karma tablolar, diğer veri yapılarına kıyasla daha iyi performansa sahiptir.
- Karma tabloların ortalama zaman karmaşıklığı O (1)
- Python'daki bir sözlük veri türü, bir karma tablo örneğidir.
- Karma tablolar ekleme, arama ve silme işlemlerini destekler.
- Boş değer, dizin değeri olarak kullanılamaz.
- Hash fonksiyonlarında çarpışmalardan kaçınılamaz. İyi bir hash işlevi, performansı iyileştirmek için meydana gelen çarpışmaların sayısını en aza indirir.