Java LinkedHashSet index validity

Question

I've been porting a big chunk of Java code to C++ and have had to implement things like LinkedHashSet as I've gone. I've made a reasonable facsimile of LinkedHashSet/Map by using Boost's Multi-Index Containers.

As I'm porting the code I'm running into some interesting stuff with multi_index, as contained objects are not mutable (unless you mark specific fields of the class as mutable). However if the key is calculated from some mutable members of the contained class, then things can get interesting.

To clarify some things I thought I'd write a trivial example in Java to check the behaviour of their LinkedHashSet. The results are a little surprising to me; it seems they behave like Boost's Multi Index containers in that indexes aren't regenerated when a contained object is modified (as you might expect); however the compiler doesn't complain in any way---it seems very easy to shoot yourself in the foot (the code I'm porting appears to commit the mentioned sin, who knows how it still works).

Is this just a limitation of the lack of const_iterators in Java, or have I managed to do something particularly stupid or tricky?

Here is the trivial example:

class StringContainer                                                        
{                                                                            
    public String s;                                                         

    public StringContainer(String s)                                         
    {                                                                        
        this.s = s;                                                          
    }                                                                        

    public boolean equals(Object t1)                                         
    {                                                                        
        StringContainer other = (StringContainer) t1;                        
        return this.s == other.s;                                            
    }                                                                        

    public int hashCode()                                                    
    {                                                                        
        int val = 8;                                                         
        for (int i = 0; i < s.length(); i++)                                 
            val += s.charAt(i);                                              
        return val;                                                          
    }                                                                        

    public String toString()                                                 
    {                                                                        
        return s;                                                            
    }                                                                        
}                                                                            

class test                                                                   
{                                                                            
    public static void main(String[] args)                                   
    {                                                                        
        Set<StringContainer> set = new LinkedHashSet();                      
        set.add(new StringContainer("Foo"));                                 
        set.add(new StringContainer("Bar"));                                 
        set.add(new StringContainer("Baz"));                                 
        set.add(new StringContainer("Qux"));                                 


        Iterator<StringContainer> it = set.iterator();                       
        while (it.hasNext())                                                 
        {                                                                    
            StringContainer s = it.next();                                   
            if (s.s == "Baz")                                                
                s.s = "Baz2";                                                
            System.out.println(s);                                           
        }                                                                    

        System.out.println("\nRe-iterate:\n");                               

        it = set.iterator();                                                 
        while (it.hasNext())                                                 
        {                                                                    
            StringContainer s = it.next();                                   
            System.out.println(s);                                           
        }                                                                    

        System.out.println();                                                

        if (set.contains(new StringContainer("Foo")))                        
            System.out.println("Contains Foo");                              

        if (set.contains(new StringContainer("Baz")))                        
            System.out.println("Contains Baz");                              
        else                                                                 
            System.out.println("Does not contain Baz");                      

        if (set.contains(new StringContainer("Baz2")))                       
            System.out.println("Contains Baz2");                             
        else                                                                 
            System.out.println("Does not contain Baz2");                     
    }                                                                        
}

It prints out the following:

Foo
Bar
Baz2
Qux

Re-iterate:

Foo
Bar
Baz2
Qux

Contains Foo
Does not contain Baz
Does not contain Baz2

Interestingly it knows that Baz has changed; however it still doesn't find Baz2.

Obviously this is contrived but the very plausible code I'm looking at seems to (through multiple indirections) cause this problem. With Boost Multi Index at least you have to const-cast an iterator to cause this!

Answer 1

It is ill-advised to use mutable objects in Set (or as keys in Map). As the Javadoc for Set says:

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set.

So your example is directly on-point, and puts your Set in the "behavior...not specified" area.

The underlying reason is exactly as Paul Bellora says in his answer.

Answer 2

Note that LinkedHashSet extends HashSet which simply wraps a HashMap that only cares about its keys. So what we're really talking about here is the behavior of HashMap.

HashMap simply holds references to its keys and is not responsible for tracking when changes are made to those objects. The only time it computes hashes of the keys are when they are put or when the HashMap resizes itself.

Theoretically a custom HashMap implementation that tracked changes to its keys would be possible, but this would be contingent on the keys implementing an interface that fired notifications when their properties were changed. The fact that this custom HashMap could only be used with a specific type of key would make it very specialized.