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
