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
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?
thanx in advanceCode: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 ; }
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.
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()); }
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 itOriginally 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 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; }
You insert should modify ht so you should pass ht
as a pointer.
This will require you to use malloc in insert but yourCode:typedef struct { Char* slot[SLOT]; }Bucket;
code does not do this. Then to insert you would write something
like
This way when you have a collision you insert one pastCode:/* 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); }
the last insert.
All of this code is wrong as you you go over the bounds onCode: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; }
table.bucket[TableSize].slot[SLOT]
TableSize should be uppercase for consistancy.
You check if it's = NULL and then copy a string into it?Code:if (ht.bucket[index].slot[h] == NULL) strcpy(ht.bucket[index].slot[h], s);
I think the whole function is wrong, you use the same h
for each slot.
You call strlen for each charecter in a loop, which calls strlenCode: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); }
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.
Just for interest what book are using?
Data Structures-A pseudocode Approach with cOriginally posted by Nick
Just for interest what book are using?
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:
thats why i'm using array, but i'm so mess up...Code:slot 0 1 2 3 -------- --------------------------------------- bucket 0 AAA BBB CCC DD 1 FFF XXX OO KK 2 SSS XYZ TT . . . 256 QQ PP
thanx anyway