HashMap Search for part of an key?

Question

I am currently using HashMap<String, Integer> which is filled with keys of type String which are all, let's say, 5 chars long. How can I search for an specific key of 4 chars or less, which is part and at the beginning of some other keys and get all hits as a collection of <Key, Value>?

You have to iterate through all the HashMap, use `getKey.length()` and add or not (depending on the condition) to a `List<>` — Javier Diaz, May 21 '13 at 07:53
Is it too tough to solve, if yes for you, then at least share what have u tried so far? — Juned Ahsan, May 21 '13 at 07:54
Question: he is looking for entries that have 4 characters instead of 5 characters? Or he is looking for a series of 4 characters which may be within 5 characters? — Menelaos, May 21 '13 at 08:03
@Machtl Is the 4 characters at the beginning or end of string)? Can they be anywhere in the string? — Menelaos, May 21 '13 at 08:15

score 31 · Accepted Answer · edited Aug 09 '17 at 12:55

31

Iterate is your only option unless you create a custom data structure:

for (Entry<String, Integer> e : map.entrySet()) {
    if (e.getKey().startsWith("xxxx")) {
        //add to my result list
    }
}

If you need something more time efficient then you'd need an implementation of map where you are tracking these partial keys.

edited Aug 09 '17 at 12:55

Maytham Fahmi

31,138
14
118
137

answered May 21 '13 at 07:55

cyborg

5,638
1
19
25

Ondrej Bozek · Answer 2 · 2020-12-02T13:07:30.777

6

It seems like a use case for TreeMap rather than HashMap. The difference is that TreeMap preserves order. So you can find your partial match much quicker. You don't have to go through the whole map.

Check this question Partial search in HashMap

edited Dec 02 '20 at 13:07

answered May 21 '13 at 07:58

Ondrej Bozek

10,987
7
54
70

harsh · Answer 3 · 2013-05-21T08:00:59.907

4

You cannot do this via HashMap, you should write your own implementation for Map for implementing string length based searching in a map.

edited May 21 '13 at 08:00

answered May 21 '13 at 07:54

harsh

7,502
3
31
32

Unless ofcourse, he changes the requirements, uses the key with only the 4 characters, and stores the other data in an object in value. Another option is to use a custom Key Object, with custom hashCode() method. – Menelaos May 21 '13 at 08:01
I wouldn't advise rolling one's own Map<>. That's probably overkill (and, besides, composition is often better than inheritance). However, I agree that the data structure, as-is, is not designed to do this. – Michael Aaron Safyan May 21 '13 at 08:03
You don't need to implement all of Map. It is pretty easy to add extra stuff if you use the decorator pattern. So for example I want to log out every key added to a map? Fine, I make my LoggingMap implement Map and then you have to supply the actual instance of the Map it's going to log out. That would work perfectly well in this case except instead of logging you'd keep track of the keys you want in a list or something along those lines. – cyborg May 21 '13 at 08:08
Yes right `Map` implementation can be extension (`extends`) of `HashMap` or other exiting implementations, override only what is required. My point was for this question `Map` seems to be a right data-structure but with some modified `get` (for length based retrieval) and put (for optimal get say `O(1)` again). As all other answers shows external logic as a solution, having a specific `Map` would enforce encapsulating that logic inside map itself. – harsh May 21 '13 at 08:13

score 3 · Answer 4 · answered May 21 '13 at 07:56

Map<String, Integer> result = new HashMap<String, Integer>;
for(String key : yourMap.keySet()) {
    if(key.length() == 4){
        result.put(key, yourMap.get(key);
    }
}

After executing this code you have all key/value pairs with 4 letter keys in result.

score 1 · Answer 5 · answered May 21 '13 at 07:57

Set<Entry<String, Integer>> s1 = map.entrySet();
    for (Entry<String, Integer> entry : s1) {
          if(entry.getKey().length == 4)
          //add it to a map;
}

First get the entry set to your hashmap. Iterate through the set and check the length of each key and add it to a map or use it as u want it.

score 0 · Answer 6 · answered May 21 '13 at 07:54

0

With HashMap<String, Integer> you can only go through keySet() and do contains() for String keys and your pattern.

answered May 21 '13 at 07:54

pbespechnyi

2,251
1
19
29

score 0 · Answer 7 · answered May 21 '13 at 07:59

As has been noted, there isn't a terribly efficient* way to do it with the datastructure you have specified. However, if you add an additional Map<Integer, List<String>> to keep track of the mapping from string length to the list of all keys with that length, then you will be able to do this very efficiently.

*Using just the Map<String, Integer>, you would need to iterate through the entire capacity of the larger map, whereas adding this supplemental datastructure would impose an O(1) lookup (assuming you used a HashMap) followed by iteration through just the result set, which is the fastest possible outcome.

score 0 · Answer 8 · answered May 21 '13 at 08:02

You can try this approach:

public Map<String,Integer> filterMap(Map<String, Integer> inputMap){
    Map<String, Integer> resultHashMap = new HashMap<String, Integer>();
        for (String key : inputMap.keySet()) {
            if(key.length()==5){
                resultHashMap.put(key,inputMap.get(key));
            }   
        }
        return resultHashMap;
    }

HashMap Search for part of an key?

8 Answers8

Linked

Related