implementar - metodo boolean equals java

¿Por qué el hashCode de Java no admite el hashing universal?

Question

Algunos esquemas de tablas hash, como hashing de cuco o hashing dinámico perfecto , dependen de la existencia de funciones hash universales y la capacidad de tomar una colección de datos que exhiben colisiones y resolver esas colisiones eligiendo una nueva función hash de la familia de funciones hash universales. .

Hace un tiempo estaba intentando implementar una tabla hash en Java respaldada por hashing de cuco y hashCode problemas porque mientras todos los objetos Java tienen una función hashCode , el valor que hashCode devuelve se fija para cada objeto (a menos que, por supuesto, los objetos cambien ) Esto significa que sin que el usuario proporcione una familia externa de funciones hash universales, es imposible construir una tabla hash que dependa de hashing universal.

Inicialmente, pensé que podría evitar esto aplicando una función hash universal a los hashCode s del objeto directamente, pero esto no funciona porque si dos objetos tienen el mismo hashCode , entonces cualquier función determinística que aplique a esos códigos hash, incluso una la función hash elegida aleatoriamente dará como resultado el mismo valor y causará una colisión.

Parece que esto sería perjudicial para el diseño de Java. Significa que HashMap y otros contenedores hash están completamente prohibidos de usar tablas basadas en hashing universal, incluso si los diseñadores del lenguaje pueden pensar que tales tablas serían apropiadas en el diseño del lenguaje. También hace que sea más difícil para los diseñadores de bibliotecas de terceros construir tablas hash de este tipo también.

Mi pregunta es: ¿hay alguna razón por la cual Java optó por diseñar hashCode sin considerar la posibilidad de mezclar objetos con múltiples funciones hash? Entiendo que muchos buenos esquemas hash como hashing encadenado o sondeo cuadrático no lo requieren, pero parece que la decisión dificulta el uso de ciertas clases de algoritmos en objetos Java.

Answer 1

Creo que el método hashCode normal se creó sin tener en cuenta el caso de "entradas maliciosas". Además, según lo escrito por larsmann, su contrato es mucho más fácil de comprender e implementar de lo que sería una función hash universal.

Aquí una idea sobre qué hacer:

• Utilice una implementación de mapa que dependa de funciones hash externas (como la HashableEquivalenceRelation que presenté aquí hace algunas horas)
• luego use una familia universal de tales implementaciones (o una implementación que permita cambiar el parámetro para cambiar a otro miembro de la familia).

Answer 2

Simplicidad . Java permite a los diseñadores de clases proporcionar su propio hashCode , que como mencionas es lo suficientemente bueno para tablas hash "comunes", y puede ser bastante difícil de entender.

Además, cuando se diseñó la API de colecciones de Java, tener tablas hash genéricas en la biblioteca estándar ya era bastante atrevida. C nunca los ha tenido. C ++ los tenía en el STL como hash_set y hash_map , pero esos no llegaron al estándar. Solo ahora, en C ++ 0x, las tablas hash se consideran nuevamente para la estandarización.