Why is HashMap automatically sorted by key (alphabetically)?
The program calculates the probability of finding one or another character in a string.

 String givenString=in.nextLine(); char[] charArray = givenString.toCharArray(); double s=1; double prom; HashMap<Character, Double> probability2 = new HashMap<>(); for(int i=0;i<charArray.length;i++) { for(int j=1;j<charArray.length;j++) { if(charArray[i]==charArray[j]) s++; } if (!probability2.containsKey(charArray[i])) { prom=s/charArray.length; probability2.put(charArray[i],prom); } s=0; } for (Map.Entry entry : probability2.entrySet()) { System.out.println("Key: " + entry.getKey() + " Value: " + entry.getValue());} }

For example, if "cccbbbbaaa" is entered, then the output is a-0.3, b-0.4, c-0.3. I was expecting s-0.3, b-0.4, a-0.3

  • five
    The order of the keys is not guaranteed; it may change the next time you start the program, when updating the JVM, or under any other conditions. - Sergey Gornostaev
  • What data is given to the program at the entrance? What are the output? What is going wrong? - default locale
  • Let me enter the string cccbbbbaaa. There is a-0.3, b-0.4, c-0.3 at the output. I was expecting s-0.3, b-0.4, a-0.3 - karimzhanov.amir
  • In the example, probability2 and probability are confused by default locale
  • I made a mistake when the code I edited there was sorting for the probability, but it was also odd - karimzhanov.amir

3 answers 3

It's just a very beautiful edge case. The Hashcode Character is the value directly wrapped in it :

 public int hashCode() { return Character.hashCode(value); } public static int hashCode(char value) { return (int)value; }

Thus, hashCode (a) = 97 or 0x61, b -> 0x62, c -> 0x63. HashMap also chooses buckets as follows:

  public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#610

The XOR is needed so that the upper bits also participate in the choice of the bake, because otherwise they are ignored (n is the number of buckets):

 tab[i = (n - 1) & hash]

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#629

Since we have a hash in this example is 0x61..0x63, all high bits are zero and play no role when hashing is mixed. The very operation of selecting a bake consists of simply discarding the higher bits of the obtained value. Thus, with any number of buckets> 2, these hashcodes guarantee getting into three consecutive bakes, because if we look at the last four bits of these hashcodes, we will see the following picture:

 a 0001 b 0010 c 0011

if n> = 100 (four buckets or more), then these bits, which are responsible for the distribution, will always be preserved. The number of buckets by default is 16, which leads to the picture described.

I repeat that this is an edge case, and one cannot expect such behavior in general

    To display items in a predictable order, use LinkedHashMap .

     HashMap<Character, Double> probability2 = new LinkedHashMap<>();

    This collection displays the elements in the order in which they were added:

    Hash table and linked list implementation with the predictable iteration order. This implementation differs from HashMap in that it maintains a list-linked list running through all of its entries. This is where the ordering keys were inserted into the map (insertion-order). If the key is re-inserted into the map.

    Pay attention to the last line: if an element is added (using put ) several times, then only the first one is considered.

    HashMap does not guarantee order when withdrawing. From the documentation:

    This is a map; in particular, it does not guarantee that the order will remain constant over time.

    I.e:

    • There is no guarantee that the collection will be sorted by keys.
    • There is no guarantee that the collection will not be sorted by keys.
    • There is no guarantee that the order of the elements will be maintained.

    For example, for the string "dg" the order will be reversed.

    In practice, the order of the elements will be reproducible (because the random order is not required of the HashMap ), but this is nowhere guaranteed.

      HashMap stores keys in order, depending directly on their hash codes. It is quite likely that a series of keys will be displayed in ascending or descending order, but this is only a matter of chance.