Author: Bruce Moreland
Date: 10:12:35 04/11/00
Go up one level in this thread
On April 11, 2000 at 11:04:35, Colin Frayn wrote: >This has been bugging me for a while. > >I've read a few articles and messages recently talking about hashtables, and how >different people implement them and deal with collisions. > >Basically, the idea is to take the hash key, and then somehow map it >non-injectively onto the (presumably smaller) hash space by taking the remainder >of a modulus division. Problem with this is of course that you get collisions, >whereby two _different_ keys map onto the _same_ hash index. This isn't the >same as two different _positions_ mapping onto the same hash _key_, but is due >to the many-to-one mapping from the key to a hash index. >(the mapping to a hash key had better be bijective or your program is gonna >start churning out strange results :) ) > >As far as I can see, many people get round this by choosing whether to keep the >original entry or to replace it with the new entry whenever a collision occurs. > >Why is this? Isn't that wasteful? > >The way I implement my hashtable, I have each hash entry followed by a linked >list of hash entries which are all different positions, but all map to the same >hash index. Every time a position is stored in the hash table, I check to see >if it is already there, in which case I only replace it if the new version is >deeper. If not, then I simply add another element at the head of the linked >list at the correct index value with the _new_ position and its values. > >Admittedly this takes more space to store as I have the hash key stored along >with the entry (because I need to distinguish between entries with identical >hash indices, but different keys.) but recent studies have shown that the >number of entries in a hash table (past a certain limit) makes hardly any >difference to the playing quality anyway. Certainly not in Blitz. > >Is this method dumb? Why? It just takes a little nasty pointer arithmetic, but >other than that it's pretty straightforward. The length of the list is rarely >more than 2 or 3 entries, so it takes no time at all to traverse. > >Input appreciated. > >Cheers, >Col If you take an apple and cut it in two, you don't have two apples. The extra space you reserve for overflow could be added to the main table. Your solution only works if you don't fill up your table, but I think that in most cases people are filling up their tables. bruce
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.