Can I use HashMap of characters in place of String?

Question

I want to have a function to build a String from inputted characters and stop building if it gets an input character that it contains.

I know I can use String.contains() for this but I am learning about HashMaps and am wondering if a faster way to do this could be storing the inputted characters in a HashMap and using the HashMap.contains() method.

Interesting idea. A few problems I can think of: The hashmap doesn't maintain order by default, so there is a lot of custom handling involved; converting back to a string for example requires a lot of overhead; you need a lot of characters (few thousend) for the hashmap to outperform an iterative approuch (which string is by default); when `contains` is not used A stupidly amount of times, it propably isn't worth the extra performance needed to create the hashmap-string in the first place — n247s, Dec 01 '21 at 07:15
If your string is, say, just a few hundred chars long, performance won’t matter. — Ole V.V., Dec 01 '21 at 07:41

Junior Dussouillez · Answer 1 · 2021-12-01T07:32:28.387

HashMap::containsKey is O(1), String::contains is not. The implementation may change dependending of the JVM version but it's more something like O(n).

So yes, using an HashMap to look for a value should be faster (on small data you'll probably don't notice a difference) than calling String::contains. But a Map stores a key and a value, if you don't care about the value, you can use a Set (be careful, all the values are unique in this type of collection) because Set::contains is O(1).

As @n247s mentionned in the comment. Except if you really have a performance issue, String::contains should works fine and make the code simpler to read.

score 1 · Accepted Answer · answered Dec 01 '21 at 07:23

A Set would be a good data structure to use here.

Just take note of 1 thing though,

If you need case-sensitive search then you can use a HashSet. Example

Set<String> set = new HashSet<>();

Else, if you need case-insensitive search then a TreeSet. Example

Set<String> set = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);

score 0 · Answer 3 · answered Dec 01 '21 at 07:18

HashMap<> is just a class that extends the Map<> interface, you can use containsKey() or containsValue(). If you want to loop through the values in the HashMap, you can use the HashMaps.values() method and concat/add the value to the String.

UNTESTED:

int count = -1;
String new = "";
for (char c : map.values()) {
    count++;
    if (string.charAt(count).equals(c))
      break;
    new.concat(c);
}

score 0 · Answer 4 · answered Dec 01 '21 at 07:25

The best Approach would be to use a Set if you do not care about insertion order, but if you do, there is a LinkedHashSet you should use, that will keep your characters in order of insertion.

Here is a link to the LinkedHashSet doc. https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html

But if you actually want to use the key / value pair of the HashMap, you can indeed use a HashMap<Character, Character>, then you can check with map.containsKey() O(1), and map.containsValue() O(n) keep in mind since containsValue() will use O(n), it's better to just check String::contain in that scenario. And if you care about insertion order, there is also a LinkedHashMap that will do that for you. Link to the doc bellow https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

Can I use HashMap of characters in place of String?

4 Answers4