Tuesday, April 11, 2017

Java class for faster searching of substrings in HashMap

Creating objects in Java requires the allocation of system memory, which is a very complex operation, so many algorithms will be faster when it is avoided. This Substring class allows you to search a portion of a String in a HashMap (one with String keys) without having to create any object. Every time the String.substring method is called, a new object is allocated for the substring (only the internal array is shared), so the solution is searching in the HashMap without using a real String as the key, which can be 2 times faster:

...
Substring substr = new Substring();
for (...) { //lots of repetitions
    String str = ...; int start = ...; int end = ...;
    //obj = hmap.get(str.substring(start, end)); //before
    obj = hmap.get(substr.setSubstring(str, start, end));
    if (obj != null) { ... }
}


Because the Java memory management is so efficient, the use of this class will only be faster if your program needs to search for thousands of substrings and you reuse the same Substring object. A similar idea could also be applied to search for the uppercase version of a String in a HashMap without creating new objects (when calling to String.toUpperCase a new object is created if a lowercase character is found). This one is left as an exercise for the reader. Enjoy!

No comments:

Post a Comment