Re: avl-trees vs. hashes

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

On Wed, 28 Oct 1998, Jay Glascoe wrote:

> yes, in almost all cases.  it's faster, e.g. to check whether two symbols
> are eq? because then, in the C code, you're comparing two long's,
> whereas testing two SCM numbers requires that you do two SCM_INUM()'s
> 
> #define SCM_INUM(x) (((x)>>1)>>1)

which takes a fraction of a nano-second.

> the problem is that a full size long won't fit into a SCM INUM.  I'm
> currently masking (and'ing) my hash with 2,097,157 which does fit, but
> obviously won't work work for extremely huge tables (>2,000,000 entries). 

536,870,912 = 2 ^ 29 - 1 

fits alright, and

536,870,909 = 536,870,912 - 3

is prime (bonus!).  Anyone needing a hash table with more than half a
billion entries (perhaps to keep track of each individual McDonald's
hamburger sold over the course of one week ;)  would probably be better
off with some kind of database instead.  From now on all my hash values
will be INUM's.

	Jay
	jglascoe@jay.giss.nasa.gov