hash design problem: both string and int[] keys

[Ali Çehreli]

On 11/20/2012 11:39 AM, Charles Hixson wrote:

 > I'm trying to figure out how to construct an associative array whose
 > keys will be a combination of strings and immutable int[]'s, but every
 > approach I've looked at has run into problems.

Can you show some code?

 > It should be relatively
 > easy, as strings are really just an immutable list of ints,

A list of dchars is more accurate of course, but yes, dchar can be 
casted to int.

 > but I
 > haven't been able to find how strings are hashed. (It's looking as if
 > the details are handled in C...which makes it difficult.)

I bet the algorithm considers all of the characters of the strings. The 
following has been mentioned in a recent forum thread:

   http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

 > I could define
 > my own hash code, but I don't find it at all clear what would be
 > appropriate given that I don't know the size.

I wonder how much slow iterating over string would be, compared to 
directly accessing the elements of a dstring. (After all, strings must 
be decoded to produce dchars.)

In any case, you don't need the length of the string; a loop would do:

     while (!s.empty) {
         // ... use s.front and s.popFront() ...
     }

Alternatively:

     foreach (c; stride(s, 1)) {
         // ... use c ...
     }

UFCS looks better: :)

     foreach (c; s.stride(1)) {
         // ... use c ...
     }

 > The data is rather sparse,
 > so a hash table seems appropriate. (My only other alternative is a
 > database, and that imposes the heavy slowdown of I/O ... even though it
 > does automate persistence it doesn't seem like a good tradeoff.)
 >
 > So far my best idea is to build two tables, and then look at the key
 > when a retrieval is attempted to figure out which table it's in. That
 > would probably work, but it feels like a kludge.

How do you differentiate between the key type being int[] vs. string?

Ali