example - java hashcode vulnerability

Detalle de implementación del método de cambio de tamaño HashMap

Question

Como el título sugiere, esta es una pregunta acerca de un detalle de implementación de HashMap#resize , que es cuando la matriz interna se duplica en tamaño. Es un poco prolijo, pero realmente he intentado demostrar que entendí lo mejor posible esto ...

Esto sucede en un momento en que las entradas en este contenedor / contenedor en particular se almacenan de forma Linked , por lo tanto, tienen un orden exacto y en el contexto de la pregunta esto es importante .

En general, el resize se puede llamar desde otros lugares, pero veamos este caso solamente.

Supongamos que colocas estas cadenas como claves en un HashMap (a la derecha está el hashcode HashMap#hash después de HashMap#hash , esa es la reorganización interna). Sí, estas se generan cuidadosamente, no son aleatorias.

 DFHXR - 11111
 YSXFJ - 01111 
 TUDDY - 11111 
 AXVUH - 01111 
 RUTWZ - 11111
 DEDUC - 01111
 WFCVW - 11111
 ZETCU - 01111
 GCVUR - 11111 

Aquí se observa un patrón simple: los últimos 4 bits son iguales para todos, lo que significa que cuando insertamos 8 de estas claves (hay 9 en total), terminarán en el mismo cubo; y en el noveno HashMap#put , se llamará el cambio de resize .

Entonces, si actualmente hay 8 entradas (con una de las claves anteriores) en el HashMap , significa que hay 16 depósitos en este mapa y los últimos 4 bits de la clave decidieron dónde terminan las entradas.

Ponemos la novena llave. En este punto, se TREEIFY_THRESHOLD y se llama a resize . Los contenedores se duplican a 32 y un bit más de las teclas decide dónde irá esa entrada (entonces, 5 bits ahora).

En última instancia, se alcanza este fragmento de código (cuando ocurre el cambio de resize ):

 Node<K,V> loHead = null, loTail = null;
 Node<K,V> hiHead = null, hiTail = null;
 Node<K,V> next;
 do {
     next = e.next;
     if ((e.hash & oldCap) == 0) {
          if (loTail == null)
               loHead = e;
          else
               loTail.next = e;
          loTail = e;
     }
     else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
     }
 } while ((e = next) != null);



 if (loTail != null) {
     loTail.next = null;
     newTab[j] = loHead;
 }
 if (hiTail != null) {
     hiTail.next = null;
     newTab[j + oldCap] = hiHead;
 }

En realidad no es tan complicado ... lo que hace es dividir la bandeja actual en entradas que se moverán a otras bandejas y a entradas que no se moverán a otras bandejas, pero se mantendrán en esta con seguridad.

Y en realidad es bastante inteligente cómo lo hace, es a través de este código:

 if ((e.hash & oldCap) == 0) 

Lo que esto hace es verificar si el siguiente bit (el 5º en nuestro caso) es en realidad cero: si lo es, significa que esta entrada permanecerá donde está; Si no es así, se moverá con una potencia de dos desplazamientos en el nuevo contenedor.

Y ahora, finalmente, la pregunta: ese fragmento de código en el cambio de tamaño se hace con cuidado para que conserve el orden de las entradas que había en ese contenedor.

Entonces, después de poner esas 9 teclas en el HashMap el orden será:

DFHXR -> TUDDY -> RUTWZ -> WFCVW -> GCVUR (one bin)

YSXFJ -> AXVUH -> DEDUC -> ZETCU (another bin)

¿Por qué querría conservar el orden de algunas entradas en el HashMap ? Ordenar en un Map es realmente malo como se detalla here o here .

Answer 1

El orden en un mapa es realmente malo [...]

No es malo, es (en terminología académica) lo que sea. Lo que Stuart Marks escribió en el primer enlace que publicaste:

[...] preservar la flexibilidad para futuros cambios de implementación [...]

Lo que significa (como lo entiendo) que ahora la implementación sucede para mantener el orden, pero en el futuro, si se encuentra una mejor implementación, se usará para mantener el orden o no.

Answer 2

Hay dos razones comunes para mantener el orden en los contenedores implementados como una lista enlazada:

Una es que mantienes el orden aumentando (o disminuyendo) el valor de hash. Eso significa que al buscar en un contenedor, puede detener tan pronto como el elemento actual sea mayor (o menor, según corresponda) que el hash que se está buscando.

Otro enfoque consiste en mover las entradas al frente (o más cerca del frente) de la cubeta cuando se accede o simplemente agregarlas al frente. Eso se adapta a situaciones donde la probabilidad de que se acceda a un elemento es alta si se acaba de acceder.

He mirado la fuente de JDK-8 y parece que (al menos en su mayor parte) está haciendo la última versión pasiva de la última (agregar al frente):

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

Si bien es cierto que nunca debe confiar en el orden de iteración de los contenedores que no lo garantizan, eso no significa que no se pueda aprovechar para el rendimiento si es estructural. También tenga en cuenta que la implementación de una clase se encuentra en una posición privilegiada para explotar los detalles de su implementación de una manera formal que un usuario de esa clase no debería.

Si observa la fuente y comprende cómo se implementa y explota, está asumiendo un riesgo. Si el implementador lo hace, ¡es un asunto diferente!

Nota: Tengo una implementación de un algoritmo que se basa en gran medida en una tabla hash llamada Hashlife. Utiliza este modelo, tiene una tabla hash que es una potencia de dos porque (a) puedes obtener la entrada mediante enmascaramiento de bits (y máscara) en lugar de una división y (b) el reinicio se simplifica porque solo haces ''descomprimir'' hash-bins.

La evaluación comparativa muestra que el algoritmo gana alrededor del 20% moviendo activamente los patrones al frente de su contenedor cuando se accede.

El algoritmo prácticamente explota estructuras repetitivas en autómatas celulares, que son comunes, así que si has visto un patrón, las posibilidades de volver a verlo son altas.