L'ordine degli elementi in una HashMap differisce quando lo stesso programma viene eseguito in JVM5 rispetto a JVM6

Question

Ho un'applicazione che visualizza una raccolta di oggetti in righe, un oggetto = una riga. Gli oggetti sono memorizzati in una HashMap. L'ordine delle righe non influisce sulla funzionalità dell'applicazione (ecco perché è stata usata una HashMap invece di una collezione ordinabile).

Tuttavia, ho notato che la stessa applicazione viene eseguita in modo diverso quando viene eseguita utilizzando due diverse versioni di Java Virtual Machine. L'applicazione viene compilata utilizzando JDK 5 e può essere eseguita utilizzando runtime di Java 5 o Java 6, senza alcuna differenza funzionale.

L'oggetto in questione ha la priorità su java.lang.Object#hashCode() e ovviamente è stata prestata attenzione a seguire il contratto specificato nell'API Java. Ciò è evidenziato dal fatto che appaiono sempre nello stesso ordine in ogni esecuzione dell'applicazione (nello stesso runtime Java).

Per motivi di curiosità, perché la scelta del runtime Java influisce sull'ordine?

Answer 1

I dettagli di implementazione di HashMap possono essere modificati. Molto probabilmente questo pacchetto metodo privato ha fatto (questo è da 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); 
} 

Per riferimento, l'analogo nel 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

Probabilmente perché un Map non è definito per avere un ordine di iterazione particolare; l'ordine con cui gli elementi ritornano è probabilmente un artefatto della sua implementazione interna e non ha bisogno di rimanere coerente.

Se l'implementazione viene aggiornata tra Java 5 e 6 (soprattutto per motivi di prestazioni), Sun non ha alcun vantaggio o obbligo per assicurarsi che l'ordine di iterazione rimanga coerente tra i due.

EDIT: Ho appena trovato un frammento di interessante in una delle prime Java 6 uscite (purtroppo non sono sicuro della versione esatta, ma è apparentemente HashMap 1.68 da giugno 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); 
} 

Quindi sembra che, nonostante le mie precedenti affermazioni, Sun abbia effettivamente considerato la consistenza dell'ordine di iterazione - in un secondo momento questo codice è stato presumibilmente abbandonato e il nuovo ordine ha fatto il definitivo.

Answer 3

HashMap non è sposato con una particolare l'ordinazione, ma l'implementazione della mappa di LinkedHashMap deve mantenere l'ordine.