Talk:Hashed array tree

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.

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)[reply]

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)[reply]

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)[reply]