== Quote from Steven Schveighoffer (schvei...@yahoo.com)'s article > My hash implementation isn't anything special, I basically implemented the > pseudo code from my algo book. The only reason it outperforms AA is > because of the custom allocator. > -Steve
Yes, but the allocation scheme is the main problem with the current implementation. IMHO memory allocation is one of the trickiest parts of designing an efficient hash table. My RandAA implementation is designed to get around this by simply performing very few allocations. In fact, if you know the approximate size that the table will be before you start creating it, you can simply pre-allocate the whole thing in O(1) allocations, and then never have to allocate while building the table. However, this comes at some cost in terms of lookup performance. If you have an even better solution, it would be great if it's used in the builtin AAs, instead of being buried in std.collections (or worse yet, in a third party lib), which most people won't use use b/c the builtin AAs have nicer syntax and are more discoverable.
