Hash Tablosu

Bu eğitimde, karma tablonun ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da karma tablo işlemlerinin çalışan örneklerini bulacaksınız.

Karma tablosu, verileri anahtar / değer çiftleri biçiminde temsil eden bir veri yapısıdır . Her anahtar, karma tablodaki bir değere eşlenir. Anahtarlar, değerleri / verileri indekslemek için kullanılır. İlişkili bir dizi tarafından benzer bir yaklaşım uygulanır.

Veriler, aşağıdaki şekilde gösterildiği gibi anahtarların yardımıyla bir anahtar değer çiftinde temsil edilir. Her veri bir anahtarla ilişkilendirilir. Anahtar, verilere işaret eden bir tamsayıdır.

1. Doğrudan Adres Tablosu

Doğrudan adres tablosu, tablonun kullandığı alan miktarı program için bir sorun oluşturmadığında kullanılır. Burada varsayıyoruz ki

  • anahtarlar küçük tam sayılardır
  • anahtarların sayısı çok büyük değil ve
  • iki verinin aynı anahtara sahip olmaması

Evren adı verilen bir tamsayı havuzu alınır U = (0, 1,… ., n-1).
Doğrudan adres tablosunun her yuvası T(0… n-1), verilere karşılık gelen öğeye bir işaretçi içerir.
Dizinin indeksi Tanahtarın kendisidir ve içeriği Tkümeye bir göstericidir (key, element). Bir anahtar için öğe yoksa, o halde bırakılır NULL.

Bazen anahtarın kendisi verilerdir.

İşlemler için sözde kod

 directAddressSearch(T, k) return T(k) directAddressInsert(T, x) T(x.key) = x directAddressDelete(T, x) T(x.key) = NIL

Doğrudan Adres Tablosunun Sınırlamaları

  • Anahtarın değeri küçük olmalıdır.
  • Bir dizinin boyut sınırını aşmaması için anahtarların sayısı yeterince küçük olmalıdır.

2. Karma Tablosu

Bir karma tablosunda, anahtarlar, gerekli öğeyle eşleşen yeni bir dizin oluşturmak için işlenir. Bu sürece hashing denir.

h(x)Bir hash fonksiyonu olalım ve kanahtar olalım .
h(k)hesaplanır ve eleman için bir dizin olarak kullanılır.

Karma Tablosunun Sınırlamaları

  • Aynı indeks birden fazla anahtar için hash fonksiyonu tarafından üretilirse, bu durumda çakışma ortaya çıkar. Bu duruma çarpışma denir.
    Bundan kaçınmak için uygun bir hash fonksiyonu seçilir. Ancak, tüm benzersiz anahtarları üretmek imkansızdır çünkü |U|>m. Bu nedenle, iyi bir hash fonksiyonu, çarpışmaları tamamen engellemeyebilir, ancak çarpışma sayısını azaltabilir.

Ancak, çarpışmayı çözmek için başka tekniklerimiz var.

Doğrudan adres tablosuna göre hash tablosunun avantajları:

Doğrudan adres tablosuyla ilgili ana sorunlar, dizinin boyutu ve bir anahtarın muhtemelen büyük değeridir. Karma işlevi dizin aralığını azaltır ve dolayısıyla dizinin boyutu da azalır.
Örneğin, If k = 9845648451321, then h(k) = 11(bazı hash işlevi kullanarak). Bu 9845648451321, dizinin indeksini sağlarken boşa harcanan belleği kaydetmeye yardımcı olur

Zincirleme ile çarpışma çözümü

Bu teknikte, bir karma işlevi birden çok öğe için aynı indeksi üretirse, bu öğeler çift bağlantılı bir liste kullanılarak aynı indekste saklanır.

Birden jfazla öğe için yuvaysa, öğe listesinin başına bir işaretçi içerir. Hiç öğe yoksa jiçerir NIL.

İşlemler için sözde kod

 chainedHashSearch(T, k) return T(h(k)) chainedHashInsert(T, x) T(h(x.key)) = x //insert at the head chainedHashDelete(T, x) T(h(x.key)) = NIL

Python, Java, C ve C ++ Uygulaması

Python Java C C ++ 
 # Python program to demonstrate working of HashTable hashTable = ((),) * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable(index) = (key, data) def removeData(key): index = hashFunction(key) hashTable(index) = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 
 // Java program to demonstrate working of HashTable import java.util.*; class HashTable ( public static void main(String args()) ( Hashtable ht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); ) ) 
 // Implementing hash table in C #include #include struct set ( int key; int data; ); struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) ( return (key % capacity); ) int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i < n / 2; i++) ( if (n % i == 0) ( return 0; ) ) return 1; ) int getPrime(int n) ( if (n % 2 == 0) ( n++; ) while (!checkPrime(n)) ( n += 2; ) return n; ) void init_array() ( capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) ( array(i).key = 0; array(i).data = 0; ) ) void insert(int key, int data) ( int index = hashFunction(key); if (array(index).data == 0) ( array(index).key = key; array(index).data = data; size++; printf(" Key (%d) has been inserted ", key); ) else if (array(index).key == key) ( array(index).data = data; ) else ( printf(" Collision occured "); ) ) void remove_element(int key) ( int index = hashFunction(key); if (array(index).data == 0) ( printf(" This key does not exist "); ) else ( array(index).key = 0; array(index).data = 0; size--; printf(" Key (%d) has been removed ", key); ) ) void display() ( int i; for (i = 0; i < capacity; i++) ( if (array(i).data == 0) ( printf(" array(%d): / ", i); ) else ( printf(" key: %d array(%d): %d ", array(i).key, i, array(i).data); ) ) ) int size_of_hashtable() ( return size; ) int main() ( int choice, key, data, n; int c = 0; init_array(); do ( printf("1.Insert item in the Hash Table" "2.Remove item from the Hash Table" "3.Check the size of Hash Table" "4.Display a Hash Table" " Please enter your choice: "); scanf("%d", &choice); switch (choice) ( case 1: printf("Enter key -: "); scanf("%d", &key); printf("Enter data -: "); scanf("%d", &data); insert(key, data); break; case 2: printf("Enter the key to delete-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Size of Hash Table is-:%d", n); break; case 4: display(); break; default: printf("Invalid Input"); ) printf("Do you want to continue (press 1 for yes): "); scanf("%d", &c); ) while (c == 1); )
 // Implementing hash table in C++ #include #include using namespace std; class HashTable ( int capacity; list *table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i  capacity = size; table = new list(capacity); ) void HashTable::insertItem(int key, int data) ( int index = hashFunction(key); table(index).push_back(data); ) void HashTable::deleteItem(int key) ( int index = hashFunction(key); list::iterator i; for (i = table(index).begin(); i != table(index).end(); i++) ( if (*i == key) break; ) if (i != table(index).end()) table(index).erase(i); ) void HashTable::displayHash() ( for (int i = 0; i < capacity; i++) ( cout << "table(" << i << ")"; for (auto x : table(i)) cout < " << x; cout << endl; ) ) int main() ( int key() = (231, 321, 212, 321, 433, 262); int data() = (123, 432, 523, 43, 423, 111); int size = sizeof(key) / sizeof(key(0)); HashTable h(size); for (int i = 0; i < n; i++) h.insertItem(key(i), data(i)); h.deleteItem(12); h.displayHash(); )

İyi Karma İşlevleri

İyi bir hash fonksiyonu aşağıdaki özelliklere sahiptir.

  1. Çok büyük anahtarlar oluşturmamalıdır ve kova alanı küçüktür. Uzay boşa gitti.
  2. Oluşturulan anahtarlar ne çok yakın ne de çok uzak olmalıdır.
  3. Çarpışma olabildiğince en aza indirilmelidir.

Hashing için kullanılan yöntemlerden bazıları şunlardır:

Bölme Yöntemi

Eğer kbir anahtardır ve mkarma tablosu boyutu, hızlı arama fonksiyonu h()şu şekilde hesaplanır:

h(k) = k mod m

Örneğin, bir hash tablosunun boyutu 10ve k = 112ardından h(k) = 112mod ise 10 = 2. Değeri m, gücünün gücü olmamalıdır 2. Bunun nedeni 2ikilik formattaki güçlerin olmasıdır 10, 100, 1000,… . Bulduğumuzda k mod m, her zaman düşük mertebeden p-bitlerini alacağız.

 if m = 22, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 01 if m = 23, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 001 if m = 24, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 0001 if m = 2p, then h(k) = p lower bits of m

Multiplication Method

h(k) = ⌊m(kA mod 1)⌋
where,

  • kA mod 1 gives the fractional part kA,
  • ⌊ ⌋ gives the floor value
  • A is any constant. The value of A lies between 0 and 1. But, an optimal choice will be ≈ (√5-1)/2 suggested by Knuth.

Universal Hashing

In Universal hashing, the hash function is chosen at random independent of keys.

Open Addressing

Multiple values can be stored in a single slot in a normal hash table.

By using open addressing, each slot is either filled with a single key or left NIL. All the elements are stored in the hash table itself.

Unlike chaining, multiple elements cannot be fit into the same slot.

Open addressing is basically a collision resolving technique. Some of the methods used by open addressing are:

Linear Probing

In linear probing, collision is resolved by checking the next slot.
h(k, i) = (h'(k) + i) mod m
where,

  • i = (0, 1,… .)
  • h'(k) is a new hash function

If a collision occurs at h(k, 0), then h(k, 1) is checked. In this way, the value of i is incremented linearly.
The problem with linear probing is that a cluster of adjacent slots is filled. When inserting a new element, the entire cluster must be traversed. This adds to the time required to perform operations on the hash table.

Quadratic Probing

In quadratic probing, the spacing between the slots is increased (greater than one) by using the following relation.
h(k, i) = (h'(k) + c1i + c2i2) mod m
where,

  • c1ve pozitif yardımcı sabitlerdir,c2
  • i = (0, 1,… .)

Çift hashing

Bir hash fonksiyonu uygulandıktan sonra bir çarpışma meydana gelirse h(k), bir sonraki slotu bulmak için başka bir hash fonksiyonu hesaplanır.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash Tablo Uygulamaları

Karma tablolar nerede uygulanır

  • sabit zamanlı arama ve ekleme gereklidir
  • kriptografik uygulamalar
  • indeksleme verileri gerekli

Ilginç makaleler...