Author: Eugene Nalimov
Date: 17:17:04 01/20/99
Go up one level in this thread
On January 20, 1999 at 16:17:53, Bruce Moreland wrote: > >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 Ok. Here is simplified example. Let's assume that we have large enough hash table, and there are 20 non-empty entries. Now assume that we search each of the keys equal number of times. Case 1. There are 10 clusters, each of length 2. Then we have to probe 1.5 entries in average during the search (in half of the probes we'll find the entry on the first try, in half - on the second try). Case 2. There is 1 cluster that contains all 20 entries. Here average number of probes is 10.5. Eugene Case
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.