Author: Bruce Moreland
Date: 13:17:53 01/20/99
Go up one level in this thread
On January 19, 1999 at 14:16:54, Eugene Nalimov wrote: >Linear rehash results in large clusters of non-empty elements. >The element that conflicts with *any* element in the cluster >will be added to that cluster, so big cluster will be bigger >and bigger over the time. With non-linear rehash conflicting >elements will be added to other clusters. You can find >discussion, analysis, and experimental results in > > D. Knuth, The Art of Computer Programming, Vol.3, > 2nd edition, pp. 526-531. > >(the data is there in the 1st edition, too, but page numbers >are different). > >At least that will happen with classic hash table, without limit >on the # of retries. When there is such a limit I don't know what >will happen, but suspect that when that limit is large enough >(e.g. 8), non-linear rehash will be better (in the terms of hash >table collisions), too - almost all assumptions are the same as in >the classic case. I read this after I responded to Bob. I will assume Knuth knows what he is talking about, although I still don't understand intuitively why the degradation on *average* won't be the same in both cases, since rather than rarely hitting a real bad case, you are more commonly hitting less bad cases. Unfortunately this won't help me either way since I don't rehash. bruce
This page took 0.01 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.