Hashtable keys get reordered when iterating

Question

I'm trying to learn Java and got an exercise which is to get the first unique item in a string. I used HashTable as the string's characters as the key and counter of how many times it has been seen in the string as the value.

After that, I'm iterating over the HashTable and checking for each key if it has a value of 1 (only seen once) I want to return it. The problem is, when I have a string like this for example abcdcd a and b are both unique, but a is the first one, but for some reason, when I get the keys on the HashTable, the b comes before a.

This is what I have:

    public static Character firstNonRepeatedCharacter(String str) {
    Hashtable<Character, Integer> characters = new Hashtable<Character, Integer>();
    char[] charsInString = str.toCharArray();

    for(int i=0; i<charsInString.length; i++){
        if (characters.containsKey(charsInString[i])){
            int counter = characters.get(charsInString[i]);
            counter ++;
            characters.put(charsInString[i], counter);
        }else {
            characters.put(charsInString[i], 1);
        }
    }

    Enumeration<Character> enumeration = characters.keys();
    while(enumeration.hasMoreElements()) {
        Character key = enumeration.nextElement();
        if(characters.get(key) == 1) {
            return key;
        }
    }

    return null;

}

Why is that happening?

1. `Hashtable` (and most other `Map` implementations) don't have a defined order to them, they only do mapping, the iteration order should be considered effectively random. 2. `Hashtable` and `Enumeration` are ancient classes that have been effectively replaced by `HashMap` and `Iterator` from the collections framework, if your course/learning source pointed you towards `Hashtable` then it's almost certainly ancient and should be avoided. — Joachim Sauer, Mar 27 '20 at 14:28
`Hashtable` and `HashMap` use the key `hashCode()` to place entries in buckets. If you need iteration order to match insertion order, use a `LinkedHashMap`. `HashMap` should be used in preference to `Hashtable` (and `Iterator` over `Enumeration`). This code looks **old**. — Elliott Frisch, Mar 27 '20 at 14:29
The order in a HashTable (or better, a HashMap) is *never* guaranteed. If you want hashing functionality in a collection that preserves insertion order, use a LinkedHashMap. If you want sorted order, use a TreeMap. — Hovercraft Full Of Eels, Mar 27 '20 at 14:29

score 0 · Answer 1 · answered Mar 27 '20 at 14:35

HashTable is a dictionary, like a Set, it does not mind any order like with comparators nor insertion order...

You must use a LinkedHashMap because it keeps the insertion order similar to any LinkedList does.

A workaround: If you want to use yes or yes a HashTable you can create a List with the keys and then iterate the list getting the values from the HashTable. An example:

Hashtable<Character, Integer> characters = new Hashtable<Character, Integer>();
List<Character> list = new LinkedList<>();
[...]
foreach(Character c: list){
 if(characters.get(c) == 1) {
            return c;
  }
}

Hashtable keys get reordered when iterating

1 Answers1