Mail Archives: djgpp/1999/06/17/10:32:31
In article <37689859 DOT CC4782DC AT cfwb DOT be> you wrote:
> Hi all,
> I had developped a program in Perl a few month ago and I would like to
> re-write it in C. So my Perl program is not very complex but use
> "hashing".
> Does somebody know how to code "hashing" in C language?
There's no general support for hash tables, at all, in C. You have to
do it by hand, or use third-party libraries to do it for you. You'll
probably need some textbook on data structures and algorithms to learn
about all the details, but the outline of the method is:
1) create a 'hash function' that takes your 'key' type (string, or
whatever), and calculates an integer from it. The integer should come
out equally distributed over a fixed range, say [0 ... N-1]. N should
be roughly twice as large as the number of entries to be expected. Try
to mix up the bits of the input data as thoroughly as you can.
2) Create an array of N elements, and flag them all as 'unused'
3) For each incoming data element, use the hash function to calculate
a position in the array. If that position is still unused, store
the data element there. If the position is already used, you have two
possibilities:
a) make each array element a linked list or other dynamic datastructure.
This results in a mixture of hashing and non-hashing methods of storage
organization.
b) Prepare another function that takes an index number and calculates a
'following' index number from it. Return to 3) with this new index
number, until you found an unused entry
For accessing an element, you 'hash' it, and check the entry at the
hashed index position. If the entry's not there, but the field is
used, follow the 'next' index numbers, as in 3b), until you either
find it, or end up at an unused entry. The latter result means the
element is not (yet) present, and could be inserted at this position.
--
Hans-Bernhard Broeker (broeker AT physik DOT rwth-aachen DOT de)
Even if all the snow were burnt, ashes would remain.
- Raw text -