From: Lyle Johnson <lyle@...>
Date: 2002-09-06T22:51:02+09:00
Subject: Re: Time to retire st_* and replace it with Judy?

Doug Baskins wrote:

>> IMHO the st_* routines are meant to be more general than simple string->word
>> mapping :-( The key comparison function might be more complex than
>> bit-by-bit...
> 
> Ok, what could a compare routine do besides compare bit-by-bit in a hashed
> environment?

The st_* routines are used in different ways. There are two special 
cases: (1) where all the keys are assumed to be integers and (2) where 
all the keys are assumed to be strings. Both of these methods are used 
internally in different places and I would expect Judy Arrays to help 
improve those cases (but I haven't tried this).

Ruby's Hash class, however, uses the third and most general case. For 
this case, no assumption is made about the types of the keys (i.e. they 
can be mixed). The keys are compared by calling the objects' eql? 
method. For example, during a lookup of the key "a", Ruby will:

* determine the hash value for a by invoking a's "hash" method
* look-up its bucket in the hash table
* if there's a collision, walk through the list of collisions
   looking for the key by calling a.eql?(key).

So the short answer is, the compare routine (eql?) could do anything it 
wants to. That's not to say that Judy Arrays couldn't also speed up this 
more general Hash table too; I'm just trying to explain the extra work 
it's doing over the more special-purpose cases.

Hope this helps,

Lyle