AA with complex keytype?

[Jarrett Billingsley]

"Bill Baxter" <dnewsgroup at billbaxter.com> wrote in message 
news:eqkmg1$hnb$1 at digitaldaemon.com...

> Someone who has too much time on their hands should take a look at what 
> the code for Python dicts and Lua tables do.  Both of those are reputed to 
> be heavily tweaked for super-duper performance.

Lua tables use (according to the source) "a mix of chained scatter table 
with Brent's variation."  The insert method comment reads:

/*
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its 
main
** position), new key goes to an empty position.
*/

It's basically using a variation on separate chaining.  Additionally, Lua 5 
tables will attempt to keep integer keys in a true array rather than in the 
hash, which improves performance when using tables as arrays, but that's not 
really necessary in a language that has true arrays like D ;)