Original HashMap is modified

Question

I have a method which looks for the smallest substring from the input string which contains group of A, C, G, T letters.

My question has nothing to do with the algorithm.

I would like to keep original HashMap and assign it to the modified map at the end of the outer for-loop, but the original HashMap is modified even though I never modify the originalMap in the code.

I am not sure if I am doing wrong.

Code:

void find2(String string) {
    int n = string.length();
    int occurrence = n / 4;
    Map<Character, Integer> cache = new HashMap<Character, Integer>();
    char[] original = { 'A', 'C', 'G', 'T' };
    for (char c : original) {
        cache.put(c, 0);
    }
    char[] chars = string.toCharArray();
    char[] modifiableChars = string.toCharArray();

    HashMap<Character, Integer> countMap = new HashMap<Character, Integer>();
    for (int ii = 0; ii < string.length(); ii++) {
        char currentChar = chars[ii];
        if (!countMap.containsKey(currentChar)) {
            countMap.put(currentChar, 1);
        } else {
            Integer count = countMap.get(currentChar);
            count++;
            countMap.put(currentChar, count);
        }
    }
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    HashMap<Character, Integer> originalMap = new HashMap<Character, Integer>();
    for (int ii = 0; ii < string.length(); ii++) {
        char c = string.charAt(ii);
        if (!map.containsKey(c)) {
            map.put(c, 1);
        } else {
            Integer count = map.get(c);
            count++;
            map.put(c, count);
        }
        if (!originalMap.containsKey(c)) {
            originalMap.put(c, 1);
        } else {
            Integer count = originalMap.get(c);
            count++;
            originalMap.put(c, count);
        }
    }
    int min = 0;
    for (int i = 0; i < chars.length; i++) {
        int change = 0;

        int checkCount = countMap.get(chars[i]);
        if (checkCount <= occurrence) {
            continue;
        }



        boolean isValidated = false;
        int j = i;
        for (j = i; j < chars.length; j++) {
            char c = chars[j];
            int count = map.get(c);
            if (count > occurrence) {

            }
            char nextChar = getNextChar(map, cache, occurrence);
            if (nextChar == ' ') {
                continue;
            }
            Integer nextCharCount = map.get(nextChar);
            nextCharCount++;
            map.put(nextChar, nextCharCount);
            chars[j] = nextChar;

            if (c != nextChar) {
                Integer currentCount = map.get(c);
                currentCount--;
                map.put(c, currentCount);
            }

            change++;
            // validate the characters.
            if (isValid(chars, occurrence)) {
                isValidated = true;
                break;
            }
        }
        if (isValidated) {
            if (min == 0) {
                min = change;
            } else {
                min = Math.min(min, change);
            }
        }
        chars = string.toCharArray();
        map = originalMap; // <--------
    }
    System.out.println(min);
}

`a = someMap` does not create a copy of `someMap` if that's the question. If you want a copy, use https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#HashMap-java.util.Map- — , Sep 20 '16 at 05:51
a gist of what this piece of code is suppose to do? You mentioned you didn't modify `originalMap` but I'm seeing code like `originalMap.put(c, 1);` — Samuel Kok, Sep 20 '16 at 05:59
the for-loop below the 'HashMap originalMap = new HashMap();' is initializing the originalMap to contain the original count of each letter, because 'map' is modified. — user826323, Sep 20 '16 at 06:05

score 0 · Accepted Answer · answered Sep 20 '16 at 06:06

0

I think you should do

Map map = new HashMap(); // generic later
map.putAll(originalMap);

instead of

map = originalMap;

this only changes the reference to point to original hashmap. So in the second iteration original hashmap is modified. what you need is to create copy.

answered Sep 20 '16 at 06:06

Suraj

184
1
14

Ah.. I see why.. thanks. – user826323 Sep 20 '16 at 06:08
please accept it as answer. If it solves the problem – Suraj Sep 20 '16 at 06:13
1

What if `map` is ahead of `originalMap` by some extra entries. Will `putAll` discard them at first? No, it won't. You may or may not have unintended entries after `putAll` operation. So, it's NOT a safe option. – Saurav Sahu Sep 20 '16 at 06:29
@Saurav Sahu is right btw. putAll doesnt remove old entries. Thanks for pointing out. – Suraj Sep 20 '16 at 06:29

score 0 · Answer 2 · edited May 23 '17 at 12:24

Create a new hashmap which is copy of original one, at the very beginning while entering inside the for loop:

Map<SomeType, OtherType> map1 = new HashMap<SomeType, OtherType>(original);

I would not recommend using putAll as it doesn't discard the already present entries in the target hashmap. Demo

   HashMap newmap1 = new HashMap();
   HashMap newmap2 = new HashMap();

   // populate hash map
   newmap1.put(1, "tutorials");
   newmap1.put(2, "point");
   newmap1.put(3, "is best");
   newmap2.put(5, "Foo");

   System.out.println("Values in newmap1: "+ newmap1);
   System.out.println("Values in newmap2: "+ newmap2);   
   newmap2.putAll(newmap1);
   System.out.println("Values in newmap2: "+ newmap2);

Gives output as :

Values in newmap1: {1=tutorials, 2=point, 3=is best}
Values in newmap2: {5=Foo}
Values in newmap2: {1=tutorials, 2=point, 3=is best, 5=Foo}

As you can see the entry {5, "Foo"} remained intact after using putAll, which is not expected when you wish to regain the original hashmap.

EDIT:

As, it is suggested to avoid new map instance creation as much as possible, use .clear() + .putAll() operations at the end of for loop.

score 0 · Answer 3 · answered Sep 20 '16 at 06:36

The other answers where map is created at the start of the loop with a copy of the original map is nicer, but following the existing logic:

    map = originalMap; // <--------

should become

    map.clear();
    map.putAll(originalMap);

And a couple of tips:

HashMap<Character, Integer> countMap = new HashMap<Character, Integer>();

can become the more abstract Map, and the inferred types <>

Map<Character, Integer> countMap = new HashMap<>();

With java 8:

    if (!countMap.containsKey(currentChar)) {
        countMap.put(currentChar, 1);
    } else {
        Integer count = countMap.get(currentChar);
        count++;
        countMap.put(currentChar, count);
    }

can become a one-liner

    countMap.merge(currentChar, 1, Integer::add);
                   ===========  =  ============
                    |           |     |
                    |           |    function(old, 1) when old value exists
                    |           |    returns new value or null to delete
                    |           |
                    |          new value when no value (or null value)
                   key

This is where I find C++ little convenient, just do `++mymap[key]` and all is good. :) — Saurav Sahu, Sep 20 '16 at 06:43

Original HashMap is modified

3 Answers3