TechCodeview

Veri Yapısında Hashing'e Giriş:

Karma, bilgisayar bilimlerinde büyük veri kümelerinin sabit uzunluklu değerlerle eşlenmesini içeren popüler bir tekniktir. Değişken büyüklükteki bir veri setini sabit büyüklükte bir veri setine dönüştürme işlemidir. Etkili arama işlemlerini gerçekleştirme yeteneği, karma oluşturmayı veri yapılarında önemli bir kavram haline getirir.

Hashing nedir?

Bir girişi (bir dize veya tamsayı gibi) sabit boyutlu bir çıktıya (karma kodu veya karma değeri olarak adlandırılır) dönüştürmek için bir karma algoritması kullanılır. Veriler daha sonra bu karma değerini bir dizide veya karma tablosunda bir dizin olarak kullanarak saklanır ve alınır. Karma işlevi deterministik olmalıdır; bu, belirli bir girdi için her zaman aynı sonucu vereceğini garanti eder.

Hashing genellikle bir veri parçası için benzersiz bir tanımlayıcı oluşturmak amacıyla kullanılır; bu tanımlayıcı, bu veriyi büyük bir veri kümesinde hızlı bir şekilde aramak için kullanılabilir. Örneğin, bir web tarayıcısı, web sitesi şifrelerini güvenli bir şekilde saklamak için karma yöntemini kullanabilir. Bir kullanıcı şifresini girdiğinde, tarayıcı bunu bir hash değerine dönüştürür ve kullanıcının kimliğini doğrulamak için bunu saklanan hash değeriyle karşılaştırır.

Hash Anahtarı nedir?

Karma bağlamında, karma anahtarı (karma değeri veya karma kodu olarak da bilinir), karma algoritması tarafından oluşturulan sabit boyutlu bir sayısal veya alfasayısal temsildir. Karma olarak bilinen bir işlem yoluyla, bir metin dizesi veya bir dosya gibi giriş verilerinden türetilir.

Hashing, girdinin boyutuna bakılmaksızın tipik olarak sabit uzunlukta benzersiz bir karma anahtarı üreten, girdi verilerine belirli bir matematiksel fonksiyonun uygulanmasını içerir. Ortaya çıkan hash anahtarı aslında orijinal verinin dijital parmak izidir.

Hash anahtarı çeşitli amaçlara hizmet eder. Giriş verilerindeki küçük bir değişiklik bile önemli ölçüde farklı bir karma anahtarı üreteceğinden, genellikle veri bütünlüğü kontrolleri için kullanılır. Hash anahtarları aynı zamanda hızlı arama ve karşılaştırma işlemlerine izin verdikleri için hash tablolarında veya veri yapılarında etkili veri alımı ve depolama için de kullanılır.

Hashing Nasıl Çalışır?

Karma işlemi üç adıma ayrılabilir:

• Giriş: Hash edilecek veriler karma algoritmasına girilir.
• Karma İşlevi: Karma algoritması giriş verilerini alır ve sabit boyutlu bir karma değeri oluşturmak için matematiksel bir işlev uygular. Hash fonksiyonu, farklı girdi değerlerinin farklı hash değerleri üreteceği ve girdideki küçük değişikliklerin çıktıda büyük değişiklikler yaratacağı şekilde tasarlanmalıdır.
• Çıktı: Veri yapısında veri depolamak veya almak için dizin olarak kullanılan karma değeri döndürülür.

Karma Algoritmalar:

Her birinin farklı avantajları ve dezavantajları olan çok sayıda karma algoritması vardır. En popüler algoritmalar aşağıdakileri içerir:

• MD5: 128 bitlik karma değeri üreten, yaygın olarak kullanılan bir karma algoritması.
• SHA-1: 160 bitlik karma değeri üreten popüler bir karma algoritması.
• SHA-256: 256 bit karma değeri üreten daha güvenli bir karma algoritması.

Özet fonksiyonu:

Karma İşlevi: Karma işlevi, bir girişi (veya anahtarı) alan ve karma kodu veya karma değeri olarak bilinen sabit boyutlu bir sonucu çıkaran bir tür matematiksel işlemdir. Hash fonksiyonunun deterministik olabilmesi için her zaman aynı girdi için aynı hash kodunu vermesi gerekir. Ek olarak, karma işlevi, her giriş için karma özelliği olarak bilinen benzersiz bir karma kodu üretmelidir.

Aşağıdakiler de dahil olmak üzere farklı türde karma işlevleri vardır:

Bölme yöntemi:

Bu yöntem, anahtarın tablo boyutuna bölünmesini ve geri kalanının karma değeri olarak alınmasını içerir. Örneğin tablo boyutu 10 ve anahtar 23 ise hash değeri 3 olacaktır (%23 10 = 3).

Çarpma yöntemi:

Bu yöntem, anahtarın bir sabitle çarpılmasını ve ürünün kesirli kısmının hash değeri olarak alınmasını içerir. Örneğin, anahtar 23 ve sabit 0,618 ise karma değeri 2 olacaktır (taban(10*(0,61823 - kat(0,61823)))) = kat(2,236) = 2).

Evrensel karma:

Bu yöntem, karma fonksiyonları ailesinden rastgele bir karma fonksiyonunun kullanılmasını içerir. Bu, karma fonksiyonunun herhangi bir belirli girdiye karşı önyargılı olmamasını ve saldırılara karşı dayanıklı olmasını sağlar.

Çarpışma Çözünürlüğü

Hashing'deki ana zorluklardan biri, iki veya daha fazla girdi değerinin aynı hash değerini ürettiğinde meydana gelen çarpışmaların üstesinden gelmektir. Aşağıdakiler de dahil olmak üzere çarpışmaları çözmek için kullanılan çeşitli teknikler vardır:

10 / 60

• Zincirleme: Bu teknikte, her karma tablosu yuvası aynı karma değerine sahip tüm değerlerin bağlantılı bir listesini içerir. Bu tekniğin uygulanması basit ve kolaydır, ancak bağlantılı listeler çok uzun olduğunda performansın düşmesine neden olabilir.
• Açık adresleme: Bu teknikte, bir çarpışma meydana geldiğinde algoritma, boş bir yuva bulunana kadar ardışık yuvaları inceleyerek karma tablosunda boş bir yuva arar. Bu teknik, yük faktörü düşük olduğunda zincirlemeye göre daha verimli olabilir ancak yük faktörü yüksek olduğunda kümelenmeye ve düşük performansa yol açabilir.
• Çift karma: Bu, bir çarpışma meydana geldiğinde araştırılacak bir sonraki yuvayı belirlemek için ikinci bir karma işlevi kullanan açık adreslemenin bir çeşididir. Bu teknik, kümelenmeyi azaltmaya ve performansı artırmaya yardımcı olabilir.

Çarpışma Çözümü Örneği

Boyutu 5 olan hash tablosu örneğimizle devam edelim. 'John: 123456' ve 'Mary: 987654' anahtar/değer çiftlerini hash tablosunda depolamak istiyoruz. Her iki anahtar da aynı 4 karma kodunu üretir, böylece bir çarpışma meydana gelir.

Çarpışmayı çözmek için zincirlemeyi kullanabiliriz. Dizin 4'te bağlantılı bir liste oluşturup anahtar/değer çiftlerini listeye ekliyoruz. Hash tablosu artık şöyle görünüyor:

0:

1:

2:

3:

4: John: 123456 -> Meryem: 987654

5:

Hash Tablosu:

Karma tablosu, verileri bir dizide saklayan bir veri yapısıdır. Tipik olarak dizi için, karma tablosuna sığabilecek öğe sayısından daha büyük bir boyut seçilir. Bir anahtar, karma işlevi kullanılarak dizideki bir dizine eşlenir.

Hash işlevi, yeni bir öğe eklemek için karma tablosuna bir öğenin eklenmesi gereken dizini bulmak için kullanılır. Eğer bir çarpışma yoksa eleman bu indekse eklenir. Eğer bir çarpışma varsa, dizideki bir sonraki boş alanı bulmak için çarpışma çözümleme yöntemi kullanılır.

Hash işlevi, öğenin karma tablosundan alınması amacıyla saklandığı dizini bulmak için kullanılır. Öğe bu dizinde bulunamazsa, öğeyi bağlantılı listede (zincirleme kullanılıyorsa) veya bir sonraki kullanılabilir yuvada (açık adresleme kullanılıyorsa) aramak için çarpışma çözümleme yöntemi kullanılır.

Karma Tablo İşlemleri

Bir karma tablosunda gerçekleştirilebilecek çeşitli işlemler vardır:

• Ekleme: Karma tablosuna yeni bir anahtar/değer çifti ekleme.
• Silme: Bir anahtar/değer çiftinin karma tablosundan kaldırılması.
• Arama: Hash tablosunda bir anahtar/değer çifti aranıyor.

Hash Tablosu Oluşturma:

Hashing, hızlı veri ekleme, silme ve almayı sağlayan veri yapıları olan hash tablolarını oluşturmak için sıklıkla kullanılır. Bir karma tablosunu oluşturan paket dizilerinin her birinde bir veya daha fazla anahtar/değer çifti depolanabilir.

Bir karma tablosu oluşturmak için öncelikle her anahtarı dizideki benzersiz bir indeksle eşleştiren bir karma işlevi tanımlamamız gerekir. Basit bir karma işlevi, anahtardaki karakterlerin ASCII değerlerinin toplamını almak ve dizinin boyutuna bölündüğünde kalanı kullanmak olabilir. Ancak bu karma işlevi verimsizdir ve çarpışmalara (aynı dizine eşlenen iki anahtar) yol açabilir.

Çarpışmaları önlemek için, dizi boyunca karma değerlerinin daha eşit dağılımını sağlayan daha gelişmiş karma işlevlerini kullanabiliriz. Popüler algoritmalardan biri, karma değeri oluşturmak için bit düzeyinde işlemleri kullanan djb2 karma işlevidir:

 unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } 

Bu karma işlevi girdi olarak bir dize alır ve işaretsiz bir uzun tamsayı karma değeri döndürür. İşlev, 5381'lik bir karma değerini başlatır ve ardından yeni bir karma değeri oluşturmak için bit düzeyinde işlemleri kullanarak dizedeki her karakter üzerinde yinelenir. Nihai karma değeri döndürülür.

C++'da Karma Tablolar

C++'da standart kitaplık, unordered_map adı verilen bir karma tablo kapsayıcı sınıfı sağlar. unordered_map kapsayıcısı bir karma tablosu kullanılarak uygulanır ve anahtar/değer çiftlerine hızlı erişim sağlar. unordered_map kapsayıcısı, anahtarların karma kodunu hesaplamak için bir karma işlevi kullanır ve ardından çarpışmaları çözmek için açık adreslemeyi kullanır.

C++'da unordered_map kapsayıcısını kullanmak için başlık dosyasını eklemeniz gerekir. İşte C++'da unordered_map kapsayıcısının nasıl oluşturulacağına ilişkin bir örnek:

 #include #include int main() { // create an unordered_map container std::unordered_map my_map; // insert some key-value pairs into the map my_map['apple'] = 10; my_map['banana'] = 20; my_map['orange'] = 30; // print the value associated with the 'banana' key std::cout << my_map['banana'] << std::endl; return 0; } 

Açıklama:

• Bu program, C++'ta karma tablosu kullanılarak uygulanan ve anahtar/değer çiftlerine hızlı erişim sağlayan unordered_map kapsayıcısının kullanımını gösterir.
• İlk olarak, program gerekli başlık dosyalarını içerir: ve.
• Daha sonra program, dize anahtarları ve tamsayı değerlerine sahip, my_map adında boş bir sırasız_map kapsayıcısı oluşturur. Bu, std::unordered_map my_map; söz dizimi kullanılarak yapılır.
• Daha sonra program, [] operatörünü kullanarak my_map kapsayıcısına üç anahtar/değer çifti ekler: 10 değeriyle 'elma', 20 değeriyle 'muz' ve 30 değeriyle 'turuncu'.
• Bu, my_map['apple'] = 10;, my_map['muz'] = 20; ve my_map['turuncu'] = 30; söz dizimi kullanılarak yapılır. sırasıyla.
• Son olarak program, [] operatörünü ve std::cout nesnesini kullanarak 'muz' tuşuyla ilişkili değeri yazdırır.

Programın Çıkışı:

Karma Tabloya Veri Ekleme

Bir karma tablosuna bir anahtar/değer çifti eklemek için, öncelikle anahtar/değer çiftini saklayacak diziye bir dizin oluşturmamız gerekir. Başka bir anahtar aynı dizine eşleşirse, bir çarpışma olur ve bunu uygun şekilde ele almamız gerekir. Yaygın bir yöntem, dizideki her grubun aynı karma değerine sahip anahtar/değer çiftlerinin bağlantılı bir listesini içerdiği zincirlemeyi kullanmaktır.

Zincirleme kullanarak bir anahtar/değer çiftinin karma tablosuna nasıl ekleneceğine dair bir örnek:

 typedef struct node { char* key; int value; struct node* next; } node; node* hash_table[100]; void insert(char* key, int value) { unsigned long hash_value = hash(key) % 100; node* new_node = (node*) malloc(sizeof(node)); new_node->key = key; new_node->value = value; new_node->next = NULL; if (hash_table[hash_value] == NULL) { hash_table[hash_value] = new_node; } else { node* curr_node = hash_table[hash_value]; while (curr_node->next != NULL) { curr_node = curr_node->next; } curr_node->next = new_node; } } 

Açıklama:

Arraylist ve bağlantılı liste

• Öncelikle hash tablosunda tek bir düğümü temsil eden, node adı verilen yapı tanımlanır.
• Her düğümün üç üyesi vardır: anahtarı saklamak için bir char* anahtarı, ilişkili değeri saklamak için bir int değeri ve bağlantılı bir liste kullanarak karma tablosundaki çarpışmaları işlemek için yanında çağrılan başka bir düğüme yönelik bir işaretçi.
• Hash_table adı verilen bir düğüm işaretçileri dizisi 100 boyutunda bildirilir. Bu dizi, karma tablosunun öğelerini depolamak için kullanılacaktır.
• Insert işlevi parametre olarak bir char* anahtarını ve bir int değerini alır.
• Programın başka bir yerinde tanımlandığı varsayılan karma fonksiyonunu kullanarak verilen anahtar için karma değerinin hesaplanmasıyla başlar.
• Daha sonra hash değeri, % 100 modül operatörü kullanılarak hash_table dizisinin boyutuna sığacak şekilde azaltılır.
• Dinamik bellek ayırma (malloc(sizeof(node))) kullanılarak yeni bir düğüm oluşturulur ve üyelerine (anahtar, değer ve sonraki) sırasıyla sağlanan anahtar, değer ve NULL ile atanır.
• Hash_table dizisindeki karşılık gelen yuva boşsa (NULL), bu da hiçbir çarpışmanın meydana gelmediğini gösterirse, yeni düğüm doğrudan o yuvaya atanır (hash_table[hash_value] = new_node).

Bununla birlikte, hash_table dizisindeki bu dizinde zaten bir düğüm mevcutsa, işlevin çarpışmayı işlemesi gerekir. Geçerli düğümden (hash_table[hash_value]) başlayarak bağlantılı listeyi geçer ve sonuna ulaşana kadar bir sonraki düğüme (curr_node->next != NULL) gider. Listenin sonuna ulaşıldığında, yeni düğüm bir sonraki düğüm olarak eklenir (curr_node->next = new_node).

Hashing'in C++'da Uygulanması:

Çarpışma çözümü için açık adresleme ve doğrusal araştırma kullanan C++'da karma işleminin bir uygulamasını görelim. Tamsayıları saklayan bir hash tablosu uygulayacağız.

 #include using namespace std; const int SIZE = 10; class HashTable { private: int arr[SIZE]; public: HashTable() { for (int i = 0; i <size; i++) { arr[i]="-1;" } int hashfunction(int key) return key % size; void insert(int index="hashFunction(key);" i="0;" while (arr[(index + i) size] !="-1" && arr[(index i++; if cout << 'element already exists in the hash table' endl; else remove(int deleted from return; not found display() for (int < (arr[i]="=" -1 || -2) continue; 'index ' ': }; main() hashtable ht; ht.insert(5); ht.insert(15); ht.insert(25); ht.insert(35); ht.insert(45); ht.display(); ht.remove(15); ht.remove(10); ht.insert(55); 0; pre> <p> <strong>Explanation:</strong> </p> <ul> <li>This program implements a hash table data structure using linear probing to handle collisions.</li> <li>A hash table is a data structure that stores data in key-value pairs, where the keys are hashed using a hash function to generate an index in an array. This allows for constant-time average-case complexity for inserting, searching, and deleting elements from the hash table.</li> <li>The HashTable class has a private integer array arr of size SIZE, which is initialized to -1 in the constructor. The hash function method takes an integer key and returns the hash value of the key, which is simply the remainder of the key when divided by SIZE.</li> <li>The insert method takes an integer key and uses the hash function to get the index where the key should be inserted.</li> <li>If the index is already occupied by another key, linear probing is used to find the next available index in the array. Linear probing checks the next index in the array until it finds an empty slot or the key itself.</li> <li>If the key is already in the hash table, the method displays a message saying that the element already exists. Otherwise, it inserts the key at the calculated index.</li> <li>The remove method takes an integer key and uses the hash function to get the index where the key is located.</li> <li>If the key is not in the calculated index, linear probing is used to search for the key in the next indices in the array. Once the key is found, it is deleted by setting its value to -2.</li> <li>If the key is not found in the hash table, the method displays a message saying that the element is not found.</li> <li>The display method simply iterates through the array and prints out all non-empty key-value pairs.</li> <li>In the main function, an instance of the HashTable class is created, and several integers are inserted into the hash table using the insert method.</li> <li>Then, the display method is called to show the contents of the hash table. The remove method is called twice, first to remove an element that exists in the hash table and then to remove an element that does not exist.</li> <li>The display method is called after each remove method call to show the updated contents of the hash table.</li> <li>Finally, another integer is inserted into the hash table, and the display method is called again to show the final contents of the hash table.</li> </ul> <p> <strong>Program Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/hashing-data-structure-3.webp" alt="Hashing in Data Structure"> <h2>Applications of Hashing</h2> <p>Hashing has many applications in computer science, including:</p> <ul> <li>Databases: Hashing is used to index and search large databases efficiently.</li> <li>Cryptography: Hash functions are used to generate message digests, which are used to verify the integrity of data and protect against tampering.</li> <li>Caching: Hash tables are used in caching systems to store frequently accessed data and improve performance.</li> <li>Spell checking: Hashing is used in spell checkers to quickly search for words in a dictionary.</li> <li>Network routing: Hashing is used in load balancing and routing algorithms to distribute network traffic across multiple servers.</li> </ul> <h2>Advantages of Hashing:</h2> <ul> <li>Fast Access: Hashing provides constant time access to data, making it faster than other data structures like linked lists and arrays.</li> <li>Efficient Search: Hashing allows for quick search operations, making it an ideal data structure for applications that require frequent search operations.</li> <li>Space-Efficient: Hashing can be more space-efficient than other data structures, as it only requires a fixed amount of memory to store the hash table.</li> </ul> <h2>Limitations of Hashing:</h2> <ul> <li>Hash Collisions: Hashing can produce the same hash value for different keys, leading to hash collisions. To handle collisions, we need to use collision resolution techniques like chaining or open addressing.</li> <li>Hash Function Quality: The quality of the hash function determines the efficiency of the hashing algorithm. A poor-quality hash function can lead to more collisions, reducing the performance of the hashing algorithm.</li> </ul> <h2>Conclusion:</h2> <p>In conclusion, hashing is a widely used technique in a data structure that provides efficient access to data. It involves mapping a large amount of data to a smaller hash table using a hash function, which reduces the amount of time needed to search for specific data elements. The hash function ensures that data is stored in a unique location within the hash table and allows for easy retrieval of data when needed.</p> <p>Hashing has several advantages over other data structure techniques, such as faster retrieval times, efficient use of memory, and reduced collisions due to the use of a good hash function. However, it also has some limitations, including the possibility of hash collisions and the need for a good hash function that can distribute data evenly across the hash table.</p> <p>Overall, hashing is a powerful technique that is used in many applications, including database indexing, spell-checking, and password storage. By using a good hash function and implementing appropriate collision resolution techniques, developers can optimize the performance of their applications and provide users with a seamless experience.</p> <hr></size;>