Helu gurus!!! I have a code below about hashing method with collision resolution...My problem is how to use the collsion resolution again if the hash index though has already a value. Please kinda help me with this..I want to determine also if the table now is full so as to stop user from entering a key.
size of the table=19,
Thanx a lot..GodBless
________________________________________________ -
#include<iostream.h>
-
#include<conio.h>
-
-
//function prototypes
-
int input(int);
-
int process(int);
-
void output(int,int);
-
int collision(int,int);
-
-
//global variable
-
int arr[19]={0};
-
-
//start of main program
-
main()
-
{
-
int key,hash_key,hash_index,m=0;
-
cout<<"Hash method: FOLD BOUNDARY";
-
cout<<"\nCollision resolution method: KEY OFFSET";
-
cout<<"\nEnter 6 digit numbers.";
-
cout<<"\nEnter 0 as sentinel.";
-
while(m<19){
-
-
hash_key=input(key);
-
if (hash_key==0) { return 0;}
-
else
-
{ hash_index=process(hash_key);
-
output(hash_key,hash_index); }
-
-
} m++;
-
cout<<"\nEntered numbers execeeded!"; //end of loop
-
}//end of main program
-
-
//start of input function
-
int input(int x){
-
cout<<"\n\nEnter key:";
-
cin>>x;
-
return x;}
-
//end of input function
-
-
//start of process function
-
int process(int x){
-
int a,b,c,d,e,f;
-
a=x/100000;
-
b=x%100000/10000;
-
int v=(b*10)+a;
-
-
c=x%10000/1000;
-
d=x%1000/100;
-
int q=(c*10)+d;
-
-
e=x%10;
-
f=x%100/10;
-
int w=(e*10)+f ;
-
-
return (w+v+q)%19+1;
-
} //end of process function
-
-
//start of output function
-
void output(int key,int adres){
-
int b,z,index1=0,index2=0,index3=0,index4=0,u;
-
bool wer;
-
cout<<"\n\tList\tKey\n";
-
-
while (arr[adres-1]!=0)
-
{ index1=collision(key,adres);
-
arr[index1-1]=key;break;
-
-
if (arr[index1-1]!=0)
-
{ index2=collision(key,index1);
-
arr[index2-1]=key;
-
-
if(arr[index2-1]!=0)
-
{ index3=collision(key,index2);
-
arr[index3-1]=key;
-
}
-
}
-
}
-
-
if (arr[adres-1]==0)
-
{ arr[adres-1]=key; }
-
-
for(u=0;u<19;u++){
-
z=arr[u];
-
cout<<"\t"<<(u+1)<<".\t"<<z<<endl; }
-
}
-
-
//end of output function
-
-
//start of collision resolution method
-
int collision(int key,int hashed){
-
int offset,adrs;
-
offset=(key/19;
-
adrs=((offset + hashed) % 19 )+1;
-
return adrs;
-
}
-
//end of collision resolution method
1 9532
May,
The following is rather lengthy, but is a complete system which contains a hashing algorithm that I cranked out in the past hour. Some code was borrowed from some previous software that I had written. At any rate, the code is written in C, as a console program, not in C++ but you should be able to use it directly from within C++.
This shows a method of hashing where you never have to worry about running out of space, and don't have to concern yourself with collisions as they will all be gracefully addressed.
What this does, is take a text file as input, parses out all ot the words (including non words, as I didn't spend the time to remove them), then adds the words to a hash table. If the word already exists in the table, only the count is incremented.
The hashing algorithm is taken directly from the Aho book on compiler design. It works extremely well with strings, but dosen't handle numbers without conversion to text. This is a small price to pay, because it is extremely fast as far as operation is concerned. I used to be able to process one million phone calls per minute on an HP9000 for a major phone company.
Once the file has been added to the hash table, you are allowed to enter words, which will be looked up in the hash table and displayed on the console, along with the number of times that it appears in the document.
The code will be in 8 small files. the only two that you will really need to look at are Hash.c, LoadHashTable.c and TryItOut.c the rest are part of the complete package.
If you have any questions at all, please ask.
Module name HashExample.h - #ifndef __HashExample__h
-
#define __HashExample__h
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <string.h>
-
#include <stdarg.h>
-
-
#define MASK 0xf0000000
-
#define SHIFT 24
-
#define HashTableNumItems 5003 // Needs to be a prime number for
-
// best distribution. At least 10% of
-
// estimated data size.
-
-
#define FileBuffSz 4096
-
#define Buff80 80
-
#define Buff256 256
-
-
#ifndef bool
-
#define bool int
-
#endif
-
-
#ifndef True
-
#define True 1
-
#define False 0
-
#endif
-
-
typedef struct _wordused
-
{
-
struct _wordused *Next;
-
char *WordUsed;
-
long NumberOfTimesUsed;
-
} wordused;
-
-
typedef struct
-
{
-
long SysInfoSz;
-
FILE *InFile;
-
FILE *Trace;
-
char *InFileName;
-
char *InBuff;
-
wordused *HashTable[HashTableNumItems];
-
int argc;
-
char **argv;
-
long TotalNumberOfWords;
-
} sysinfo;
-
-
// Function prototypes
-
void main(int argc, char** argv);
-
void Initialize(sysinfo *SysInfo);
-
void TryItOut(sysinfo *SysInfo);
-
void FreeData(sysinfo *SysInfo);
-
void LoadHashTable(sysinfo *SysInfo);
-
unsigned int Hash(char *String, long TabLen);
-
void SysAbort(sysinfo *SysInfo, char *String, int NumArgs, ...);
-
#endif
Module Name: HashExample.c - /*
-
*
-
* Example of Hashing which never runs out of space, and
-
* handles collisions gracefully and painlessly
-
*
-
* Usage for this Example HashExample -f FileName
-
8 where filename = the name of a local text file
-
* or remote file (with full path)
-
*
-
* What does it do? It will parse all of the words
-
* In the input file, counting the number of
-
* occurences of each word. After the input file
-
* has been parsed, the user can query on a word
-
* and the count will be returned.
-
*
-
* Plese note that the hashing algorithm used expects
-
* a string input, there fore integers, floats, etc.
-
* must be converted to string before hashing. The
-
* algorithm does, however, give extremely good
-
* distribution, thus making it ideal for very large
-
* amounts of entries. I used it while employed in the
-
* telecommunications industry for looking up data in
-
* indexed flat files (created using the hash) of over
-
* 4 million records. The original algorithm comes from
-
* Compilers: Principles, Techniques, and Tools ...
-
* By: Alfred V. Aho - fondly known as the Dragon book.
-
*
-
* Enjoy !
-
*
-
*/
-
#include "HashExample.h"
-
-
void main(int argc, char** argv)
-
{
-
sysinfo *SysInfo = NULL;
-
-
SysInfo = (sysinfo *) calloc(1, sizeof(sysinfo));
-
SysInfo->argc = argc;
-
SysInfo->argv = argv;
-
-
Initialize(SysInfo);
-
LoadHashTable(SysInfo);
-
TryItOut(SysInfo);
-
FreeData(SysInfo);
-
free(SysInfo);
-
}
-
Module Name: Initialize.c - #include "HashExample.h"
-
-
void Initialize(sysinfo *SysInfo)
-
{
-
char *ArgPtr = NULL;
-
char Argid = 0;
-
int i = 0;
-
-
SysInfo->SysInfoSz = sizeof(sysinfo);
-
for(i = 1; i < SysInfo->argc; i++)
-
{
-
if(SysInfo->argv[i][0] == '-')
-
{
-
Argid = SysInfo->argv[i][1];
-
if(!SysInfo->argv[i][2])
-
{
-
i++;
-
ArgPtr = SysInfo->argv[i];
-
}
-
else
-
ArgPtr = (char *)&SysInfo->argv[i][2];
-
switch (Argid)
-
{
-
case 'f':
-
SysInfo->InFileName = ArgPtr;
-
break;
-
default:
-
SysAbort(SysInfo, "%c is not a valid option", 1, Argid);
-
}
-
}
-
}
-
-
if(SysInfo->InFileName == NULL)
-
SysAbort(SysInfo, "Please Specify Input File Name with -f option", 0);
-
-
SysInfo->InBuff = (char *)calloc(1, FileBuffSz);
-
SysInfo->TotalNumberOfWords = 0;
-
}
-
Module Name: SysAbort.c - #include "HashExample.h"
-
-
void SysAbort(sysinfo *SysInfo, char *String, int NumArgs, ...)
-
{
-
va_list ap;
-
va_start(ap, NumArgs);
-
-
vfprintf(stderr, String, ap);
-
-
va_end(ap);
-
-
// Check if n\memory needs to be cleaned up
-
FreeData(SysInfo);
-
-
free(SysInfo);
-
exit(1);
-
}
Module Name: FreeData.c - #include "HashExample.h"
-
-
void FreeData(sysinfo *SysInfo)
-
{
-
int i = 0;
-
wordused *CurrentNode = NULL;
-
wordused *NextNode = NULL;
-
-
fclose(SysInfo->InFile);
-
-
for(i = 0; i < HashTableNumItems; i++)
-
{
-
CurrentNode = SysInfo->HashTable[i];
-
if(CurrentNode)
-
{
-
while(CurrentNode)
-
{
-
NextNode = CurrentNode->Next;
-
free(CurrentNode->WordUsed);
-
free(CurrentNode);
-
CurrentNode = NextNode;
-
}
-
}
-
}
-
-
free(SysInfo->InBuff);
-
}
-
Module Name: Hash.c - #include "HashExample.h"
-
-
unsigned int Hash(char *String, long TabLen)
-
{
-
unsigned long HashCode = 0;
-
unsigned long g = 0;
-
char *p;
-
-
if(String) {
-
for(p = String; *p; p++) {
-
HashCode = (HashCode << 4) + *p;
-
if(g = HashCode & MASK) {
-
HashCode ^= g >> SHIFT;
-
HashCode ^= g;
-
}
-
}
-
}
-
return(HashCode % TabLen);
-
}
-
Module Name: LoadHashTable.c - #include "HashExample.h"
-
-
void LoadHashTable(sysinfo *SysInfo)
-
{
-
int i = 0;
-
int NodeSz = sizeof(wordused);
-
unsigned long HashCode = 0L;
-
wordused *CurrentNode = NULL;
-
int IdxSz = sizeof(wordused);
-
char *Word = NULL;
-
bool FoundItem = False;
-
-
for(i = 0; i < HashTableNumItems; i++)
-
{
-
SysInfo->HashTable[i] = NULL;
-
}
-
-
SysInfo->InFile = fopen(SysInfo->InFileName, "r");
-
if(SysInfo->InFile == NULL)
-
{
-
fprintf(stderr, "Unable to open InFile", SysInfo->InFileName);
-
}
-
else
-
{
-
while(True)
-
{
-
fread(SysInfo->InBuff, IdxSz, 1, SysInfo->InFile);
-
if(feof(SysInfo->InFile))
-
break;
-
Word = strtok(SysInfo->InBuff, " \n\t");
-
while(Word)
-
{
-
FoundItem = False;
-
HashCode = Hash(Word, HashTableNumItems);
-
CurrentNode = SysInfo->HashTable[HashCode];
-
CurrentNode = SysInfo->HashTable[HashCode];
-
if(CurrentNode)
-
{
-
while(CurrentNode)
-
{
-
if(CurrentNode->WordUsed &&
-
(!(strcmp(CurrentNode->WordUsed, Word))))
-
{
-
CurrentNode->NumberOfTimesUsed += 1;
-
FoundItem = True;
-
break;
-
}
-
else if(CurrentNode->Next == NULL)
-
{
-
CurrentNode->Next = (wordused *)calloc(1, NodeSz);
-
break;
-
}
-
else
-
CurrentNode = CurrentNode->Next;
-
}
-
}
-
if(!FoundItem)
-
{
-
SysInfo->TotalNumberOfWords += 1;
-
if(!CurrentNode)
-
{
-
CurrentNode = SysInfo->HashTable[HashCode] =
-
(wordused *)calloc(1, NodeSz);
-
}
-
CurrentNode->WordUsed = (char *)calloc(1, (strlen(Word)+1));
-
strcpy(CurrentNode->WordUsed, Word);
-
CurrentNode->NumberOfTimesUsed = 1;
-
}
-
Word = strtok(NULL, " \n\t");
-
}
-
}
-
}
-
}
Module Name: TryItOut.c - #include "HashExample.h"
-
-
void TryItOut(sysinfo *SysInfo)
-
{
-
wordused *CurrentNode = NULL;
-
unsigned long HashCode = 0L;
-
char *Aword = (char *)calloc(1, Buff256);
-
bool WordFound = False;
-
-
fprintf(stdout, "The document contained %ld words\n",
-
SysInfo->TotalNumberOfWords);
-
while(True)
-
{
-
gets(Aword);
-
if(!(strcmp(Aword, "GoodByeYall")))
-
break;
-
HashCode = Hash(Aword, HashTableNumItems);
-
CurrentNode = SysInfo->HashTable[HashCode]; WordFound = False;
-
while(CurrentNode)
-
{
-
if(!strcmp(CurrentNode->WordUsed, Aword))
-
{
-
WordFound = True;
-
break;
-
}
-
CurrentNode = CurrentNode->Next;
-
}
-
-
if(WordFound)
-
fprintf(stdout, "%s was used in the document %d times\n",
-
Aword, CurrentNode->NumberOfTimesUsed);
-
else
-
fprintf(stdout, "%s was not used in the document\n");
-
}
-
}
-
Ti exit the program, type 'GoodByeYall' case sensitive.
Enjoy,
Larry
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Farouche |
last post by:
Hi
I would like some suggestions on how to, effectively compute a Hash Value
for a "Collection" of simple Field Objects:
internal class Field
{
private string _fieldName;
private object...
|
by: Dave |
last post by:
Hi folks,
I am trying to develop a routine that will handle sphere-sphere and
sphere-triangle collisions and interactions. My aim is to develop a
quake style collision engine where a player can...
|
by: Foodbank |
last post by:
Hi,
Has anyone ever hashed a text file to disk before? I'm trying to
convert an in-memory hash to disk hash and I can't find any relevant
information to help me. Also, I'd like to use lseek,...
|
by: Maya |
last post by:
Hello all,
I'm using MD5 hashing in my application to give unique values to huge
list of items my application receives, originally every item's name was
difficult to use as an id for this item...
|
by: raylopez99 |
last post by:
I seem to get name collision between the Generic collection SortedList
and C++.NET Framework collection SortedList.
How to resolve? Here are the libraries that seem to clash:...
|
by: January Weiner |
last post by:
Hello,
I need to use a hashing function for relatively short strings (roughly 16
characters or less). The data that needs to be accessed via hash is just a
simple int. I just need to look up...
|
by: Johnny Jörgensen |
last post by:
I'm wondering (and hoping that somebody will be able to answer this):
If I calculate the hash value of files (either MD5 or SHA1), can I then be
sure that:
1) Two files with the same hash...
|
by: Helmut Jarausch |
last post by:
Hi,
I need to hash arrays of integers (from the hash module).
So, I have to derive from array and supply a __hash__ method.
But how to hash an array (of fixed length, say 25)?
What I need is...
|
by: dansongarcia |
last post by:
I am currently doing an investigation in this topic. Please give some feedback that can help me in my investigation.
Is there any way to compare hash functions namely: Extraction, Folding,...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
|
by: ryjfgjl |
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
| |