Associative arrays with void values

[Steven Schveighoffer]

On Mon, 13 Apr 2009 01:45:00 -0400, bearophile <bearophileHUGS at lycos.com>  
wrote:

> dsimcha:
>> What if the key is a long?
>
> At the moment an AA like this:
> byte[long] aa;
> allocates 16 or more bytes/pair, so it needs the same memory as:
> long[long] aa;
>
> A built-in set can of course use only about 8 bytes (plus few empty  
> cells in the hash) for a:
> HashSet!(long)
>
> Bye,
> bearophile

The AA node types are currently implemented as a binary tree for collision  
resolution, so each node also needs at least 2 pointers for the child  
nodes.  Possibly a parent pointer, but I don't think so.

So T[long] aa will be 16 bytes + sizeof(T) for each node, assuming a  
pointer is 4 bytes.

But technically, there is always going to be cases where waste occurs,  
even without the void hack, depending on the resulting size of your  
nodes.  Imagine a 33 byte node, which will use up 64 bytes of space per  
node.  This is one of the reasons Tango and Dcollections have chunk  
allocators where a large chunk of nodes is allocated at once from the GC  
(or from malloc for non-GC types).

-Steve