[Freeciv-Dev] Re: Hash tables

[David Pfitzner <dwp@xxxxxxxxxxxxxx>]

Sebastian Bauer wrote:
> On 26-Mär-00, Vasco Alexandre Da Silva Costa wrote:
> > i.e. each bucket contains a list of nodes.
> 
> > In the current implementation, each bucket can contain only one node.
> > So if there is a colision, we have a big problem.
> 
> Since hashing was the last thing (but I haven't though about it really)
> we had in university...if there is a collision you could also take
> for example the next bucket and see if it free. If it is free take this
> if not try the next again (this is called linear probing, there also
> other methods but this is the simplest I guess).

Yes, this is exactly what the current implementation does.
("closed hashing" IIRC, compared to "open hashing" which Vasco
was referring to.  Unless it's the other way round ;-).

Simple to code, and simple memory allocation pattern (eg avoids 
lots of small memory allocations for buckets/genlists).  I think 
the appropriate number of buckets differs depending on whether 
you have open or closed hashing, but the current values are very 
guessy anyway.
 
> > Also, the size of an hash table (number of buckets) should be a prime
> > number to reduce the number of colisions.
> 
> Yes, we learned that too :-)

I thought that in general this would depend on the specific
hash function used?  (Not that I know that case for any specific 
hash function, and thanks to Vasco for the improved one.)

-- David