[Freeciv-Dev] Re: Hash tables

[sebauer@xxxxxxxxxxx (Sebastian Bauer)]

Hi David

On 27-Mär-00, David Pfitzner wrote:
> Sebastian Bauer wrote:
>> 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.

Yes. I saw it now :-)

> ("closed hashing" IIRC, compared to "open hashing" which Vasco
> was referring to.  Unless it's the other way round ;-).

It's the other way around ;-)
It is called open hashing because unused buckets (still opened)
are used in case of a collision.

> 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.

Yes, open hashing (this which your implemention uses) is said to
be good if you know about the number of buckets which should be
inserted.

>>> 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.)

Hmm...if I think about it...this could be.
I neihter really know it nor I have tested it yet for myself. At
least the hash function we had was better if the maximal number of
buckets was a prime number.

bye,
Sebastian Bauer