Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations SkipVought on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Best way to implement a hash-like structure?
- Thread starter svar
- Start date
The "low-level" solution: take your string 'xxiofhdj' and get the sum of each char. (x is a decimal 65 and so on - google "ascii chart" for more). So, sum=65+65+105+111+102+104+100+106
Now take the total number of records n (maybe an estimate) and double it, N=n*2. (optionally, take the first prime # greater than N - there exists a proof that the algorithm is faster when N is a prime.)
Next, divide the sum by N and take the remainder, R. R will be an integer between 0 and N-1.
Next, make an array
char *hashTable[N];
Store your string in the array:
hashTable[R] = "xxiofhdj"; /* usually this string is a
key field of a record
with other fields */
practically speaking, there would be more fields associated with the key string, e.g.
hashTable[R]="xxiofhdj,032404,215-555-1234";
To do a lookup (hash lookups are very fast!), take a string as input, add the chars, divide by N and get R, then go to hashTable[R]. There you will find your string (key field with more fields - see comment above)
Ooops, wait a minute, what if some other string "hashed" to the same R value? This is called a collision. I know of two ways to handle collisions.
1. easy way -
1.1 assign to hashTable - if hashTable[R] is used, then try hashTable[R+1], and keep going (R+2, R+3, ...) until you find an unused cell.
1.2 lookup - compare string at hashTable[R] with input string. If not same, then compare hashTable[R+1], and keep going (R+2, R+3, ...) until you find an a match.
2. Harder way
2.1 assign to hashTable - Create a linked list at hashTable[R], whenver there is a collision, add to the linked list.
2.2 lookup - left to you to figure out
Have fun!
Now take the total number of records n (maybe an estimate) and double it, N=n*2. (optionally, take the first prime # greater than N - there exists a proof that the algorithm is faster when N is a prime.)
Next, divide the sum by N and take the remainder, R. R will be an integer between 0 and N-1.
Next, make an array
char *hashTable[N];
Store your string in the array:
hashTable[R] = "xxiofhdj"; /* usually this string is a
key field of a record
with other fields */
practically speaking, there would be more fields associated with the key string, e.g.
hashTable[R]="xxiofhdj,032404,215-555-1234";
To do a lookup (hash lookups are very fast!), take a string as input, add the chars, divide by N and get R, then go to hashTable[R]. There you will find your string (key field with more fields - see comment above)
Ooops, wait a minute, what if some other string "hashed" to the same R value? This is called a collision. I know of two ways to handle collisions.
1. easy way -
1.1 assign to hashTable - if hashTable[R] is used, then try hashTable[R+1], and keep going (R+2, R+3, ...) until you find an unused cell.
1.2 lookup - compare string at hashTable[R] with input string. If not same, then compare hashTable[R+1], and keep going (R+2, R+3, ...) until you find an a match.
2. Harder way
2.1 assign to hashTable - Create a linked list at hashTable[R], whenver there is a collision, add to the linked list.
2.2 lookup - left to you to figure out
Have fun!
See GNU gperf utility (state-of-art string hashing example):
- Status
Similar threads
