Question

***********Java Programming**********

I would like to use a data structure that can be resized at run time and is efficient in memory and can be printed out in order. Give an example of any Java implementation of a data structure that fits this description and tell how it can be used.

Answer 1

If the total size is known, ahead of time, or if O(n) insertions due to resizing (but still O(1) amortized in the average case) are fine, then hash table is the best option. The one-time hit of copying the whole table when resizing can also be distributed over several operations by usingincremental resizing.

Hash table should be partially empty to avoid collisions, which may feel like wasting memory. But with tree-based maps, we usually have at least one additional pointer per item, which will also “waste” a significant amount of memory. Also, with a hash table, we can tweak how much of it to keep empty, partially trading performance for memory (or vice versa).

But there also is a tree-based data structure optimized for looking up recently accessed keys: splay tree. It uses rotations to keep recently used keys near the root, while still maintaining amortized worst case of O(log n) for insertion and searching. (That “amortized” bit is important, some operations can still be O(n)).