How do i parse a map (foreach) in the same order i created it (JAVA)

Question

So i have a map that i created (inserted data) in an order i wanted. When parsing the map the 1st key returned in foreach is not the first key i inserted. Is there a way for that to happen?

Also sorting my map is kinda tricky cause it has to be sorted by Value and in specific field within the Value. Ty

Answer 1

Check out http://java.sun.com/j2se/1.4.2/docs/api/java/util/LinkedHashMap.html for a Map implementation with predictable iteration order. You also might consider just using a List if you're not actually doing lookup by keys.

Answer 2

If you can sort your items up front by the value attribute, then you can use a LinkedListHashMap, since that preserves the order you specify. However, this seems a bit fragile, and is not suitable if you need to later add more items to the map.

The alternative is to store the values in a list, sorted as you need, and use binary search to retrieve items and find the insertion point for new items.

You can even wrap all this and put it behind a Map interface.

The Collections class provides binarySearch. Here's an outline:

• Put your Value class in a list, List<Value> values.
• Implement a Comparable<Value> class that compares values using the attribute you want to sort them on.
• Use Comparator<Value> to sort the list.
• Now that the list is sorted, you can use Collections.binarySearch(values, aValue, Comparator<Value>) to find the index of the actual value. Note that aValue isn't a real value - it's a value with the attributes set to provide the key, but the rest of it is uninitalized. The aValue is only used to hold the sort key.

In code

List<Value> values = new ArrayList<Values>();
// .. add values
values.add(new Value(key, data1, data2, etc..));
Comparator<Value> compValue = new Comparator<Value>() {
  public int compare(Value v1, Value v2) {
     return v1.getKey()>v2.getKey();
  }
}

Collections.sort(values, compValue);
// now we can search on key
int index = Collections.binarySearch(values, new Value(keyTofind), valueComp);
Value foundValue = null;  // value with the key may not be in the list
if (index>=0) 
   foundValue = values.get(index);

// we can also update the list
Value newValue = new Value(key, data, data2, etc...);
int insert = Collections.binarySearch(values, newValue, valueComp);
// insert will be negative
values.add((-insert)-1, newValue);

EDIT: If you wrap this up in a Map interface, e.g. extending AbstractMap, it will be serializable.

Answer 3

Let's see. Your requirements seem to be:

1. You have a set of key / value pairs, where the keys are unique.
2. You want to be able to do fast lookup of the value for a given key.
3. You want to be able to iterate over the keys (or pairs) in insertion order.
4. You want to be able to iterate over the values in order of some field of the value type.

There is no single standard Java collection class that satisfies all of these requirements. And I don't think that Commons collections or Google collections would either ...

If you were to throw out requirement 3, then a TreeSet (instantiated with a custom Comparator) would do the job. If you were to throw out requirement 4, then a LinkedHashMap would do the job.

To satisfy all requirements you need to do one of the following:

• Use a LinkedHashMap, and when you want to iterate in some order dependent on the values extract the map's values collection, sort it using your custom comparator, and return an iterator for the sorted collection.

• Use both a LinkedHashMap and a TreeMap, and update the two in parallel.

• Create a custom fascade class for a LinkedHashMap and a TreeMap. This needs to keep both data structures up to date when you call put, remove etcetera, and also provide extra methods for getting the sorted values.