vulnerability - object equals java

¿Por qué no funciona el caché hashCode() de String 0?

Question

Observé en el código fuente de Java 6 para String que hashCode solo almacena valores en caché que no sean 0. La diferencia en el rendimiento se muestra en el siguiente fragmento:

public class Main{
   static void test(String s) {
      long start = System.currentTimeMillis();
      for (int i = 0; i < 10000000; i++) {
         s.hashCode();
      }
      System.out.format("Took %d ms.%n", System.currentTimeMillis() - start);
   }
   public static void main(String[] args) {
      String z = "Allocator redistricts; strict allocator redistricts strictly.";
      test(z);
      test(z.toUpperCase());
   }
}

Ejecutando esto en ideone.com da el siguiente resultado:

Took 1470 ms.
Took 58 ms.

Entonces mis preguntas son:

• ¿Por qué no funciona el caché hashCode () de String 0?
• ¿Cuál es la probabilidad de que una cadena de Java se nutra a 0?
• ¿Cuál es la mejor manera de evitar la penalización de rendimiento de volver a calcular el valor hash cada vez para cadenas que hash a 0?
• ¿Es esta la mejor práctica de los valores de almacenamiento en caché? (es decir, ¿caché todo menos uno?)

Para tu diversión, cada línea aquí es una cadena que tiene hash a 0:

pollinating sandboxes
amusement & hemophilias
schoolworks = perversive
electrolysissweeteners.net
constitutionalunstableness.net
grinnerslaphappier.org
BLEACHINGFEMININELY.NET
WWW.BUMRACEGOERS.ORG
WWW.RACCOONPRUDENTIALS.NET
Microcomputers: the unredeemed lollipop...
Incentively, my dear, I don''t tessellate a derangement.
A person who never yodelled an apology, never preened vocalizing transsexuals.

Answer 1

• ¿Por qué no funciona el caché hashCode () de String 0?

El valor cero está reservado para significar que "el código hash no está en la memoria caché".

• ¿Cuál es la probabilidad de que una cadena de Java se nutra a 0?

De acuerdo con el Javadoc, la fórmula para el código hash de una cadena es:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

usando int arithmetic, donde s[i] es el i-ésimo carácter de la cadena y n es la longitud de la cadena. (El hash de la Cadena vacía se define como cero como un caso especial).

Mi intuición es que la función de código hash como la anterior proporciona una dispersión uniforme de los valores Hash String en todo el rango de valores int . Un spread uniforme que significaría que la probabilidad de un hashing de cadena generado aleatoriamente a cero era 1 en 2 ^ 32.

• ¿Cuál es la mejor manera de evitar la penalización de rendimiento de volver a calcular el valor hash cada vez para cadenas que hash a 0?

La mejor estrategia es ignorar el problema. Si repetidamente has hashing el mismo valor String, hay algo bastante extraño en tu algoritmo.

• ¿Es esta la mejor práctica de los valores de almacenamiento en caché? (es decir, ¿caché todo menos uno?)

Este es un intercambio de espacio versus tiempo. AFAIK, las alternativas son:

• Agregue un indicador en cached a cada objeto String, haciendo que cada cadena Java tome una palabra adicional.

• Use el bit superior del miembro hash como indicador en caché. De esta forma puede almacenar en caché todos los valores de hash, pero solo tiene la mitad de los posibles valores de hash de cadena.

• No almacene hashcodes en cadenas en absoluto.

Creo que los diseñadores de Java han hecho la llamada correcta para Strings, y estoy seguro de que han realizado un amplio perfil que confirma la solidez de su decisión. Sin embargo, esto no significa que esta sea siempre la mejor forma de tratar con el almacenamiento en caché.

(Tenga en cuenta que hay dos valores de Cadena "común" que tiene Hash a cero, la Cadena vacía y la Cadena que consiste en solo un carácter NUL. Sin embargo, el costo de calcular los códigos Hash para estos valores es pequeño en comparación con el costo de calcular el hashcode para un valor de cadena típico).

Answer 2

0 no se almacena en caché, ya que la implementación interpreta un valor en caché de 0 como "valor en caché aún no inicializado". La alternativa habría sido usar un java.lang.Integer , donde null implicaba que el valor aún no estaba en la memoria caché. Sin embargo, esto habría significado una sobrecarga de almacenamiento adicional.

En cuanto a la probabilidad de que un código hash de String se compute como 0, diría que la probabilidad es bastante baja y puede ocurrir en los siguientes casos:

• La cadena está vacía (aunque volver a calcular este código hash cada vez es efectivamente O (1)).
• Se produce un desbordamiento por el cual el código hash calculado final es 0 ( eg Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0 ).
• The String contiene solo el carácter Unicode 0. Muy poco probable ya que este es un personaje de control sin significado aparte del "mundo de la cinta de papel" (!):

De la Wikipedia :

El código 0 (nombre de código ASCII NUL) es un caso especial. En cinta de papel, es el caso cuando no hay agujeros. Es conveniente tratar esto como un personaje de relleno sin otro significado .

Answer 3

Bueno amigos, mantiene 0 porque si es de longitud cero, terminará como cero de todos modos.

Y no toma mucho tiempo descubrir que el len es cero y también debe ser el código hash.

Por lo tanto, para su code-reviewz! Aquí está en toda su gloria de Java 8:

 public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

Como puede ver, esto siempre devolverá un cero rápido si la cadena está vacía:

  if (h == 0 && value.length > 0) ...

Answer 4

Creo que hay algo importante que las otras respuestas hasta ahora están ausentes: el valor cero existe, por lo que el mecanismo hashCode-caching funciona de manera robusta en un entorno de subprocesos múltiples.

Si tuviera dos variables, como cachedHashCode en sí mismo y un isHashCodeCalculated boolean para indicar si se había calculado cachedHashCode, necesitaría la sincronización de subprocesos para que las cosas funcionen en un entorno multiproceso. Y la sincronización sería mala para el rendimiento, especialmente porque las cadenas se reutilizan con mucha frecuencia en varios hilos.

Mi comprensión del modelo de memoria de Java es un poco incompleto, pero aquí está más o menos lo que está pasando:

1. Cuando varios subprocesos acceden a una variable (como el hashCode en caché), no hay garantía de que cada subproceso vea el último valor. Si una variable comienza en cero, A lo actualiza (lo establece en un valor distinto de cero), luego el hilo B lo lee poco después, el hilo B aún puede ver el valor cero.

2. Hay otro problema para acceder a valores compartidos desde múltiples hilos (sin sincronización): puede terminar tratando de usar un objeto que solo se ha inicializado parcialmente (la construcción de un objeto no es un proceso atómico). Las lecturas y escrituras de subprocesos múltiples de primitivas de 64 bits como largos y dobles tampoco son necesariamente atómicas, por lo que si dos subprocesos intentan leer y cambiar el valor de uno largo o uno doble, un subproceso puede terminar viendo algo extraño y parcialmente establecido . O algo así de todos modos. Hay problemas similares si intenta utilizar dos variables juntas, como cachedHashCode y isHashCodeCalculated: un hilo puede aparecer fácilmente y ver la última versión de una de esas variables, pero una versión anterior de otra.

3. La forma habitual de evitar estos problemas de subprocesos múltiples es utilizar la sincronización. Por ejemplo, podría poner todo el acceso al hashCode en caché dentro de un bloque sincronizado, o podría usar la palabra clave volátil (aunque tenga cuidado con eso porque la semántica es un poco confusa).

4. Sin embargo, la sincronización ralentiza las cosas. Mala idea para algo así como una cadena hashCode. Las cadenas se utilizan muy a menudo como claves en HashMaps, por lo que necesita el método hashCode para un buen rendimiento, incluso en entornos de subprocesos múltiples.

5. Las primitivas Java de 32 bits o menos, como int, son especiales. A diferencia de, por ejemplo, un valor largo (64 bits), puede estar seguro de que nunca leerá un valor parcialmente inicializado de un int (32 bits). Cuando lee un int sin sincronización, no puede estar seguro de que obtendrá el último valor establecido, pero puede estar seguro de que el valor que obtiene es un valor que ha sido explícitamente establecido en algún momento por su hilo o otro hilo.

El mecanismo de caché hashCode en java.lang.String está configurado para confiar en el punto 5 anterior. Puede comprenderlo mejor si mira la fuente de java.lang.String.hashCode (). Básicamente, con múltiples hilos llamando a hashCode a la vez, hashCode podría terminar siendo calculado varias veces (ya sea si el valor calculado es cero o si varios hilos llaman a hashCode a la vez y ambos ven un valor en caché cero), pero puedes estar seguro de que hashCode () siempre devolverá el mismo valor. Por lo tanto, es robusto y funciona bien (porque no hay sincronización para actuar como un cuello de botella en entornos con múltiples subprocesos).

Como dije, mi comprensión del modelo de memoria de Java es un poco incompleto, pero estoy bastante seguro de que tengo la esencia de lo de arriba. En definitiva, es una expresión muy inteligente para almacenar en caché el hashCode sin la sobrecarga de la sincronización.

Answer 5

Esta resulta ser una buena pregunta, relacionada con una vulnerabilidad de seguridad .

"Al manipular una cadena, Java también guarda el valor hash en el atributo hash, pero solo si el resultado es diferente de cero. Por lo tanto, el valor objetivo cero es particularmente interesante para un atacante, ya que previene el almacenamiento en caché y obliga a volver a hash."

Answer 6

La sugerencia de "evitar 0" parece apropiada para recomendar como mejor práctica, ya que ayuda a un problema genuino (degradación de rendimiento seriamente inesperada en casos construibles que pueden ser suministrados por atacante) por el escaso costo de una operación de sucursal antes de una escritura. Existe una "degradación inesperada del rendimiento" restante que puede ejercerse si las únicas cosas que entran en un ajuste son el valor ajustado especial. Pero esto es en el peor de los casos una degradación 2 veces más que ilimitada.

Por supuesto, la implementación de String no se puede cambiar, pero no hay necesidad de perpetuar el problema.

Answer 7

No te preocupas por nada. Aquí hay una manera de pensar sobre este tema.

Supongamos que tiene una aplicación que no hace nada más que sentarse alrededor de hash Strings todo el año. Digamos que lleva mil cadenas, todo en la memoria, llama a hashCode () repetidamente en forma de contramarcha, un millón de veces, luego obtiene otras mil cadenas nuevas y lo vuelve a hacer.

Y supongamos que la probabilidad de que el código hash de una cadena sea cero era, de hecho, mucho mayor que 1/2 ^ 32. Estoy seguro de que es algo mayor que 1/2 ^ 32, pero digamos que es mucho peor que eso, como 1/2 ^ 16 (¡la raíz cuadrada! ¡Ahora eso es mucho peor!).

En esta situación, tiene más para beneficiarse de los ingenieros de Oracle que mejoran la forma en que estos códigos hash de cadenas se almacenan en caché que nadie más con vida. Entonces les escribes y les pides que lo arreglen. Y trabajan su magia para que cada vez que s.hashCode () sea cero, vuelva instantáneamente (¡incluso la primera vez! ¡Una mejora del 100%!). Y digamos que lo hacen sin degradar el rendimiento en ningún otro caso.

¡Hurra! Ahora tu aplicación es ... veamos ... 0.0015% más rápido.

¡Lo que solía tomar un día entero ahora solo toma 23 horas, 57 minutos y 48 segundos!

Y recuerde, configuramos el escenario para dar todos los beneficios posibles de la duda, a menudo hasta un grado ridículo.

¿Te parece que esto vale la pena?

EDITAR: desde que publiqué esto hace un par de horas, he dejado que uno de mis procesadores se vuelva loco buscando frases de dos palabras con cero códigos hash. Hasta ahora se ha propuesto: bequirtle zorillo, chronogrammic schtoff, contusive cloisterlike, creashaks organzine, drumwood boulderhead, electroanalytic ejercitable y favosely no evaluable. Esto está fuera de alrededor de 2 ^ 35 posibilidades, por lo que con una distribución perfecta esperaríamos ver solamente 8. Claramente, para cuando termine tendremos unas pocas veces más, pero no extravagantemente más. ¡Lo que es más significativo es que ahora he encontrado algunos nombres de bandas / nombres de bandas interesantes! ¡No es un robo justo!

Answer 8

Utiliza 0 para indicar "Aún no he resuelto el código hash". La alternativa sería usar un indicador booleano separado, lo que requeriría más memoria. (O para no almacenar en caché el código hash en absoluto, por supuesto).

No espero muchas cadenas hash a 0; podría decirse que tendría sentido para la rutina de hash evitar deliberadamente 0 (por ejemplo, traducir un hash de 0 a 1 y guardarlo en caché). Eso aumentaría las colisiones, pero evitaría volver a generar colisiones. Sin embargo, es demasiado tarde para hacer eso, ya que el algoritmo String hashCode está documentado explícitamente.

En cuanto a si esta es una buena idea en general: es un mecanismo de caché ciertamente eficiente, y podría (ver edición) ser aún mejor con un cambio para evitar el reajuste de los valores que terminan con un hash de 0. Personalmente estaría interesado en ver los datos que llevaron a Sun a creer que esto valía la pena hacerlo, están ocupando 4 bytes adicionales por cada cadena que se haya creado, sin embargo, a menudo o rara vez, y el único beneficio es para las cadenas que se procesan más de una vez .

EDITAR: Como señala KevinB en un comentario en otro lugar, la sugerencia de "evitar 0" anterior bien puede tener un costo neto porque ayuda en un caso muy raro , pero requiere una comparación adicional para cada cálculo de hash.