CODEWITHSUNDEEP
javahashmapiteration
DevSay
DevSay

Reputation: 1176

Iterate over key-range of HashMap

Is it possible to iterate over a certain range of keys from a HashMap?

My HashMap contains key-value pairs where the key denotes a certainr row-column in Excel (e.g. "BM" or "AT") and the value is the value in this cell.

For example, my table import is:

startH = {
   BQ=2019-11-04, 
   BU=2019-12-02, 
   BZ=2020-01-06, 
   CD=2020-02-03, 
   CH=2020-03-02, 
   CM=2020-04-06
}  

endH = {
   BT=2019-11-25, 
   BY=2019-12-30, 
   CC=2020-01-27, 
   CG=2020-02-24, 
   CL=2020-03-30, 
   CP=2020-04-27
}

I need to iterate over those two hashmap using a key-range in order to extract the data in the correct order. For example from "BQ" to "BT".

Upvotes: 3

Views: 1388

Answers (3)

Zabuzard
Zabuzard

Reputation: 25903

Explanation

Is it possible to iterate over hashmap but using its index?

No.

A HashMap has no indices. Depending on the underlying implementation it would also be impossible. Java HashMaps are not necessarily represented by a hashing-table. It can switch over to a red-black tree and they do not provide direct access at all. So no, not possible.

There is another fundamental flaw in this approach. HashMap does not maintain any order. Iterating it yields random orders that can change each time you start the program. But for this approach you would need insertion order. Fortunately LinkedHashMap does this. It still does not provide index-based access though.

Solutions

Generation

But, you actually do not even want index based access. You want to retrieve a certain key-range, for example from "BA" to "BM". A good approach that works with HashMap would be to generate your key-range and simply using Map#get to retrieve the data:

char row = 'B';
char columnStart = 'A';
char columnEnd = 'M';

for (char column = columnStart; columnStart <= columnEnd; column++) {
    String key = Chararcter.toString(row) + column;
    String data = map.get(key);
    ...
}

You might need to fine-tune it a bit if you need proper edge case handling, like wrapping around the alphabet (use 'A' + (column % alphabetSize)) and maybe it needs some char to int casting and vice versa for the additions, did not test it.

NavigableMap

There is actually a variant of map that offers pretty much what you want out of the box. But at higher cost of performance, compared to a simple HashMap. The interface is called NavigableMap. The class TreeMap is a good implementation. The problem is that it requires an explicit order. The good thing though is that you actually want Strings natural order, which is lexicographical.

So you can simply use it with your existing data and then use the method NavigableMap#subMap:

NavigableMap<String, String> map = new TreeMap<>(...);
String startKey = "BA";
String endKey = "BM";

Map<String, String> subMap = map.subMap(startKey, endKey);
for (Entry<String, String> entry : subMap.entrySet()) {
    ...
}

If you have to do those kind of requests more than once, this will definitely pay off and it is the perfect data-structure for this use-case.

Linked iteration

As explained before, it is also possible (although not as efficient) to instead have a LinkedHashMap (to maintain insertion order) and then simply iterate over the key range. This has some major drawbacks though, for example it first needs to locate the start of the range by fully iterating to there. And it relies on the fact that you inserted them correctly.

LinkedHashMap<String, String> map = ...
String startKey = "BA";
String endKey = "BM";

boolean isInRange = false;
for (Entry<String, String> entry : map.entrySet()) {
    String key = entry.getKey();
    if (!isInRange) {
        if (key.equals(startKey)) {
            isInRange = true;
        } else {
            continue;
        }
    }

    ...

    if (key.equals(endKey)) {
        break;
    }
}

Upvotes: 3

Chris Gerken
Chris Gerken

Reputation: 16392

I don't believe you can. The algorithm you propose assumes that the keys of a HashMap are ordered and they are not. Order of keys is not guaranteed, only the associations themselves are guaranteed.

You might be able to change the structure of your data to something like this:

ranges = {
   BQ=BT, 
   BU=BY, 
   ....
}

Then the iteration over the HashMap keys (start cells) would easily find the matching end cells.

Upvotes: 0

Sid
Sid

Reputation: 4997

// rangeLower and rangeUpper can be arguments
int i = 0;
for (Object mapKey : map.keySet()) {
    if (i < rangeLower || i > rangeUpper) {
        i++; 
        continue;
    }
    // Do something with mapKey
}

The above code iterates by getting keyset and explicitly maintaining index and incrementing it in each loop. Another option is to use LinkedHashMap, which maintains a doubly linked list for maintaining insertion order.

Upvotes: 0

Related Questions