Content deleted Content added
No edit summary |
→Expansions and size reductions: new section |
||
Line 9:
: There's more detail in the linked article on DDJ. I do agree the article could do with a little more information. [[Special:Contributions/82.150.248.28|82.150.248.28]] ([[User talk: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). [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 20:22, 3 November 2011 (UTC)
| |||