Veri Yapısında Hashing: Fonksiyon, Teknikler [Örneklerle]

Tanıtım

Hashing, bir dizideki verileri verimli bir şekilde bulma ve depolama sorununu çözmek için tasarlanmış önemli bir veri yapısıdır . Örneğin, 20000 numaradan oluşan bir listeniz varsa ve bu listede aranacak bir numara verdiyseniz, bir eşleşme bulana kadar listedeki her numarayı tarayacaksınız.

Tüm listede arama yapmak ve o belirli numarayı bulmak için önemli miktarda zamanınızı gerektirir. Bu manuel tarama süreci, yalnızca zaman alıcı olmakla kalmaz, aynı zamanda verimsizdir. Veri yapısındaki hashing ile aramayı daraltabilir ve saniyeler içinde sayıyı bulabilirsiniz.

Bu blog size hash metodu, hash tabloları ve örneklerle lineer problama hakkında daha derin bir anlayış sağlayacaktır.

Veri Yapısında Hashing Nedir?

Veri yapısında karma oluşturma, bir karma işlevi kullanarak büyük bir veri yığınını küçük tablolara eşleme tekniğidir. Mesaj özeti işlevi olarak da bilinir. Benzer öğelerden oluşan bir koleksiyondan belirli bir öğeyi benzersiz bir şekilde tanımlayan bir tekniktir.

Verileri bir dizi biçiminde depolamak için karma tabloları kullanır. Dizideki her değere benzersiz bir dizin numarası atanmıştır. Karma tabloları, bir dizi biçiminde depolanan her değer için bu benzersiz dizin numaralarını oluşturmak için bir teknik kullanır. Bu tekniğe hash tekniği denir.

Verileri bulmak yerine yalnızca istediğiniz öğenin dizinini bulmanız gerekir. İndeksleme ile tüm listeyi hızlıca tarayabilir ve istediğiniz öğeye ulaşabilirsiniz. Dizin oluşturma, belirli bir konuma veri eklemeniz gerektiğinde işlemleri eklemeye de yardımcı olur. Tablo ne kadar büyük veya küçük olursa olsun, verileri saniyeler içinde güncelleyebilir ve alabilirsiniz.

Bir veri yapısında karma oluşturma , iki adımlı bir işlemdir.

1. Karma işlevi, öğeyi küçük bir tam sayıya veya karma değere dönüştürür. Bu tam sayı, orijinal verileri depolamak için bir dizin olarak kullanılır.
2. Verileri bir hash tablosunda saklar. Verileri hızlı bir şekilde bulmak için bir karma anahtar kullanabilirsiniz.

Veri Yapısında Hashing Örnekleri

Aşağıdakiler , veri yapısındaki karma işlemin gerçek hayattan örnekleridir :

• Okullarda öğretmen, her öğrenciye benzersiz bir rulo numarası atar. Daha sonra öğretmen, o öğrenci hakkında bilgi almak için bu rulo numarasını kullanır.
• Bir kütüphanede sonsuz sayıda kitap vardır. Kütüphaneci her kitaba benzersiz bir numara atar. Bu benzersiz numara, kitapların kitaplıktaki konumunu belirlemeye yardımcı olur.

Ödeme: Veri Yapısında Sıralama

Özet fonksiyonu

Bir veri yapısındaki karma işlevi, rastgele boyuttaki verileri sabit boyutlu verilere eşler. Şu değerleri döndürür: küçük bir tamsayı değeri (karma değeri olarak da bilinir), karma kodları ve karma toplamları.

hash = hashfunc(anahtar)

dizin = karma % dizi_boyutu

has işlevi aşağıdaki gereksinimleri karşılamalıdır:

• İyi bir hash fonksiyonunun hesaplanması kolaydır.
• İyi bir karma işlevi, kümelemede asla takılıp kalmaz ve anahtarları karma tablosunda eşit olarak dağıtır.
• İyi bir karma işlevi, iki öğe veya öğe aynı karma değerine atandığında çarpışmayı önler.

Hash Tablosu

Veri yapısındaki karma, anahtar/değer çiftlerini depolamak için karma tabloları kullanır. Hash tablosu daha sonra bir indeks oluşturmak için hash fonksiyonunu kullanır. Hashing, ekleme, güncelleme ve arama işlemlerini gerçekleştirmek için bu benzersiz dizini kullanır.

Veri Yapısında Hashing Nasıl Çalışır?

Karma işleminde, karma işlevi dizeleri veya sayıları küçük bir tamsayı değerine eşler. Karma tabloları, bir karma işlevi kullanarak öğeyi listeden alır. Karma tekniğinin amacı, verileri bir dizi boyunca eşit olarak dağıtmaktır. Hashing, tüm öğelere benzersiz bir anahtar atar. Hash tablosu, listedeki verilere erişmek için bu anahtarı kullanır.

Hash tablosu, verileri bir anahtar/değer çiftinde saklar. Anahtar, karma işlevine bir girdi görevi görür. Karma işlevi daha sonra depolanan her değer için benzersiz bir dizin numarası üretir. Dizin numarası, o anahtara karşılık gelen değeri tutar. Hash işlevi, çıktı olarak küçük bir tamsayı değeri döndürür. Hash fonksiyonunun çıktısına hash değeri denir.

Bir örnekle bir veri yapısındaki hash'i anlayalım . 30 hücreli bir karma tablosunda bazı öğeleri (anahtar/değer çiftinde düzenlenmiş) saklamanız gerektiğini düşünün.

Değerler: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

Hash tablosu aşağıdaki gibi görünecektir:

Ayrıca Okuyun: Python'da Veri Yapısı Türleri

Çarpışma Çözme Teknikleri

Hash tablosunda iki tuşa aynı indeks numarası atanırsa, veri yapısındaki hashing bir çarpışmaya girer. Çarpışma bir problem yaratır çünkü bir hash tablosundaki her indeksin sadece bir değeri saklaması beklenir. Veri yapısındaki karma, bir karma tablosunun performansını yönetmek için birkaç çarpışma çözümleme tekniği kullanır.

Doğrusal Sondalama

Veri yapısındaki karma , zaten bir değeri depolamak için kullanılan bir dizi dizini ile sonuçlanır. Böyle bir durumda, karma bir arama işlemi gerçekleştirir ve sonraki boş hücreyi doğrusal olarak araştırır.

Doğrusal Sondalama Örneği

Bazı öğeleri 30 boyutunda bir karma tablosunda saklamanızın istendiğini düşünün. Öğeler zaten bir anahtar/değer çifti biçiminde sıralanmıştır. Verilen değerler: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

Hash(n), bir hash fonksiyonu kullanılarak hesaplanan indekstir ve T, tablo boyutudur. Slot indeksi = ( hash(n) % T) doluysa, 1 ((hash(n) + 1) % T ekleyerek sonraki slot indeksini ararız. Eğer (hash(n) + 1) % T de doluysa, o zaman (hash(n) + 2) % T'yi deneriz. Eğer (hash(n) + 2) % T de doluysa, o zaman deneriz (hash( n) + 3) %T.

Hash tablosu aşağıdaki gibi görünecektir:

Çift Karma

Çift hash tekniği iki hash fonksiyonu kullanır. İkinci karma işlevi, birinci işlev bir çarpışmaya neden olduğunda kullanıma girer. Değeri saklamak için bir ofset indeksi sağlar.

Çift karma tekniğinin formülü aşağıdaki gibidir:

(firstHash(anahtar) + i * secondHash(anahtar)) % sizeOfTable

i ofset değeridir. Bu ofset değeri, boş bir yuva bulana kadar artmaya devam eder.

Örneğin, iki hash fonksiyonunuz var: h1 ve h2. Boş bir yuva bulmak için aşağıdaki adımları gerçekleştirmelisiniz:

1. hash1(key) öğesinin boş olup olmadığını doğrulayın. Evet ise, değeri bu yuvaya kaydedin.
2. hash1(key) boş değilse, hash2(key) kullanarak başka bir yuva bulun.
3. hash1(key) + hash2(key) öğesinin boş olup olmadığını doğrulayın. Evet ise, değeri bu yuvaya kaydedin.
4. Sayacı artırmaya devam edin ve boş bir yuva bulana kadar hash1(key)+2hash2(key), hash1(key)+3hash2(key) vb. ile tekrarlayın.

Çift Karma Örneği

20 boyutunda bir hash tablosunda bazı öğeleri saklamanız gerektiğini düşünün. Verilen değerler: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) mod 20

Çözüm

Double hashing yüksek bir hesaplama maliyetine sahiptir, ancak bir sonraki boş slotu lineer problama yönteminden daha hızlı arar. Makalede verilen örnekler sadece açıklama amaçlıdır. Yukarıda verilen ifadeleri ihtiyaçlarınıza göre değiştirebilirsiniz. Bu blogda, veri yapısındaki karma kavramını öğrendik .

Veri yapısı bilginizi güçlendirmek için örneği deneyebilirsiniz. Veri yapısı hakkında daha fazla bilgi edinmek istiyorsanız , Tam Yığın Geliştirme kursundaki upGrad Yönetici PG Programına göz atın . Bu kurs, çalışan profesyoneller için tasarlanmıştır ve en iyi şirketlerle sıkı eğitim ve işe yerleştirme sunar.