Bucket hashing

This is a discussion on Bucket hashing within the C Programming forums, part of the General Programming Boards category; Can anyone tell me where I can find the sample insert code for Bucket hashing? I cna't find in my ...

  1. #1
    Registered User
    Join Date
    Sep 2001
    Posts
    21

    Bucket hashing

    Can anyone tell me where I can find the sample insert code
    for Bucket hashing? I cna't find in my book, and i'm so mess up with hashing. thanx a lot

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    21
    well i wrote a insert hashing function by using array, but it doesn't work
    can anyone tell me whats wrong with it?

    Code:
    Data type and define:
    
    #define SLOT 3
    #define TableSize 256
    
    
    typedef struct
    {
    		char* slot[SLOT];
    }Bucket;
    
    
    typedef struct
    {
    	char identifier[MAXNAME];
    	bool found;
    	bool overflow;
    	Bucket bucket[TableSize];
    	int count;
    
    }Hash_tables;
    
    my function:
    
    bool hash_insert(Hash_tables ht,char* s)
    // Inserts string  in hash table, provided
    // no collision is found. This function must be
    // modified to handle collisions.
    {	
    	unsigned long int index;
    	
    	int overflow = 1, h=0;
    
    	if (! isfull(ht,s))
    	{	
    	//printf("%d %s\n", h, ht.bucket[index].slot[h]);
    
    		index = hash(s);
    		if (ht.bucket[index].slot[h] == NULL)
    		{
    				strcpy(ht.bucket[index].slot[h], s);
    		
    		}
    		else
    		{
    			++h;
    			strcpy(ht.bucket[index].slot[h], s);
    			if(strcmp(ht.bucket[index].slot[h-1], ht.bucket[index].slot[h])==0)
    			{
    				printf("Error!!Identifier %s is already in the table!!\n", s);
    				ht.bucket[index].slot[h]=NULL;
    				
    			}
    			else
    				if(h==3)
    				{
    					printf("Overflow!!\n");
    					ht.overflow=true;
    				}
    				else 
    					ht.overflow=false;
    		}
    	}
    	else
    		overflow=0;
    	return overflow ;
    }
    thanx in advance

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Try passing by reference rather than by value. Your hash table (the original, not the copy you're passing) is likely not getting updated because you're just passing it by value (ie: making a copy of it which is destroyed when the function ends)

    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Here's some code. It's in c++ though.


    Code:
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include <fstream>
    #include <string>
    using namespace std;
    
    const int TABLE_SIZE = 70951;
    
    struct Node {
        char* s;
        struct Node* next;
    };
    
    struct Hash_table {
        Node* buckets[TABLE_SIZE];
    };
    
    const char* word_list = "/usr/share/dict/words";
    
    
    int hash_string(const char* s, int tbl_size);
    void hash_init(Hash_table* h);
    void hash_insert(Hash_table* h, const char* s);
    Node* hash_find(Hash_table* h, const char* s); 
    void hash_destroy(Hash_table* h);
    void build_dictionary(Hash_table* h, const char* filename);
    
    int main(void)
    {
        Hash_table ht;
        string s;
    
        hash_init(&ht);
    
        build_dictionary(&ht, word_list);
        
        while(getline(cin, s)) {
            Node* n = hash_find(&ht, s.c_str());
            if (n != 0) 
                cout << n->s << " is in the dictionary" << endl;
            else 
                cout << "not in the dictionary" << endl;
        }
    
        hash_destroy(&ht);
    
        return 0;
    }
    
    
    int hash_string(const char* s, int tbl_size)
    {
        int r = 0;
    
        for (int i = 0; s[i] != '\0'; ++i) 
            r = 37 * r + s[i];
        
        r %= tbl_size;
    
        if (r < 0)
            r += tbl_size;
        return r;
    }
    
    void hash_init(Hash_table* h)
    {
        for (int i = 0; i < TABLE_SIZE; ++i)
            h->buckets[i] = 0;
    
    }
    
    void hash_insert(Hash_table* h, const char *s)
    {
        int hash_nr = hash_string(s, TABLE_SIZE);
        Node** lst = &h->buckets[hash_nr];
        Node* curr = *lst; 
        bool found = false;
    
    
        while(curr != 0 && !found) {
            if (!strcmp(curr->s, s))
                found = true; 
            curr = curr->next; 
        }
    
        // if not found insert at the beginning of the list 
        if (!found) {
            Node* tmp = new Node;
            tmp->s = new char[strlen(s) + 1];
            strcpy(tmp->s, s);
    
            tmp->next = *lst;
            *lst = tmp;
        }
    }
    
    Node* hash_find(Hash_table* h, const char* s)
    {
        int hash_nr = hash_string(s, TABLE_SIZE);
        Node* curr = h->buckets[hash_nr];
        Node* n = 0;
     
        while(curr != 0 && n == 0) {
            if (!strcmp(curr->s, s))
                n = curr;
            curr = curr->next;
        }
    
        return n;
    }
    
    void hash_destroy(Hash_table* h)
    {
        for (int i = 0; i < TABLE_SIZE; ++i) {
            Node* curr = h->buckets[i];
            Node* t;
            while(curr != 0) {
                t = curr->next;
                delete[] curr->s;
                delete curr;
                curr = t;
            }
        }
    }
    
    void build_dictionary(Hash_table* h, const char* filename)
    {
        ifstream inf(filename);
        string s;
    
        if (!inf) {
            cout << "file not found" << endl;
            exit(0);
        }
    
        while(getline(inf, s)) 
            hash_insert(h, s.c_str());
    }

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    21
    Originally posted by quzah
    Try passing by reference rather than by value. Your hash table (the original, not the copy you're passing) is likely not getting updated because you're just passing it by value (ie: making a copy of it which is destroyed when the function ends)

    Quzah.
    thanx Quzah, but can you give me an example of passing by reference ? And I put my whole code maybe you can figure out whats wwrong with it

    thanx in advance!

    Code:
    #include <ctype.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define bool int
    #define false 0
    #define true 1
    
    #define TERMINATE 666
    #define R 8
    #define MAXNAME 51
    #define SLOT 3
    #define TableSize 256
    
    typedef struct
    {
    		Char* slot[SLOT];
    }Bucket;
    
    
    typedef struct
    {
    	char identifier[MAXNAME];
    	bool found;
    	bool overflow;
    	Bucket bucket[TableSize];
    	int count;
    
    }Hash_tables;
    
    int GetData(Hash_tables, int *);
    unsigned long int hash(char* );
    unsigned long int mid_square(unsigned long int, char* );
    void hash_table_init(Hash_tables);
    bool isfull(Hash_tables, char* );
    bool hash_insert(Hash_tables ,char* );
    
    int main(void)
    {
    
    	int N;
    	int exit_control = 0;
    	Hash_tables table;
    	hash_table_init(table);
    	exit_control = GetData(table, &N);
    	if (exit_control != TERMINATE)
    		printf("something here\n");
    	
    }
    
    
    void hash_table_init(Hash_tables table)
    {
    	int i, j,k;
    	for (i=0; i <= TableSize; ++i)
    	{
    		for (j=0; j <= SLOT; ++j)
    			table.bucket[i].slot[j]=NULL;
    	}
    	for (k=0; k < MAXNAME; ++k)
    		table.identifier[k]=NULL;
    }
    
    int GetData(Hash_tables ht, int *N)
    {
    	FILE *in;
    	int return_value = 0, i=0;
    	char word[MAXNAME];
    	if ((in = fopen("p3.data","r")) == NULL)
    	{
    		printf("Error.  Master Data File does not exist.\n"
     				"Terminating Program.\n\n\n");
    		return_value = TERMINATE;  // no exit or return here!
    	}
    	else
    	{
    		while((fscanf(in, " %[^\n]", word))!=EOF)
    		{
    			
    			if(!hash_insert(ht, word))
    				printf("%s\n",word);
    				
    				i++;
    		}
    		*N=i;
    	}
    	fclose(in);
    	return return_value;
    }
    
    void printid(Hash_tables data, int N)
    {
    	int i;
    	
    	for(i=0;i<=N; i++)
    		printf("%s\n", data.identifier);
    }
    
    bool hash_insert(Hash_tables ht,char* s)
    {	
    	unsigned long int index;
    	
    	int overflow = 1, h=0;
    
    	if (! isfull(ht,s))
    	{	
    		index = hash(s);
    		if (ht.bucket[index].slot[h] == NULL)
    				strcpy(ht.bucket[index].slot[h], s);
    		else
    		{
    			++h;
    			strcpy(ht.bucket[index].slot[h], s);
    			if(strcmp(ht.bucket[index].slot[h-1], ht.bucket[index].slot[h])==0)
    			{
    				printf("Error!!Identifier %s is already in the table!!\n", s);
    				ht.bucket[index].slot[h]=NULL;
    				
    			}
    			else
    				if(h==3)
    				{
    					printf("Overflow!!\n");
    					ht.overflow=true;
    				}
    				else 
    					ht.overflow=false;
    		}
    	}
    	else
    		overflow=0;
    	printf("%s\n", ht.bucket[index].slot[h]);
    	return overflow ;
    }
    
    
    bool isfull(Hash_tables ht,char* s) 
    {
    	bool cond;
    	unsigned long int index;
    
    	
    	index = hash(s);
    	
    	if(ht.bucket[TableSize].slot[SLOT] != NULL)
    		cond = true;
    	else
    		cond =false;
    	return cond;
    		
    }
                 
    unsigned long int hash(char* s)
    {
    	unsigned long int sum = 0;
    	int i;
    	for (i=0; i < (int)strlen(s); ++i)
    	{
    		if(s[i]==' ' || s[i]==',')
    			sum-=' ';
    		sum += s[i];
    	}
    	return mid_square(sum*sum, s);
    }
    
    unsigned long int mid_square(unsigned long int sum_sq, char* s)
    {   
    	int len, left, right;
    	char str[33];
    	itoa(sum_sq,str,2);
    	len = (int)strlen(str);
    	if((len % 2) == 1)
    	{
    		right = (len - R)/2;
    		left = (len - R)/2 +1;
    	}
    	else
    		right = left = (len - R)/2;
    	sum_sq = (sum_sq >> right);
    	sum_sq = (sum_sq & 256);
    	return sum_sq;
    }

  6. #6
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    You insert should modify ht so you should pass ht
    as a pointer.

    Code:
    typedef struct
    {
           Char* slot[SLOT];
    }Bucket;
    This will require you to use malloc in insert but your
    code does not do this. Then to insert you would write something
    like
    Code:
            /* b is a bucket */
            int i = 0;
            while(i < SLOT && b.slot[i] != NULL)
                    i++;
            if (i < SLOT) {
                    b.slot[i] = malloc(strlen(s) + 1);
                    strcpy(b.slot[i], s);
            } else {
                    print_error();
                    exit(EXIT_FAILURE);
            }
    This way when you have a collision you insert one past
    the last insert.

    Code:
    void hash_table_init(Hash_tables table)
    {
    	int i, j,k;
    	for (i=0; i <= TableSize; ++i)
    	{
    		for (j=0; j <= SLOT; ++j)
    			table.bucket[i].slot[j]=NULL;
    	}
    	for (k=0; k < MAXNAME; ++k)
    		table.identifier[k]=NULL;
    }
    All of this code is wrong as you you go over the bounds on
    table.bucket[TableSize].slot[SLOT]

    TableSize should be uppercase for consistancy.

    Code:
    if (ht.bucket[index].slot[h] == NULL)
        strcpy(ht.bucket[index].slot[h], s);
    You check if it's = NULL and then copy a string into it?
    I think the whole function is wrong, you use the same h
    for each slot.

    Code:
    unsigned long int hash(char* s)
    {
    	unsigned long int sum = 0;
    	int i;
    	for (i=0; i < (int)strlen(s); ++i)
    	{
    		if(s[i]==' ' || s[i]==',')
    			sum-=' ';
    		sum += s[i];
    	}
    	return mid_square(sum*sum, s);
    }
    You call strlen for each charecter in a loop, which calls strlen
    strlen(s) + 1 times. Better is to check for the
    null charecter as all c style strings are terminated with '\0'.
    I have no clue if your hash function distributes the keys
    evenly, the one I used is simpler and was from a book.
    Last edited by Nick; 04-04-2002 at 02:07 PM.

  7. #7
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Just for interest what book are using?

  8. #8
    Registered User
    Join Date
    Sep 2001
    Posts
    21
    Originally posted by Nick
    Just for interest what book are using?
    Data Structures-A pseudocode Approach with c
    but there is no code inside, just algorithm

    And all i want to do is trying to make an 2d-array and store
    the elements into the row'th (bucket) and colum'th (slot)
    and it should be like:
    Code:
    slot                0             1            2              3
    --------          ---------------------------------------
    bucket  
    0                   AAA          BBB        CCC       DD
    1                   FFF          XXX        OO        KK
    2                   SSS          XYZ                  TT         
    .
    .
    .
    256                               QQ          PP
    thats why i'm using array, but i'm so mess up...
    thanx anyway

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Floating Exception (Core Dumped)
    By DarrenY in forum C Programming
    Replies: 9
    Last Post: 05-14-2007, 11:01 AM
  2. Creating Linked List Using Hashing and Stack
    By m0ntana in forum C Programming
    Replies: 2
    Last Post: 04-07-2007, 08:11 AM
  3. Insert Items in Hash Table Container.
    By joenching in forum C++ Programming
    Replies: 18
    Last Post: 05-02-2005, 02:50 PM
  4. Clearing Buffer
    By AndyBomstad in forum C++ Programming
    Replies: 11
    Last Post: 04-30-2005, 02:04 AM
  5. Double Hashing
    By carrja99 in forum C++ Programming
    Replies: 1
    Last Post: 03-28-2003, 08:36 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21