Talk:Hashed array tree

Please add this to http://en.wikipedia.org/wiki/Category:Data_structures.

Thank you.

--

can someone write a little more about hashed array trees? i don't even understand why it's using a 2-dimensional array whose sub arrays are the same size as the main array 20:34, 27 April 2008 (UTC)

There's more detail in the linked article on DDJ. I do agree the article could do with a little more information. 82.150.248.28 (talk) 07:49, 27 September 2010 (UTC)

Expansions and size reductions

This does not discuss removing elements at all. Size reductions come after removing elements from the HAT; but when removing elements one-by-one, a global move must be done after each removal step, to make it directly addressable again (if not, chunks' fill levels must be kept track of, and access done by e.g. binary search which means O(log n) access time, not O(1) access time).

Another, and related thing is, if no elements need ever be removed, there is no need for global reallocations at all. Powers-of-2 scheme may be abandoned and quotient&remainder used instead for access, still having O(1) access time, and growing the global size by simply adding another chunk to it (with some possible drawbacks on size overhead, but to re-balance that, the global reallocation could be made available as an explicit routine, to be called explicitly). The "directory" array will need to be reallocated on expansions, probably with powers-of-2 scheme, but it can be kept small in size itself with bigger chunks size. I don't know if that was ever published. Maybe in some language manual(s). WillNess (talk) 20:22, 3 November 2011 (UTC)

Actually, the article itself has this, two paragraphs above "Memory Overhead" subsection, as "further optimizations to eliminate copying". WillNess (talk) 22:41, 21 December 2011 (UTC)

Might someone provide an animation illustrating the expansion and reduction processes? Thanks!OlyDLG (talk) 00:19, 23 November 2015 (UTC)

Is it even mathematically proven?

Cannot find any references except for the original article in dr Dobbs, where it seems like an experimental piece of code. Andru nl (talk) 03:58, 29 October 2017 (UTC)