StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There's no such implementation in the JDK itself. Although <code>TreeMap</code> iterates in natural key ordering, its internal data structures are all based on trees and not arrays (remember that <code>Maps</code> do not order keys, by definition, in spite of that the very common use case).</p> <p>That said, you have to make a choice as it is not possible to have O(1) computation time for your comparison criteria both for insertion into the <code>Map</code> and the <code>indexOf(key)</code> calculation. This is due to the fact that lexicographical order is not stable in a mutable data structure (as opposed to insertion order, for instance). An example: once you insert the first key-value pair (entry) into the map, its position will always be one. However, depending on the second key inserted, that position might change as the new key may be "greater" or "lower" than the one in the <code>Map</code>. You can surely implement this by maintaining and updating an indexed list of keys during the insertion operation, but then you'll have O(n log(n)) for your insert operations (as will need to re-order an array). That might be desirable or not, depending on your data access patterns.</p> <p><code>ListOrderedMap</code> and <code>LinkedMap</code> in Apache Commons both come close to what you need but rely on insertion order. You can check out their implementation and develop your own solution to the problem with little to moderate effort, I believe (that should be just a matter of replacing the <code>ListOrderedMap</code>s internal backing array with a sorted list - <code>TreeList</code> in Apache Commons, for instance).</p> <p>You can also calculate the index yourself, by subtracting the number of elements that are lower than then given key (which should be faster than iterating through the list searching for your element, in the most frequent case - as you're not comparing anything).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload