Mistake in hashCode() implementation in some classes

[davidalain]

Those implemented hashCode() methods in some classes generate the same output (hash collision) when swapping multiplying operands. An incorrect implementation of hashCode() and equals() methods may cause errors that are hard to debug when a class is used as a Map key.

I have searched by this usage and I found the following classes with that mistake:

• Turn.java
• Path.java

For example, in Turn class we have:

public int hashCode() {
        return (int) src.hashCode() * dest.hashCode();
}

This hashCode implementation will generate same output value when swapping src to dest.

The following classes are using a Turn object as a Map key.

• ArrivalBoundCache.java: line 44.
• ServerGraph.java: line 83.
• PmooSinkTreeAffineABCache.java: line 209.

A simple way to fix this is by using Objects.hash(...) method with the class attributes:

public int hashCode() {
        return Objects.hash(src, dest);
}

Also, other classes are using the hashCode() method with multiplying. It is recommended to fix them using Objects.hash(...) method instead of multiplying attribute values.

[davidalain]

There are some usages of HashSet instantiation with class 'T' without overwritting hashCode() method. This may cause the same problems with cloned objects.

Objects with same content must output the same hashCode() value, but without overwritting hashCode() on them they will output different hashCode() values because the default hashCode() implementation (from Object class) uses the address memory to compute the hash value.

I'm working on this fixing.

[davidalain]

@sbondorf @matyesz

I found also some other classes used as HashMap key that does not have hashCode() method overwritten.

To fix these issues, I need to know what attributes of the following classes you consider being key attributes to differentiate an instance from another:

• Server.java
• Flow.java

Other objects used as Map key or Set key are enums, but enums values are all constants and do not suffer from this hashCode() issue.

[sbondorf]

My suggestion is to check if the class overrides Object's equals method.

equals not overwritten: Two servers or two flows are always different. Either needs to be created by the network instance it belongs to. That network instance then gives them a unique ID to differentiate them despite otherwise equal attributes set by the user. So, I guess a hash based on address memory should be fine here.

Turn overwrites the equals method. There should not be two turns with the same source and destination. So it need to be treated differently. As for the hash, can we simply use a non-commutative operation instead of the multiplication of hash codes? E.g., String concatenation?

Path overwrites the equals method, too. It is all about the order of servers and turns that are taken. Therefore, either is stored in a List. This order property should make the hash code unique despite using the multiplication, right?

[davidalain]

Like you suggested, all instances of Server and Flow must be unique (even they have beeing attributes with the same values), then using default hashCode (that uses address memory) is fine.

Turn and Path match this case. Also, they have hashCode (that was fixed on #81).

AnalysisConfig does not have equals overwritten, but it has copy method. On my fixing, I have implemented hashCode and equals based on the same attributes used in copy method.

I think AnalysisConfig is the only class remaining hashCode fixing. I made a pull request with these modifications.

DNC code is:

/**
 * Returns a deep copy of this analysis configuration.
 *
 * @return The copy.
 */
public AnalysisConfig copy() { // deep copy as primitive data types are copied by value
    return new AnalysisConfig(multiplexing_enforcement, enforce_max_sc, enforce_max_sc_output_rate, arrival_bound_methods,
            convolve_alternative_arrival_bounds, server_backlog_arrival_bound);
}

My modifications are:

@Override
public int hashCode() {
    return Objects.hash(multiplexing_enforcement, enforce_max_sc, enforce_max_sc_output_rate, arrival_bound_methods,
            convolve_alternative_arrival_bounds, server_backlog_arrival_bound);
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    AnalysisConfig other = (AnalysisConfig) obj;

    return Objects.equals(this.multiplexing_enforcement, other.multiplexing_enforcement) &&
            Objects.equals(this.enforce_max_sc, other.enforce_max_sc) &&
            Objects.equals(this.enforce_max_sc_output_rate, other.enforce_max_sc_output_rate) &&
            Objects.equals(this.arrival_bound_methods, other.arrival_bound_methods) &&
            Objects.equals(this.convolve_alternative_arrival_bounds, other.convolve_alternative_arrival_bounds) &&
            Objects.equals(this.server_backlog_arrival_bound, other.server_backlog_arrival_bound);
}   

[NetCal]

PR #81 needs forward-porting to the master branch.

[davidalain]

Fixed in #84