Java Hashmap's key is not in the hashmap-CodePudding

I'm working on a small program in java to create access list for a firewall based on netflow data.

In a nutshell, I have a hashmap called sourceAggregatedFlows, that contains source IP Groups (Custom object) as keys and the destination IP addresses as values

private static Map<List<IPGroups>, String> sourceAggregatedFlows = new HashMap<List<IPGroups>, String>();

At a point in my code, I need to iterate through the source IP groups and determine if the destination address in the value of a key matches the address that I'm searching for.

I've noticed an issue, that sometimes iterating through the keyset would give a nullpointer exception on the value. I've started debugging and found out, that this piece of code:

if (sourceAggregatedFlows.containsValue(destination)) {
    for (List<IPGroups> sources : sourceAggregatedFlows.keySet()) {
        System.out.println(sourceAggregatedFlows.containsKey(sources));
    }
}

somehow is able to print out this:

false
true
true

Looking at the debugger, everything seems to be fine. The hashmap contains 3 non-null keys with 3 non-null values

The Value of the destination variable (String) is at this point the same as the 1st value in the HashMap. I've checked it with the debugger tool also and it the sources variable seemed to perfectly match with the 1st key in the hashmap, but for some reason it still outputted false at the end.

This seems to be an impossible scenario for me, because I haven't experienced anything like this in a single threaded program.

It might be that my programming skills got a bit rusty, but I have no clue wat could cause this, but it doesn't even happen all the time. It always happens at the same point in my program, when the destination variable and the 1st value of the hashmap is "172.24.22.54". Before this happens it performs twice (in the same run) as expected.

Does anyone have an experience with anything like this? Could this be a buggy version of Java, or am I missing something?

CodePudding user response：

I believe that the problem you are experiencing is because your HashMap keys (i.e. the lists) are not immutable.

If you do a hash and then change the key, you will not necessarily be able to find the value

CodePudding user response：

You can't use non-stable objects as keys in a map. When you do use non-stables, you get this exact behaviour: Keys that can be 'observed' with iterators but which cannot be observed at all with .containsKey, .get, .computeIfAbsent, or any other 'pinpoint' method.

A non-stable object is one whose hashCode changes after adding it to the map. This can be because hashCode is inherently unstable (which makes it completely useless and means your hashCode impl is just broken; fix it), or because the object is mutable, and you mutate it afterwards.

That last point is 99% certain what happened here. You did this:

Make a list.
Add it to the map as key.
Add or remove something from the list.

You can't do that. There's no easy fix. One solution is:

Anytime you want to mutate a list...
remove the k/v pair from the map before mutating.
mutate it
Add it right back in.

Another is to simply not use something you want to mutate as key; instead, use something else as key that is stable and then have 2 maps. One maps the stable key to your List<IpGroup> and the other maps your stable key to String (replaces the map you currently have).

The reason is simple:

Hashmap works as follows: To store anything, it takes the key and asks for its hashCode. It then finds the right 'bucket' for that hashcode and sticks the key in that bucket.

To look up a key, e.g. to do map.get(k), hashmap asks 'k' for its hashCode, and then looks only in that bucket and no others.

So, if you put an object in when it has hashcode 1234, it goes in bucket 1200-1300. If later that same object's hashCode() now returns 4321, and you call map.get(k), hashmap looks in bucket 4300-4400, doesn't find it, and goes: No, that is not in here!

CodePudding user response：

The objects that you're using the keys of a Map should be immutable because hash of each key in a map is being calculated only once. In case if a mutable key changes, its hash would change as well, and it would no longer match to the hash stored in the map.

Here is how Node of HashMap is implemented:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // <- pay attention to this line
    final K key;
    V value;
    Node<K,V> next;

    // the rest code
}

If you need to use a List as a key, you need to either make it immutable manually or wrap it a class which would ensure that.

public class MyKey<T> {
    private List<T> items;

    public MyKey(List<T> items) {
        this.items = Collections.unmodifiableList(items);
    }
}