Özet fonksiyonu
Bu bölümde veri yapısında yer alan veri öğesine ait ilgili anahtarın hash kodunun çalıştırılmasına yardımcı olan hash fonksiyonunu aşağıda bahsedildiği gibi ele alacağız:
Int hashItem ( int anahtar ){
geri dönmek anahtar % masa boyutu ;
}
Bir dizinin indeksini çalıştırma işlemine karma denir. Bazen, farklı zincirleme (bağlantılı liste oluşturma) ve açık adresleme stratejilerinin uygulanması yoluyla gerçekleştirilen, çarpışma adı verilen aynı anahtarları kullanarak aynı dizini oluşturmak için aynı kod türü yürütülür.
C++'da Hash Table'ın Çalışması
Gerçek değerleri gösteren işaretçiler karma tablosunda tutulur. Anahtarlara karşı değerlerin bir dizide istenen konumda saklanması gereken bir dizinin dizinini aramak için bir anahtar kullanır. Aşağıda belirtildiği gibi 10 boyutlu hash tablosunu aldık:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Herhangi bir veriyi farklı anahtarlara karşı rastgele alalım ve bu anahtarları sadece indeksi hesaplayarak bir hash tablosunda saklayalım. Böylece veriler, bir hash fonksiyonu yardımıyla hesaplanan indeksteki anahtarlara karşı saklanır. Diyelim ki bir veri = {14,25,42,55,63,84} ve anahtarlar =[ 15,9,5,25,66,75 ] alıyoruz.
Hash fonksiyonunu kullanarak bu verilerin indeksini hesaplayın. İndeks değeri aşağıda belirtilmiştir:
| Anahtar | on beş | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Endeksi Hesapla | %1510 = 5 | %910=0 | %2910=9 | %4310=3 | %6610=6 | %7110=1 |
| Veri | 14 | 25 | 42 | 55 | 63 | 84 |
Bir dizinin indeksini oluşturduktan sonra, daha önce açıklandığı gibi verileri, belirli bir dizinin tam indeksine anahtara yerleştirin.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Bundan sonra, iki veya daha fazla anahtarın aynı hash koduna sahip olması durumunda, dizideki öğelerin aynı indeksiyle sonuçlanan bir çarpışmanın meydana geldiğini görebiliriz. Çarpışma olasılığını önlemek için tek bir çözümümüz var: iyi bir hash yöntemi seçmek ve doğru stratejileri uygulamak.
Şimdi farklı uygulama tekniklerini uygun örnekler yardımıyla tartışalım.
Örnek: Açık Karma Tekniği Kullanarak Karma Tablosuna Veri Ekleme
Bu örnekte, hash tablosunda çarpışmayı önlemek için Open Hashing gibi bir uygulama tekniğini kullanıyoruz. Açık karma veya zincirlemede, karma tablosunun değerlerini zincirlemek için bağlantılı bir liste oluştururuz. Bu örneğin kod pasajı, açık karma tekniğini açıklayan aşağıya eklenmiştir:
#include#include
sınıf Karma Tablo {
özel :
statik yapı int masa boyutu = 10 ;
std :: liste < int > masaVar [ masa boyutu ] ;
int hashFunc ( int anahtar ) {
geri dönmek anahtar % masa boyutu ;
}
halk :
geçersiz sokmak ( int anahtar ) {
int dizin = hashFunc ( anahtar ) ;
masaVar [ dizin ] . Geri itmek ( anahtar ) ;
}
geçersiz görünümTablosu ( ) {
için ( int Ben = 0 ; Ben < masa boyutu ; ++ Ben ) {
std :: cout << '[' << Ben << ']' ;
için ( Oto BT = masaVar [ Ben ] . başlamak ( ) ; BT ! = masaVar [ Ben ] . son ( ) ; ++ BT ) {
std :: cout << ' -> ' << * BT ;
}
std :: cout << std :: sonunda ;
}
}
} ;
int ana ( ) {
HashTable hasTable ;
hasTable. sokmak ( on beş ) ;
hasTable. sokmak ( 33 ) ;
hasTable. sokmak ( 23 ) ;
hasTable. sokmak ( 65 ) ;
hasTable. sokmak ( 3 ) ;
hasTable. görünümTablosu ( ) ;
geri dönmek 0 ;
}
Bu çok ilginç bir örnek: bağlantılı bir liste oluşturuyoruz ve verileri karma tablosuna ekliyoruz. Öncelikle programın başında kütüphaneleri tanımlıyoruz. < liste > Kütüphane bağlantılı liste uygulaması için kullanılır. Daha sonra “HashTable” isminde bir sınıf oluşturuyoruz ve “private:” anahtar sözcüğünü kullanarak sınıfın tablo boyutu ve tablo dizisi gibi özel olan niteliklerini oluşturuyoruz. Özel niteliklerin sınıf dışında kullanılamayacağını unutmayın. Burada tablonun boyutunu “10” olarak alıyoruz. Bunu kullanarak hash yöntemini başlatıyoruz ve hash tablosunun indeksini hesaplıyoruz. Hash fonksiyonunda hash tablosunun anahtarını ve boyutunu aktarıyoruz.
Gerekli birkaç fonksiyonu derliyoruz ve bu fonksiyonları sınıfta herkese açık hale getiriyoruz. Public fonksiyonların sınıf dışında her yerde kullanılabileceğini unutmayın. Sınıfın herkese açık kısmını başlatmak için “public:” anahtar sözcüğünü kullanırız . Hash tablosuna yeni elemanlar eklemek istediğimiz için fonksiyonun argümanı olarak bir anahtar içeren “InsertHash” adında bir fonksiyon oluşturuyoruz. “Insert” fonksiyonunda indeks değişkenini başlatıyoruz. Hash fonksiyonunu indeks değişkenine aktarıyoruz. Bundan sonra, tabloya bir öğe eklemek için indeks değişkenini “push” yöntemini kullanarak bağlı liste tableHas[]'a iletin.
Bundan sonra yeni eklenen verileri görmek için hash tablosunu görüntüleyecek bir “viewHashTab” fonksiyonu oluşturuyoruz. Bu fonksiyonda hash tablosunun sonuna kadar değerleri arayan bir “for” döngüsü alıyoruz. Değerlerin karma işlevi kullanılarak geliştirilen aynı dizinde saklandığından emin olun. Döngüde değerleri ilgili indekslerine aktarıyoruz ve sınıfı burada sonlandırıyoruz. “Main” fonksiyonunda ise “hasTable” isimli bir sınıfın nesnesini alıyoruz. Bu sınıf nesnesi yardımıyla yöntemdeki anahtarı geçirerek ekleme yöntemine erişebiliriz. “Main” fonksiyonunda aktardığımız anahtar, hash tablosundaki indeks konumunu döndüren “insert” fonksiyonunda hesaplanıyor. Bir “Class” nesnesi yardımıyla “view” fonksiyonunu çağırarak hash tablosunu görüntüledik.
Bu kodun çıktısı aşağıdaki dosyaya eklenmiştir:
Gördüğümüz gibi hash tablosu C++'daki bağlantılı liste kullanılarak başarıyla oluşturuldu. Aynı endeksin çarpışmasını önlemek için açık zincirleme kullanılır.
Çözüm
Sonuçta, büyük miktarda veriyi verimli bir şekilde işlemek için değer çiftlerine sahip anahtarları depolamak ve almak için karma tablosunun en yeni ortaya çıkan teknik olduğu sonucuna vardık. Hash tablosunda çarpışma olasılığı çok yüksektir, bu da veriyi ve depolama alanını tahrip eder. Hash tablosu yönetiminin farklı tekniklerini kullanarak bu çarpışmanın üstesinden gelebiliriz. Geliştiriciler, karma tablosunu C++'da geliştirerek, verileri karma tablosunda depolamak için en uygun tekniği kullanarak performansı artırabilir. Bu makalenin karma tablosunu anlamanıza yardımcı olacağını umuyoruz.