[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Poor ROTten SXHASH
- To: JONL at MIT-MC (Jon L White)
- Subject: Re: Poor ROTten SXHASH
- From: Guy.Steele at CMU-10A
- Date: Fri ,31 Oct 80 16:02:00 EDT
- Cc: lisp-forum at MIT-MC
The hash function you suggest for vectors is probably adequate.
I don't think that adding in a funny function of I helps.
I went down that path some time ago when analyzing the function.
If you remember that + is commutative and associative, then
it becomes clear that adding in (randomify I) on every cycle
is the same as adding in (SUM I 0 N (randomify I)) = (randomify1 N)
at the end of the loop. (Ooops, that's not quite right -- the result
gets ROT'd at each step -- but the principle is roughly the same.)
So it's not really as good an extra randomization as one might think.
I recommend ROT'ing by more than 1 though -- maybe by 11 or so --
so as to cause more "edge interactions" (get the former ends of the
word near the middle so additive carries will muddle things up;
this reduces the probability of the + really being associative).