Memory usage of AAs?

[spir]

On 03/30/2011 01:24 AM, Nick Sabalausky wrote:
> My understanding of hash tables is that they allocate a fixed size array and
> map keys to indicies within the range 0..predefined_length_of_the_AA.
>
> So I've been wondering, how many elements do D's built-in AAs have? And
> what's the content of each one, just a single pointer?

Each element is a data structure, often called bucket (typically a link list), 
storing (key:value) pairs for which the key, once hashed and modulo-ed, maps to 
the given index. That's why the famous O(1) lookup time for hash tables is very 
theoretic: the constant part holds average time for hashing which is very 
variable, plus another average time for linearly traversing the bucket. The 
latter part depends on table load factor (= number of elements / number of 
buckets) and proper statistical repartition of keys into buckets.

The key (!) points are finding a good hash func to "linearize" said repartition 
(which depends on actual key-data domain, not only on their type...), but 
better ones rapidly eat much time (ones used in practice are rather simple & 
fast); and finding optimal load factor, and growth scheme. In practice, all of 
this tends to make hash tables an implementation nightmare (for me). I'd love 
to find practicle alternatives, but efficient binary trees also are complex and 
even more depend on kind of keys, I guess.

Denis
-- 
_________________
vita es estrany
spir.wikidot.com