CODEWITHSUNDEEP
javahashmap
Sergey Morozov
Sergey Morozov

Reputation: 4628

Why hash table is sorted?

Why hash table(java.util.HashMap) is sorted for long, int, byte and short ?

See code bellow:

public class Main {

    private static final int INITIAL_CAPACITY = 10;

    public static void main(String[] args) {

        final Map<Long, Long> longMap = new HashMap<>(INITIAL_CAPACITY);
        final Map<Integer, Integer> integerMap = new HashMap<>(INITIAL_CAPACITY);
        final Map<Byte, Byte> byteMap = new HashMap<>(INITIAL_CAPACITY);
        final Map<Short, Short> shortMap = new HashMap<>(INITIAL_CAPACITY);

        final Map<Double, Double> doubleMap = new HashMap<>(INITIAL_CAPACITY);
        final Map<Float, Float> floatMap = new HashMap<>(INITIAL_CAPACITY);
        final Map<BigDecimal, BigDecimal> bigDecimalMap = new HashMap<>(INITIAL_CAPACITY);
        final Map<String, String> stringMap = new HashMap<>(INITIAL_CAPACITY);

        final Random random = new Random();

        for(int i=0; i < 100; i++){

            int value = random.nextInt(10);
            longMap.put(Long.valueOf(value), Long.valueOf(value));
            integerMap.put(Integer.valueOf(value), Integer.valueOf(value));
            byteMap.put(Byte.valueOf((byte)value), Byte.valueOf((byte)value));
            shortMap.put(Short.valueOf((short)value), Short.valueOf((short)value));

            doubleMap.put(Double.valueOf(value), Double.valueOf(value));
            floatMap.put(Float.valueOf(value), Float.valueOf(value));
            bigDecimalMap.put(BigDecimal.valueOf(value), BigDecimal.valueOf(value));
            stringMap.put(String.valueOf(value), String.valueOf(value));
        }

        System.out.println("\n========== SORTED ==========\n");
        System.out.println("Map<Long, Long>:             " + longMap);
        System.out.println("Map<Integer, Integer>:       " + integerMap);
        System.out.println("Map<Byte, Byte>:             " + byteMap);
        System.out.println("Map<Short, Short>:           " + shortMap);
        System.out.println("\n======== NOT SORTED ========\n");
        System.out.println("Map<Double, Double>:         " + doubleMap);
        System.out.println("Map<Float, Float>:           " + floatMap);
        System.out.println("Map<BigDecimal, BigDecimal>: " + bigDecimalMap);
        System.out.println("Map<String, String>: " + stringMap);
    }

}

Output this program:

========== SORTED ==========

Map<Long, Long>             : {0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
Map<Integer, Integer>       : {0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
Map<Byte, Byte>             : {0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
Map<Short, Short>           : {0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}

======== NOT SORTED ========

Map<Double, Double>         : {0.0=0.0, 3.0=3.0, 6.0=6.0, 7.0=7.0, 2.0=2.0, 1.0=1.0, 4.0=4.0, 9.0=9.0, 8.0=8.0, 5.0=5.0}
Map<Float, Float>           : {1.0=1.0, 0.0=0.0, 4.0=4.0, 3.0=3.0, 5.0=5.0, 2.0=2.0, 8.0=8.0, 9.0=9.0, 7.0=7.0, 6.0=6.0}
Map<BigDecimal, BigDecimal> : {6=6, 0=0, 5=5, 9=9, 7=7, 8=8, 3=3, 4=4, 2=2, 1=1}
Map<String, String>         : {3=3, 2=2, 1=1, 0=0, 7=7, 6=6, 5=5, 4=4, 9=9, 8=8}

Upvotes: 1

Views: 255

Answers (2)

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 136122

HashMap is not sorted, your results are simply accidental. Try this

    Map<Long, Long> m = new HashMap<>();
    m.put(1001L, 1001L);
    m.put(1000L, 1000L);
    m.put(1002L, 1002L);
    System.out.println(m);

output

{1001=1001, 1000=1000, 1002=1002}

-- no sorting

Upvotes: 2

Jack
Jack

Reputation: 133629

Because for Long, Integer, Byte and Short the overridden int hashCode() method is trivial and returns the numeric value itself. Since the hashcode is used to index the specific bucket in which the element is placed inside the hashmap, a lower hash results in a lower index. Mind that the preserved order is just apparent: by adding other elements to the hash map it's likely that more element will be placed inside the same bucket so what you see is not guaranteed, it is just a side effect that may arise. HashMap is not a sorted collection and you should not use it as such. TreeMap is the way to go when you need sorted pairs.

For Double, Float, BigInteger and String the hash code function is less trivial thus order is not preserved.

Upvotes: 5

Related Questions