java - una - tablas hash aplicaciones

¿Por qué los diseñadores de lenguajes de Java prefirieron el encadenamiento al direccionamiento abierto para la mayoría de las estructuras basadas en hash, excepto algunas como ThreadLocal?

Question

Sé la diferencia entre Open Addressing y Chaining para resolver colisiones hash. La mayoría de las estructuras de datos basadas en hash básicas como HashSet , HashMap en Java utilizan principalmente la técnica de encadenamiento. Leí que ThreadLocal realmente usa un esquema de sondeo. Entonces, quiero entender por qué el direccionamiento abierto no se usa tanto en Java. Quiero decir que sería difícil eliminar los registros utilizando ese esquema, en el sentido de que tiene que marcar esas celdas con un manejo especial. Sin embargo, parece que el requisito de memoria será bajo para el esquema de direccionamiento abierto.

Edición : solo quiero entender las posibles razones principales para esta decisión de diseño. No quiero detalles más finos. También me gustaría saber por qué ThreadLocal utiliza la técnica menos común de direccionamiento abierto. Supongo que las dos respuestas pueden estar relacionadas entre sí. Así que prefiero preguntar en la misma pregunta en sí.

Answer 1

Actualmente estoy discutiendo las reimplementaciones de memoria compacta de HashMap y HashSet con, entre otros, Doug Lea. Esta pregunta en particular no ha surgido, pero aquí están mis primeros pensamientos sobre la pregunta ...

• Las tablas hash encadenadas se degradan razonablemente con gracia. Ya sea que se trate de factores de carga más altos o muchas colisiones de hash, el encadenamiento no se degrada tan rápido como el direccionamiento abierto.
• Como ha dicho, remove es ... no es una operación agradable en tablas de direcciones abiertas. Como regla general, remove es la operación menos común en las tablas hash, pero hay aplicaciones para las que es más común y se notaría un mal rendimiento.
• También sospecho, aunque no tengo muchos datos, que implementar una tabla hash direccionada abierta "enlazada" sería notablemente más difícil. LinkedHashMap está escrito como una subclase de HashMap y toma prestados la mayoría de los detalles de implementación; es algo más fácil implementar la lista enlazada de entradas cuando las entradas son objetos discretos, y en ese punto, ya está casi todo el camino hacia una implementación encadenada.
• No hay nada en la especificación que los vincule a esta implementación; siempre son libres de jugar con ella más tarde.
• Las bibliotecas de colecciones JDK ... no hacen que el consumo de memoria sea una prioridad especialmente alta. La memoria es barata. (Puede o no estar de acuerdo con esto, pero definitivamente es una tendencia notable).