Talk:Hashed array tree: Difference between revisions

Revision as of 20:22, 3 November 2011

Latest revision as of 06:14, 2 February 2024

(4 intermediate revisions by 4 users not shown)

Line 1:

{{WikiProject Computingbanner shell|class=Start|importance=}}

{{WikiProject Computing|importance=}}

}}

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

Line 15 ⟶ 17:

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). [[User:WillNess|WillNess]] ([[User talk: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". [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 22:41, 21 December 2011 (UTC)

Might someone provide an animation illustrating the expansion and reduction processes? Thanks![[User:OlyDLG|OlyDLG]] ([[User talk: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. [[User:Andru nl|Andru nl]] ([[User talk:Andru nl|talk]]) 03:58, 29 October 2017 (UTC)