Thread: 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

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

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());
}

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;
}

Just for interest what book are using?

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