examples - ¿Por qué los mapas hash en Java 8 usan un árbol binario en lugar de una lista vinculada?

hashmap java example

Question

Recientemente descubrí que en Java 8, los mapas hash usan un árbol binario en lugar de una lista vinculada y se usa el código hash como factor de ramificación. Comprendo que en caso de colisión alta, la búsqueda se reduce a O (log n) desde O (n ) mediante el uso de árboles binarios. Mi pregunta es qué tan bueno es realmente ya que la complejidad del tiempo amortizado sigue siendo O (1) y tal vez si fuerza almacenar todas las entradas en el mismo segmento proporcionando el mismo código hash para todas las claves que puede ver una diferencia de tiempo significativa, pero nadie en su sano juicio haría eso.

El árbol binario también usa más espacio que la lista vinculada individualmente, ya que almacena los nodos izquierdo y derecho. ¿Por qué aumentar la complejidad del espacio cuando no hay absolutamente ninguna mejora en la complejidad del tiempo, excepto en algunos casos de prueba espurios?

Answer 1

Esto es principalmente un cambio relacionado con la seguridad. Mientras que en situaciones normales rara vez es posible tener muchas colisiones, si las claves hash llegan de fuentes no confiables (por ejemplo, nombres de encabezado HTTP recibidos del cliente), entonces es posible y no muy difícil crear la entrada, por lo que las claves resultantes tendrán el mismo hashcode. Ahora, si realiza muchas búsquedas, puede experimentar denegación de servicio. Parece que hay un montón de código en la naturaleza que es vulnerable a este tipo de ataques, por lo que se decidió solucionar esto en el lado de Java.

Para obtener más información, consulte JEP-180 .

Answer 2

Su pregunta contiene algunas premisas incorrectas.

1. Una colisión de cubo no es necesariamente una colisión hash. No necesita tener el mismo código hash para que dos objetos terminen en el mismo cubo. El cubo es un elemento de un conjunto y el código hash debe asignarse a un índice en particular. Dado que el tamaño de la matriz debe ser razonable con respecto al tamaño del Map , no puede elevar el tamaño de la matriz arbitrariamente para evitar colisiones de cubetas. Incluso existe la limitación teórica de que un tamaño de matriz puede ser máximo de 2³¹ mientras que hay 2³² posibles códigos hash.
2. Tener una colisión hash no es un signo de mala programación. Para todos los objetos que tienen un espacio de valor superior a 2³², la posibilidad de objetos distintos con el mismo código hash es inevitable. String son un ejemplo obvio, pero incluso un Point lleva dos valores int o una tecla Long simple tienen inevitables colisiones hash. Por lo tanto, podrían ser más comunes de lo que piensas y dependen en gran medida del caso de uso.
3. La implementación cambia a un árbol binario solo cuando el número de colisiones en un contenedor excede un cierto umbral, de modo que los costos de memoria más altos solo se aplican cuando dan resultado. parece haber un malentendido común con respecto a cómo funcionan. Dado que la colisión del cubo no es necesariamente una colisión hash, la búsqueda binaria primero buscará los códigos hash. Solo cuando los códigos hash sean idénticos y la clave implemente apropiadamente Comparable , se usará su orden natural. Los ejemplos que podría haber encontrado en la web utilizan deliberadamente el mismo código hash para objetos para demostrar el uso de la implementación Comparable que de otro modo no aparecería. Lo que activan es solo el último recurso de la implementación.
4. Como señaló Tagir , este problema podría afectar la seguridad de un software, ya que una lenta recuperación podría abrir la posibilidad de ataques DoS. Ha habido varios intentos en versiones anteriores de JRE para abordar este problema que tenía más inconvenientes que el consumo de memoria de un árbol binario. Por ejemplo, hubo un intento de aleatorizar la asignación de los códigos hash a las entradas de la matriz en Java 7, lo que provocó una sobrecarga de inicialización como se documenta en este informe de errores . Este no es el caso con esta nueva implementación.