Порядок элементов в HashMap отличается, когда одна и та же программа выполняется в JVM5 или JVM6

Question

У меня есть приложение, которое отображает коллекцию объектов в строках, один объект = одна строка.Объекты хранятся в хэш-карте.Порядок строк не влияет на функциональность приложения (именно поэтому вместо сортируемой коллекции была использована HashMap).

Однако я заметил, что одно и то же приложение работает по-разному при запуске с использованием двух разных версий виртуальной машины Java.Приложение скомпилировано с использованием JDK 5 и может быть запущено с использованием сред выполнения Java 5 или Java 6 без каких-либо функциональных различий.

Рассматриваемый объект переопределяет java.lang.Object#hashCode() и, очевидно, были приняты меры для соблюдения контракта, указанного в Java API.Об этом свидетельствует тот факт, что они всегда появляются в одном и том же порядке при каждом запуске приложения (в одной и той же среде выполнения Java).

Ради любопытства, почему выбор среды выполнения Java влияет на порядок?

Answer 1

Детали реализации HashMap можете меняться и делаете это.Скорее всего, это сделал частный метод этого пакета (это из JDK 1.6.0_16):

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Для справки, аналогом в JDK 1.5.0_06 является:

/**
 * Returns a hash value for the specified object.  In addition to 
 * the object's own hashCode, this method applies a "supplemental
 * hash function," which defends against poor quality hash functions.
 * This is critical because HashMap uses power-of two length 
 * hash tables.<p>
 *
 * The shift distances in this function were chosen as the result
 * of an automated search over the entire four-dimensional search space.
 */
static int hash(Object x) {
    int h = x.hashCode();

    h += ~(h << 9);
    h ^=  (h >>> 14);
    h +=  (h << 4);
    h ^=  (h >>> 10);
    return h;
}

Answer 2

Вероятно, потому, что Map не определено, чтобы иметь какой-либо определенный порядок итерации;порядок, в котором элементы возвращаются, скорее всего, является артефактом его внутренней реализации и не обязательно должен оставаться последовательным.

Если реализация обновляется между Java 5 и 6 (особенно по соображениям производительности), Sun не имеет никакой выгоды или обязанности следить за тем, чтобы порядок итераций оставался согласованным между ними.

Редактировать:Я только что нашел интересный фрагмент в одном из ранних выпусков Java 6 (к сожалению, я не уверен в точной версии, но, по-видимому, это HashMap 1.68 от июня 2006):

 /**
  * Whether to prefer the old supplemental hash function, for
  * compatibility with broken applications that rely on the
  * internal hashing order.
  *
  * Set to true only by hotspot when invoked via
  * -XX:+UseNewHashFunction or -XX:+AggressiveOpts
  */
 private static final boolean useNewHash;
 static { useNewHash = false; }

 private static int oldHash(int h) {
     h += ~(h << 9);
     h ^= (h >>> 14);
     h += (h << 4);
     h ^= (h >>> 10);
     return h;
 }

 private static int newHash(int h) {
     // This function ensures that hashCodes that differ only by
     // constant multiples at each bit position have a bounded
     // number of collisions (approximately 8 at default load factor).
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
 }

Таким образом, похоже, что, несмотря на мои вышеприведенные утверждения, Sun действительно учитывала согласованность порядка итераций - в какой-то более поздний момент этот код, по-видимому, был удален, и новый порядок стал окончательным.

Answer 3

HashMap не привязан к какому-либо конкретному порядку, но LinkedHashMap - Связанная карта реализация Map должна сохранять порядок.