> Could we make all really small hashed structures do linear searches?
> 
> - Stephen

Can you elaborate on exactly what improvement you are thinking of?

The hash algorithm is already more or less linear, the hash is used to get
the first index to look at, and then the code scans thru the remaining slots
in consecutive order (index _ index + 1) wrapping around as needed.

(This apparently inefficient scanning strategy is to make scanning during
message lookup cheap; more complex schemes such as double hashing would
require more complex operations there. IIRC I measured that the gain from
scanning fewer slots would be relatively minor.)

The only difference that I see for small dictionaries is to always start the
scan at 1; this would merely save the calculation of the hash value for the
key, and I think the gain is negligible.

I could be wrong though, and this is why I ask the above question.

Henrik