Phenquestions
Yaşadığınız ilçede büyük bir erzak dükkanının sahibi olduğunuzu varsayın. Ticari bir alan olmayan geniş bir alanda yaşadığınızı varsayalım. Bölgede erzak dükkanı olan tek kişi siz değilsiniz; birkaç rakibin var. Sonra müşterilerinizin telefon numaralarını bir deftere kaydetmeniz gerektiği aklınıza geldi. Tabii ki, alıştırma kitabı küçüktür ve tüm müşterilerinizin tüm telefon numaralarını kaydedemezsiniz.
Böylece sadece düzenli müşterilerinizin telefon numaralarını kaydetmeye karar veriyorsunuz. Ve böylece iki sütunlu bir tablonuz var. Soldaki sütunda müşterilerin adları ve sağdaki sütunda ilgili telefon numaraları bulunur. Bu sayede müşteri isimleri ile telefon numaraları arasında bir eşleme olur. Tablonun sağ sütunu çekirdek karma tablosu olarak kabul edilebilir. Müşteri adlarına artık anahtar, telefon numaralarına da değerler deniyor. Bir müşteri transfere devam ettiğinde, sırasını iptal etmeniz, sıranın boş olmasına veya yeni bir normal müşterininkiyle değiştirilmesine izin vermeniz gerekeceğini unutmayın. Ayrıca zamanla düzenli müşteri sayısının artabileceğini veya azalabileceğini ve dolayısıyla tablonun büyüyüp küçülebileceğini unutmayın.
Bir başka haritalama örneği olarak, bir ilçede bir çiftçi kulübü olduğunu varsayalım. Tabii ki, tüm çiftçiler kulübe üye olmayacak. Kulübün bazı üyeleri düzenli üye olmayacak (katılım ve katkı). Barmen üyelerin isimlerini ve içecek seçimlerini kaydetmeye karar verebilir. İki sütunlu bir tablo geliştirir. Sol sütuna kulüp üyelerinin isimlerini yazar. Sağ sütunda, ilgili içecek seçimini yazıyor.
Burada bir sorun var: sağ sütunda kopyalar var. Yani bir içeceğin aynı adı birden fazla bulunur. Başka bir deyişle, farklı üyeler aynı tatlı içeceği veya aynı alkollü içeceği içerken, diğer üyeler farklı bir tatlı veya alkollü içecek içerler. Barmen, iki sütun arasına dar bir sütun ekleyerek bu sorunu çözmeye karar verir. Bu orta sütunda, üstten başlayarak sıfırdan başlayan satırları numaralandırır (i.e. 0, 1, 2, 3, 4, vb.), aşağı gidiyor, satır başına bir dizin. Bununla, üye adı artık bir içki adına değil bir dizine eşlendiğinden sorunu çözüldü. Bu nedenle, bir içecek bir dizin tarafından tanımlandığından, bir müşteri adı karşılık gelen dizine eşlenir.
Değerler (içecekler) sütunu tek başına temel karma tablosunu oluşturur. Değiştirilmiş tabloda, indeksler sütunu ve bunlarla ilişkili değerler (yinelenenler olsun veya olmasın) normal bir karma tablo oluşturur - bir karma tablonun tam tanımı aşağıda verilmiştir. Anahtarlar (ilk sütun) mutlaka karma tablosunun bir parçasını oluşturmaz.
Yine başka bir örnek olarak, bir kullanıcının istemci bilgisayarından bazı bilgileri ekleyebildiği, bazı bilgileri sildiği veya bazı bilgileri değiştirebildiği bir ağ sunucusunu düşünün. Sunucu için birçok kullanıcı var. Her kullanıcı adı, sunucuda saklanan bir parolaya karşılık gelir. Sunucunun bakımını yapanlar, kullanıcı adlarını ve ilgili şifreyi görebilir ve böylece kullanıcıların çalışmalarını bozabilir.
Böylece sunucunun sahibi, saklanmadan önce bir parolayı şifreleyen bir işlev üretmeye karar verir. Bir kullanıcı, normal anlaşılan şifresiyle sunucuya giriş yapar. Ancak artık her parola şifrelenmiş bir biçimde saklanıyor. Herhangi biri şifrelenmiş bir parola görür ve onu kullanarak oturum açmaya çalışırsa, çalışmaz, çünkü oturum açmak sunucu tarafından şifrelenmiş bir parola değil, anlaşılmış bir parola alır.
Bu durumda, anlaşılan parola anahtardır ve şifrelenmiş parola değerdir. Şifrelenmiş parola, şifrelenmiş parolalar sütunundaysa, o sütun temel bir karma tablodur. Bu sütundan önce sıfırdan başlayan endekslere sahip başka bir sütun geliyorsa, böylece her şifreli parola bir dizinle ilişkilendirilirse, hem dizin sütunu hem de şifreli parola sütunu normal bir karma tablo oluşturur. Anahtarlar mutlaka karma tablosunun bir parçası değildir.
Bu durumda, anlaşılan bir parola olan her anahtarın bir kullanıcı adına karşılık geldiğine dikkat edin. Dolayısıyla, bir dizine eşlenmiş bir anahtara karşılık gelen ve şifreli bir anahtar olan bir değerle ilişkilendirilen bir kullanıcı adı vardır.
Bir hash fonksiyonunun tanımı, bir hash tablosunun tam tanımı, bir dizinin anlamı ve diğer detaylar aşağıda verilmiştir. Bu öğreticinin geri kalanını takdir etmek için işaretçiler (referanslar) ve bağlantılı listeler hakkında bilgi sahibi olmanız gerekir.
Hash Fonksiyonu ve Hash Tablosunun Anlamı
Dizi
Bir dizi, ardışık bellek konumları kümesidir. Tüm konumlar aynı boyuttadır. İlk konumdaki değere 0 indeksi ile erişilir; ikinci konumdaki değere 1 indeksi ile ulaşılır; üçüncü değere indeks, 2 ile ulaşılır; indeksli dördüncü, 3; ve benzeri. Bir dizi normalde artamaz veya küçülemez. Bir dizinin boyutunu (uzunluğunu) değiştirmek için yeni bir dizi oluşturulmalı ve karşılık gelen değerler yeni diziye kopyalanmalıdır. Bir dizinin değerleri her zaman aynı tiptedir.
Özet fonksiyonu
Yazılımda, bir karma işlevi, bir anahtar alan ve bir dizi hücresi için karşılık gelen bir dizin üreten bir işlevdir. Dizi sabit bir boyuttadır (sabit uzunluk). Anahtarların sayısı, genellikle dizinin boyutundan daha büyük, rastgele boyuttadır. Hash fonksiyonundan kaynaklanan indekse hash değeri veya özet veya hash kodu veya basitçe hash denir.
Hash Tablosu
Bir karma tablo, indeksleri, anahtarları eşlenen değerlere sahip bir dizidir. Anahtarlar dolaylı olarak değerlere eşlenir. Aslında, anahtarların değerlerle eşlendiği söylenir, çünkü her dizin bir değerle ilişkilendirilir (yinelemeli veya kopyasız). Ancak, eşleme yapan işlev (i.e. hashing), değerlerde kopyalar olabileceğinden, anahtarları gerçekten değerlerle değil dizi indeksleriyle ilişkilendirir. Aşağıdaki şema, kişilerin adları ve telefon numaraları için bir karma tabloyu göstermektedir. Dizi hücrelerine (yuvalar) paketler denir.
Bazı kovaların boş olduğuna dikkat edin. Bir karma tablosunun tüm kovalarında mutlaka değerlere sahip olması gerekmez. Paketlerdeki değerlerin artan sırada olması gerekmez. Ancak, ilişkili oldukları endeksler artan sıradadır. Oklar eşlemeyi gösterir. Anahtarların bir dizide olmadığına dikkat edin. Herhangi bir yapıda olmaları gerekmez. Bir karma işlevi herhangi bir anahtarı alır ve bir dizi için bir dizini özetler. Karma işlemi yapılan dizinle ilişkili kovada herhangi bir değer yoksa, o kovaya yeni bir değer konabilir. Mantıksal ilişki anahtar ve dizin arasındadır, anahtar ile dizinle ilişkili değer arasında değil.
Bu karma tablodakiler gibi bir dizinin değerleri her zaman aynı veri türündendir. Bir karma tablosu (kovalar), anahtarları farklı veri türlerinin değerlerine bağlayabilir. Bu durumda, dizinin değerlerinin tümü farklı değer türlerine işaret eden işaretçilerdir.
Hash tablosu, hash işlevine sahip bir dizidir. İşlev bir anahtar alır ve karşılık gelen bir dizini hash eder ve böylece dizideki anahtarları değerlere bağlar. Anahtarların karma tablosunun bir parçası olması gerekmez.
Hash Tablosu için Neden Dizi ve Bağlantılı Liste Değil
Bir karma tablo dizisi, bağlantılı bir liste veri yapısı ile değiştirilebilir, ancak bir sorun olacaktır. Bağlantılı bir listenin ilk öğesi doğal olarak 0 dizinindedir; ikinci eleman doğal olarak 1 indeksindedir; üçüncüsü doğal olarak 2 indeksindedir; ve benzeri. Bağlantılı listedeki sorun, bir değer almak için listenin yinelenmesi gerektiğidir ve bu zaman alır. Bir dizideki bir değere rasgele erişimle erişilir. İndeks bilindiğinde, değer yineleme olmadan elde edilir; bu erişim daha hızlı.
Çarpışma
Karma işlevi, ilişkili değeri okumak veya yeni bir değer eklemek için bir anahtar alır ve karşılık gelen dizini hash eder. Amaç bir değeri okumak ise şu ana kadar bir sorun (sorun yok) yok. Ancak amaç bir değer eklemekse, karma dizin zaten ilişkili bir değere sahip olabilir ve bu bir çakışmadır; yeni değer, zaten bir değerin olduğu yere konamaz. Çarpışmayı çözmenin yolları vardır - aşağıya bakın.
Çarpışma Neden Oluşur?
Yukarıdaki provizyon dükkanı örneğinde, müşteri isimleri anahtarlar ve içeceklerin isimleri değerlerdir. Dizinin sınırlı bir boyutu varken müşterilerin çok fazla olduğuna ve tüm müşterileri alamayacağına dikkat edin. Böylece dizide sadece düzenli müşterilerin içecekleri saklanır. Çarpışma, düzenli olmayan bir müşteri düzenli hale geldiğinde meydana gelir. Dükkanın müşterileri büyük bir küme oluştururken, dizideki müşteriler için kova sayısı sınırlıdır.
Hash tabloları ile, kaydedilen, çok olası olan anahtarların değerleridir. Olası olmayan bir anahtar olası hale geldiğinde, muhtemelen bir çarpışma olacaktır. Aslında, çarpışma her zaman karma tablolarla gerçekleşir.
Çarpışma Çözünürlüğü Temelleri
Çarpışma çözümüne yönelik iki yaklaşım, Ayrı Zincirleme ve Açık Adresleme olarak adlandırılır. Teorik olarak, anahtarlar veri yapısında olmamalı veya hash tablosunun bir parçası olmamalıdır. Ancak, her iki yaklaşım da anahtar sütunun karma tablosundan önce gelmesini ve genel yapının bir parçası olmasını gerektirir. Anahtarlar, anahtarlar sütununda olmak yerine, anahtarlara yönelik işaretçiler anahtarlar sütununda olabilir.
Pratik bir karma tablosu bir anahtar sütunu içerir, ancak bu anahtar sütun resmi olarak karma tablosunun bir parçası değildir.
Çözüm için her iki yaklaşımın da dizinin sonunda olması gerekmeyen boş kovaları olabilir.
Ayrı Zincirleme
Ayrı zincirlemede, bir çarpışma meydana geldiğinde, çarpışan değerin sağına (yukarıda veya aşağıda değil) yeni değer eklenir. Böylece iki veya üç değer aynı dizine sahip olur. Nadiren üçten fazlası aynı dizine sahip olmalıdır.
Bir dizide birden fazla değer gerçekten aynı dizine sahip olabilir mi?? - Hayır. Bu nedenle, çoğu durumda, dizin için ilk değer, bir, iki veya üç çarpışmış değeri tutan bağlantılı bir liste veri yapısına yönelik bir işaretçidir. Aşağıdaki şema, müşterilerin ve telefon numaralarının ayrı zincirlenmesi için bir karma tablo örneğidir:
Boş kovalar x harfi ile işaretlenmiştir. Yuvaların geri kalanında bağlantılı listelere işaretçiler bulunur. Bağlantılı listenin her öğesi iki veri alanına sahiptir: biri müşteri adı için, diğeri telefon numarası için. Anahtarlar için çatışma çıkıyor: Peter Jones ve Suzan Lee. Karşılık gelen değerler, bağlantılı bir listenin iki öğesinden oluşur.
Çakışan anahtarlar için, değer ekleme kriteri, değeri bulmak (ve okumak) için kullanılan kriterle aynıdır.
Açık Adresleme
Açık adresleme ile tüm değerler kova dizisinde saklanır. Çakışma meydana geldiğinde, yeni değer, bazı kriterler izlenerek, çatışmaya karşılık gelen yeni değer olan boş bir kovaya eklenir. Çakışan bir değer eklemek için kullanılan kriter, değeri bulmak (aramak ve okumak) için kullanılan kriterle aynıdır.
Aşağıdaki şema, açık adresleme ile çakışma çözümünü göstermektedir:
Karma işlevi, Peter Jones anahtarını alır ve 152 dizini hash eder ve telefon numarasını ilgili klasörde saklar. Bir süre sonra, karma işlevi aynı dizini hash eder, anahtardan 152, Suzan Lee, Peter Jones için dizinle çarpışır. Bunu çözmek için, Suzan Lee'nin değeri, boş olan bir sonraki dizin olan 153'ün kovasında saklanır. Karma işlevi, anahtar için 153 dizini hash eder, Robin Hood, ancak bu dizin önceki bir anahtar için çatışmayı çözmek için zaten kullanılmıştır. Böylece Robin Hood'un değeri, 154 indeksinin değeri olan bir sonraki boş kovaya yerleştirilir.
Ayrı Zincirleme ve Açık Adresleme için Çakışmaları Çözme Yöntemleri
Ayrı zincirlemenin çatışmaları çözme yöntemleri vardır ve açık adreslemenin de çatışmaları çözmek için kendi yöntemleri vardır.
Ayrı Zincirleme Çakışmalarını çözme yöntemleri
Ayrı zincirleme karma tabloları için yöntemler şimdi kısaca açıklanmıştır:
Bağlantılı Listelerle Ayrı Zincirleme
Bu yöntem yukarıda açıklandığı gibidir. Ancak, bağlantılı listenin her bir elemanı mutlaka anahtar alanına sahip olmak zorunda değildir (e.g. yukarıdaki müşteri adı alanı).
Liste Baş Hücreleri ile Ayrı Zincirleme
Bu yöntemde, bağlantılı listenin ilk elemanı dizinin bir kovasında saklanır. Bu, dizinin veri türü bağlantılı listenin öğesiyse mümkündür.
Diğer Yapılarla Ayrı Zincirleme
Gerekli işlemleri destekleyen Kendi Kendini Dengeleyen İkili Arama Ağacı gibi diğer herhangi bir veri yapısı, bağlantılı liste yerine kullanılabilir - daha sonra bakın.
Açık Adresleme Çakışmalarını çözme yöntemleri
Açık adreslemede çakışmayı çözmek için bir yönteme araştırma dizisi denir. İyi bilinen üç prob dizisi şimdi kısaca açıklanmıştır:
Doğrusal Sondalama
Doğrusal yoklama ile, bir çakışma meydana geldiğinde, çakışan kovanın altındaki en yakın boş kova aranır. Ayrıca lineer problama ile hem anahtar hem de değeri aynı kovada saklanır.
İkinci Dereceden Sondalama
Çatışmanın H indeksinde gerçekleştiğini varsayalım. H + 1 dizinindeki bir sonraki boş yuva (kova)2 kullanıldı; bu zaten doluysa, H + 2'deki bir sonraki boş olan2 zaten doluysa, H + 3'te bir sonraki boş olan kullanılır2 kullanılır ve benzeri. bunun varyantları var.
Çift Karma
Çift hash ile iki hash fonksiyonu vardır. İlki dizini hesaplar (karmalar). Bir çakışma meydana gelirse, ikincisi, değerin ne kadar aşağıya eklenmesi gerektiğini belirlemek için aynı anahtarı kullanır. Bunun daha fazlası var - sonra bakın.
Mükemmel Hash Fonksiyonu
Mükemmel bir özet işlevi, herhangi bir çarpışmaya neden olmayan bir özet işlevidir. Bu, anahtar kümesi nispeten küçük olduğunda ve her bir anahtar, karma tablosundaki belirli bir tamsayı ile eşlendiğinde meydana gelebilir.
ASCII Karakter Kümesi'nde, büyük harfli karakterler, bir karma işlevi kullanılarak karşılık gelen küçük harflerle eşlenebilir. Harfler bilgisayar belleğinde sayılarla temsil edilir. ASCII Karakter Setinde A 65, B 66, C 67, vb. ve a 97, b 98, c 99, vb. A'dan a'ya eşlemek için 32'den 65'e ekleyin; B'den b'ye eşlemek için 32'yi 66'ya ekleyin; C'den c'ye eşlemek için 32'den 67'ye ekleyin; ve benzeri. Burada büyük harfler tuşlar, küçük harfler değerlerdir. Bunun için hash tablosu, değerleri ilişkili indeksler olan bir dizi olabilir. Unutmayın, dizinin kovaları boş olabilir. Böylece 64'ten 0'a kadar dizideki kovalar boş olabilir. Karma işlevi, dizini elde etmek için büyük harf kod numarasına 32 ekler ve dolayısıyla küçük harf. Böyle bir fonksiyon mükemmel bir hash fonksiyonudur.
Tamsayıdan Tamsayı İndekslerine Hashing
Tamsayı hash için farklı yöntemler vardır. Bunlardan biri Modulo Bölme Metodu (İşlev) olarak adlandırılır.
Modulo Division Hashing Fonksiyonu
Bilgisayar yazılımındaki bir fonksiyon matematiksel bir fonksiyon değildir. Hesaplamada (yazılımda), bir işlev, bağımsız değişkenlerden önce gelen bir dizi ifadeden oluşur. Modulo Bölme İşlevi için, anahtarlar tam sayılardır ve kova dizisinin dizinleriyle eşlenir. Anahtar kümesi büyüktür, bu nedenle yalnızca etkinlikte ortaya çıkma olasılığı çok yüksek olan anahtarlar eşlenir. Bu nedenle, olası olmayan anahtarların eşlenmesi gerektiğinde çarpışmalar meydana gelir.
açıklamada,
20 / 6 = 3R2
20 temettü, 6 bölen ve 3 kalan 2 bölümdür. Kalan 2, modulo olarak da adlandırılır. Not: Modulo'nun 0 olması mümkündür.
Bu karma için, tablo boyutu genellikle 2, e'nin gücüdür.g. 64 = 26 veya 256 = 28, vb. Bu hash işlevinin böleni, dizi boyutuna yakın bir asal sayıdır. Bu işlev anahtarı bölenle böler ve modulo değerini döndürür. Modulo, kova dizisinin indeksidir. Paketteki ilişkili değer, seçtiğiniz bir değerdir (anahtarın değeri).
Değişken Uzunluk Anahtarlarını Hash Etme
Burada, tuş takımının tuşları farklı uzunluklardaki metinlerdir. Aynı sayıda bayt kullanılarak bellekte farklı tam sayılar saklanabilir (İngilizce karakterin boyutu bir bayttır). Farklı anahtarlar farklı bayt boyutlarında olduğunda, bunların değişken uzunlukta olduğu söylenir. Değişken uzunlukları hash etme yöntemlerinden biri Radix Conversion Hashing olarak adlandırılır.
Radix Dönüşüm Karması
Bir dizgede, bilgisayardaki her karakter bir sayıdır. Bu yöntemde,
Hash Kodu (indeks) = x0birk-1+x1birk-2+… +xk-2bir1+xk-1bir0
Burada (x0, x1,… , xk−1) giriş dizesinin karakterleridir ve a bir sayı tabanıdır, e.g. 29 (daha sonra bakınız). k, dizideki karakter sayısıdır. Bunun daha fazlası var - sonra bakın.
Anahtarlar ve Değerler
Bir anahtar/değer çiftinde, değer mutlaka bir sayı veya metin olmayabilir. rekor da olabilir. Kayıt, yatay olarak yazılmış bir listedir. Bir anahtar/değer çiftinde, her bir anahtar aslında başka bir metne, sayıya veya kayda atıfta bulunuyor olabilir.
ilişkisel dizi
Liste, liste öğelerinin ilişkili olduğu ve listede çalışan bir dizi işlemin bulunduğu bir veri yapısıdır. Her liste öğesi bir çift öğeden oluşabilir. Anahtarları ile birlikte genel hash tablosu bir veri yapısı olarak düşünülebilir, ancak bir veri yapısından çok bir sistemdir. Anahtarlar ve bunlara karşılık gelen değerler birbirine çok bağımlı değildir. Birbirleriyle pek ilgili değiller.
Öte yandan, bir ilişkisel dizi benzer bir şeydir, ancak anahtarlar ve değerleri birbirine çok bağlıdır; birbirleriyle çok ilgililer. Örneğin, ilişkisel bir dizi meyveye ve renklerine sahip olabilirsiniz. Her meyvenin doğal olarak kendi rengi vardır. Meyvenin adı anahtardır; renk değerdir. Ekleme sırasında, her anahtar değeriyle birlikte eklenir. Silerken, her anahtar değeriyle birlikte silinir.
Bir ilişkisel dizi, anahtarlar için herhangi bir kopyanın olmadığı, anahtar/değer çiftlerinden oluşan bir karma tablo veri yapısıdır. Değerlerin kopyaları olabilir. Bu durumda, anahtarlar yapının bir parçasıdır. Yani, anahtarların saklanması gerekirken, genel hast tablosunda anahtarların saklanması gerekmez. Yinelenen değerler sorunu, kova dizisinin endeksleri tarafından doğal olarak çözülür. Bir dizinde yinelenen değerler ve çarpışma arasında karıştırmayın.
İlişkisel dizi bir veri yapısı olduğundan, en azından aşağıdaki işlemlere sahiptir:
İlişkili Dizi İşlemleri
ekle veya ekle
Bu, anahtarı değerine eşleyerek koleksiyona yeni bir anahtar/değer çifti ekler.
yeniden atamak
Bu işlem, belirli bir anahtarın değerini yeni bir değerle değiştirir.
sil veya kaldır
Bu, bir anahtarı artı karşılık gelen değerini kaldırır.
yukarı Bak
Bu işlem, belirli bir anahtarın değerini arar ve değeri döndürür (kaldırmadan).
Sonuç
Bir karma tablo veri yapısı, bir dizi ve bir işlevden oluşur. İşleve karma işlevi denir. İşlev, anahtarları dizinin dizinleri aracılığıyla dizideki değerlere eşler. Anahtarlar mutlaka veri yapısının bir parçası olmamalıdır. Anahtar seti genellikle depolanan değerlerden daha büyüktür. Bir çarpışma meydana geldiğinde, Ayrı Zincirleme Yaklaşımı veya Açık Adresleme Yaklaşımı ile çözülür. İlişkisel dizi, karma tablo veri yapısının özel bir durumudur.
