Date: Thu, 17 Jun 1999 14:47:27 +0200 From: Hans-Bernhard Broeker Message-Id: <199906171247.OAA02123@acp3bf.physik.rwth-aachen.de> To: djgpp AT delorie DOT com Subject: Re: Perl versus C Newsgroups: comp.os.msdos.djgpp Organization: RWTH Aachen, III. physikalisches Institut B X-Newsreader: TIN [version 1.2 PL2] Reply-To: djgpp AT delorie DOT com 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.