Coalesce Hashing in C
#include <stdio.h> #include <stdlib.h> #define TABLESIZE 37 #define PRIME 13 enum Marker {EMPTY,USED}; typedef struct _slot{ int key; enum Marker indicator; int next; } HashSlot; int HashInsert(int key, HashSlot hashTable[]); int HashFind(int key, HashSlot hashTable[]); int hash(int key) { return (key % TABLESIZE); } int main() { int opt; int i; int key; int index; HashSlot hashTable[TABLESIZE]; for(i=0;i<TABLESIZE;i++){ hashTable[i].next = -1; hashTable[i].key = 0; hashTable[i].indicator = EMPTY; } printf("============= Hash Table ============\n"); printf("|1. Insert a key to the hash table |\n"); printf("|2. Search a key in the hash table |\n"); printf("|3. Print the hash table |\n"); printf("|4. Quit |\n"); printf("=====================================\n"); printf("Enter selection: "); scanf("%d",&opt); while(opt>=1 && opt <=3){ switch(opt){ case 1: printf("Enter a key to be inserted:\n"); scanf("%d",&key); index = HashInsert(key,hashTable); if(index <0) printf("Duplicate key\n"); else if(index < TABLESIZE) printf("Insert %d at index %d\n",key, index); else printf("Table is full.\n"); break; case 2: printf("Enter a key for searching in the HashTable:\n"); scanf("%d",&key); index = HashFind(key, hashTable); if(index!=-1) printf("%d is found at index %d.\n",key,index); else printf("%d is not found.\n",key); break; case 3: printf("index:\t key \t next\n"); for(i=0;i<TABLESIZE;i++) printf("%d\t%d\t%d\n",i, hashTable[i].key,hashTable[i].next); break; } printf("Enter selection: "); scanf("%d",&opt); } return 0; } int HashInsert(int key, HashSlot hashTable[]) { int index=hash(key),inIndex=0,count=0; if(hashTable[index].indicator == EMPTY) // first slot empty { hashTable[index].key = key; hashTable[index].next = -1; hashTable[index].indicator = USED; return index; } else // slot used { while(1) { while(hashTable[count].indicator == USED) // all slots used { count++; if(count == TABLESIZE) { return count; // return table is full } } if(index<TABLESIZE) // index slot < TABLESIZE { for(index=hash(key);index<TABLESIZE;index++) // iterate thru { if(hashTable[index].key == key) { return -1; } if (hashTable[index].next == -1 && hashTable[index].indicator == USED && hash(key)==hash(hashTable[index].key) )//save the last point where it has the same mod value { inIndex = index; } else if(hashTable[index].indicator == EMPTY) { hashTable[inIndex].next = index; // lastpoint.next = currentindex hashTable[index].key = key; hashTable[index].next = -1; hashTable[index].indicator = USED; return index; // return insertion value } } } else { for(index=hash(index);index<TABLESIZE;index++) // if index > TABLESIZE { if(hashTable[index].key == key) { return -1; } if (hashTable[index].next == -1 && hashTable[index].indicator == USED && hash(key)==hash(hashTable[index].key) ) //save the last point where it has the same mod value { inIndex = index; } else if(hashTable[index].indicator == EMPTY) { hashTable[inIndex].next = index; // latestmodvalue.next = currentindex hashTable[index].key = key; hashTable[index].next = -1; hashTable[index].indicator = USED; return index; // return insertion value } } } } } if(HashFind(key,hashTable) == index) // if key cant be found return -1; } int HashFind(int key, HashSlot hashTable[]) { int index; index = hash(key); if(hashTable[index].key == 0) return -1; // if empty slot , return -1 else if(hashTable[index].key == key) // if found key , return index { return index; } else { while(hashTable[index].key!=key && index!=-1) // find the link , then find the key { index = hashTable[index].next; } return index; } } The idea is to implement a hash table with a combination of closed addressing and linear probing. I have tried multiple test cases that I came up with such as dealing with negatives or accessing an item that is not in the HashTable, nothing seems to pass the hidden test case. Passed the sample test case though. Is there something that I am overlooking on?
Given test case :
Insert key : 1 2 5 41 42 4 10(search then insert)
Search key: 4 10(Display DNE)
Output from my Code
============= Hash Table ============ |1. Insert a key to the hash table | |2. Search a key in the hash table | |3. Print the hash table | |4. Quit | ===================================== Enter selection: 1 Enter a key to be inserted: Insert 1 at index 1 Enter selection: 1 Enter a key to be inserted: Insert 2 at index 2 Enter selection: 1 Enter a key to be inserted: Insert 5 at index 5 Enter selection: 1 Enter a key to be inserted: Insert 41 at index 4 Enter selection: 1 Enter a key to be inserted: Insert 42 at index 6 Enter selection: 3 index: key: next: 0 0 -1 1 1 -1 2 2 -1 3 0 -1 4 41 -1 5 5 6 6 42 -1 7 0 -1 8 0 -1 9 0 -1 10 0 -1 11 0 -1 12 0 -1 13 0 -1 14 0 -1 15 0 -1 16 0 -1 17 0 -1 18 0 -1 19 0 -1 20 0 -1 21 0 -1 22 0 -1 23 0 -1 24 0 -1 25 0 -1 26 0 -1 27 0 -1 28 0 -1 29 0 -1 30 0 -1 31 0 -1 32 0 -1 33 0 -1 34 0 -1 35 0 -1 36 0 -1 Enter selection: 1 Enter a key to be inserted: Insert 4 at index 7 Enter selection: 2 Enter a key for searching in the HashTable: 4 is found at index 7. Enter selection: 2 Enter a key for searching in the HashTable: 10 is not found. Enter selection: 1 Enter a key to be inserted: Insert 10 at index 10 Enter selection: 3 index: key: next: 0 0 -1 1 1 -1 2 2 -1 3 0 -1 4 41 7 5 5 6 6 42 -1 7 4 -1 8 0 -1 9 0 -1 10 10 -1 11 0 -1 12 0 -1 13 0 -1 14 0 -1 15 0 -1 16 0 -1 17 0 -1 18 0 -1 19 0 -1 20 0 -1 21 0 -1 22 0 -1 23 0 -1 24 0 -1 25 0 -1 26 0 -1 27 0 -1 28 0 -1 29 0 -1 30 0 -1 31 0 -1 32 0 -1 33 0 -1 34 0 -1 35 0 -1 36 0 -1 
没有评论:
发表评论