Hash Table

Kategori: C , 04 Temmuz 2019 , JanFranco


Hash tablosu, veriye bir anahtar (key) yardımı ile erişilen basit bir dizi üzerine inşa edilmiştir. Bir veriyi depolayacağımızda, sadece veriyi değil, verinin yanında bir de key değeri göndeririz. Bu key değerini bir hash fonksiyonuna göndeririz ve dönen değer ile veri yapısında saklanır. Bu veri yapısını implemente edelim. İlk olarak main fonksiyonun dışında, global olarak bir dizi açalım. Dizinin yanında bir de kullanıcı veri ekledikçe değeri artan userSize adında bir değişken tanımlayalım. Bunu yapmamızın sebebi hash table dolunca daha fazla verinin gönderilmesini engellemek:


int hashArray[SIZE];
int userSize = 0;
Verilerin hangi indexte saklanacağını belirleyen bir hash fonksiyonu yazalım. Bu fonksiyon gönderilen key değerinin, dizinin boyutuna göre modunu alacak ve geri döndürecek. Burada daha farklı denklemler de kullanabilirdik:

int hash_code(int key){
    return key % SIZE;
}
Dizinin tüm elemanlarını -1 yapacak bir fonksiyon yazalım. -1 değeri bizim için hash table'ın boş olup olmadığını söyleyecek.

void init(){
    int i;

    for(i=0; i<SIZE; i++){
        hashArray[i] = -1;
    }
}
Hash table'a veri ekleyecek bir fonksiyon yazalım. Fonksiyon parametre olarak bir key değeri bir de value değeri alacak. Fonksiyonda ilk olarak userSize kontrolü yapıyoruz. Eğer userSize dizinin boyutunu aşmışsa daha fazla veri eklenmesini engelliyoruz. Daha sonra key değerini hash fonksiyonuna gönderiyoruz ve geri dönen değeri index kabul ederek, indexe veriyi ekliyoruz. Veri ekleme işlemini -1 değerine göre yapıyoruz. Eğer o indexteki değer -1 ise veri ekliyoruz. Değilse indexi bir artırıyoruz ve hash fonksiyonuna gönderiyoruz. Geri dönen değeri index kabul ediyoruz. indexi bir artırmak zorunda değildik, farklı yöntemler de mevcut. Veri ekledikten sonra da userSize değerini bir artırıyoruz:

void insert(int key, int value){

    if(userSize >= SIZE){
        printf("hashArray is full!\n");
    }
    else{
        int index = hash_code(key);

        while(hashArray[index] != -1){
            index = hash_code(index + 1);
        }

        hashArray[index] = value;
        userSize++;
    }
}
Hash table'ı konsola bastıran bir fonksiyon yazalım. Eğer hash table'daki değer -1 ise "~~" karakterlerini ekrana bastıralım, -1 değil ise yani doluysa o indeteki değeri bastıralım:

void display(){
    int i;

    for(i=0; i<SIZE; i++){
        if(hashArray[i] != -1){
            printf("%d.  VALUE = %d\n", i, hashArray[i]);
        }
        else{
            printf("%d.  VALUE = ~~\n", i);
        }
    }
}
Parametre olarak verdiğimiz değeri hash table'da arayacak bir fonksiyon yazalım. Eğer değer table'da mevcutsa o değerin konumunu, değilse -1 değerini döndürecek:

int search(int value){
    int i;

    for(i=0; i<SIZE; i++){
        if(hashArray[i] == value){
            return i;
        }
    }

    return -1;
}
Parametre olarak verdiğimiz değeri hash table'dan silecek bir fonksiyon yazalım. İlk olarak değeri hash table'da arıyoruz ve bulursak değeri -1 olarak değiştiriyoruz. -1 değeri bizim için orada değer yok demek idi:

int del(int value){
    int i;

    for(i=0; i<SIZE; i++){
        if(hashArray[i] == value){
            hashArray[i] = -1;
            userSize--;
            return 1;
        }
    }

    return -1;
}
init() fonksiyonu ile başlayarak fonksiyonları kullanalım:

int main() {

    int i;
    init();

    for(i=0; i<SIZE; i++){
        insert(rand() % 10, i);
    }

    display();
    printf("--------------------\n");
    int result = search(3);
    if(result != -1){
        printf("%d is found at %d\n", 3, result);
    }
    else{
        printf("Not found\n");
    }
    printf("--------------------\n");
    del(7);
    insert(1, 12);
    display();

    return 0;
}
Tüm kodları bütün olarak verelim:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

int hashArray[SIZE];
int userSize = 0;

int hash_code(int key){
    return key % SIZE;
}

void init(){
    int i;

    for(i=0; i<SIZE; i++){
        hashArray[i] = -1;
    }
}

void insert(int key, int value){

    if(userSize >= SIZE){
        printf("hashArray is full!\n");
    }
    else{
        int index = hash_code(key);

        while(hashArray[index] != -1){
            index = hash_code(index + 1);
        }

        hashArray[index] = value;
        userSize++;
    }
}

void display(){
    int i;

    for(i=0; i<SIZE; i++){
        if(hashArray[i] != -1){
            printf("%d.  VALUE = %d\n", i, hashArray[i]);
        }
        else{
            printf("%d.  VALUE = ~~\n", i);
        }
    }
}

int search(int value){
    int i;

    for(i=0; i<SIZE; i++){
        if(hashArray[i] == value){
            return i;
        }
    }

    return -1;
}

int del(int value){
    int i;

    for(i=0; i<SIZE; i++){
        if(hashArray[i] == value){
            hashArray[i] = -1;
            userSize--;
            return 1;
        }
    }

    return -1;
}

int main() {

    int i;
    init();

    for(i=0; i<SIZE; i++){
        insert(rand() % 10, i);
    }

    display();
    printf("--------------------\n");
    int result = search(3);
    if(result != -1){
        printf("%d is found at %d\n", 3, result);
    }
    else{
        printf("Not found\n");
    }
    printf("--------------------\n");
    del(7);
    insert(1, 12);
    display();

    return 0;
}
Output>>

0.  VALUE = 3
1.  VALUE = 0
2.  VALUE = 7
3.  VALUE = 8
4.  VALUE = 2
5.  VALUE = 5
6.  VALUE = 9
7.  VALUE = 1
8.  VALUE = 6
9.  VALUE = 4
--------------------
3 is found at 0
--------------------
0.  VALUE = 3
1.  VALUE = 0
2.  VALUE = 12
3.  VALUE = 8
4.  VALUE = 2
5.  VALUE = 5
6.  VALUE = 9
7.  VALUE = 1
8.  VALUE = 6
9.  VALUE = 4


Sonraki Yazı: Hash Table with Struct
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın