Spaz Wrote:errr...I would *think* the second would be faster since you're doing 1 lookup instead of 3. In a properly implemented hash table with a good hash function, lookup is O(1) with the size of the table.
Main costs of hash table are overfull (lots of collisions -> slower lookup) or resizing (may have to recalculate all keys)
If you know how big it'll be, as in the given example, it won't be a problem. I'm not sure splitting into smaller tables helps though, as efficient hashing avoids clumping it'll tend to have to resize all the tables anyway if they become overfull.
In terms of seek time, I think having to follow more pointers would be slower than just having a big table (key 1->value 1, value 1->table 2, key 2->value 2, value 2->table 3, key 3->value 3) or (longer key -> final value)
The 1 big table does require some concatenation to make the key, but I don't think that takes long.
otoh if you can generalize some areas to less depth (eg. all lookups with a=b=0 return 0 instead of a c hash table) then being able to cut off at an earlier depth might be better than having to look up the full string every time.