¿Por qué HashSet tiene "Hash" en su nombre?

Question

¿Por qué se llama a Hashset un conjunto "Hash"?

Entiendo que llamamos hashmap o un hashmap, ya que es un almacén de valores clave y cuando ponemos(), la clave es hash y se distribuye de manera uniforme con una buena función hash.

Supongo que se llama HashSet porque cuando agregamos(), el valor se codifica y se almacena para mantenerlo único. Pero, ¿por qué la exageración? Realmente no nos importa la "distribución equitativa" de datos, como hacemos en una tabla Hash.

Answer 1

Nos preocupamos por la distribución equitativa porque queremos un rendimiento constante de tiempo en nuestros Collection operaciones básicas. Para respetar las reglas básicas de SET, no hay dos objetos iguales, queremos encontrar una coincidencia potencialmente igual rápidamente. HashSet es una forma bastante buena de hacerlo. Compare con un ArraySet teórico donde agregar un nuevo elemento es una operación de tiempo lineal para iterar y verificar cada entrada existente para la igualdad.

Answer 2

Un HashSet se llama HashSet porque hash es realmente importante para su funcionalidad. Operaciones como contains(Object) (sin duda el método más importante en un Set) y remove(Object) son capaces de trabajar en tiempo constante, haciendo uso del código hash del objeto (por medio de HashMap).

Answer 3

¿Qué 'overkill'? La idea de un HashXXX para cualquier X es proporcionar un rendimiento O (1), y eso se logra mediante hash. Si no quiere un rendimiento O (1), no lo use. Use un TreeSet por ejemplo.

Answer 4

HashSet (como HashMap) utiliza, así, hashing, para lograr O (1) amortizados set/prueba/eliminar el rendimiento. (había algunas suposiciones incorrectas en la pregunta sobre HashSet no usar hash.)

Ahora, en Java, todos los objetos son "hashable" - es decir, que tienen una función hashCode() (ya que como descendientes de Object). La calidad de esta función de hash permitirá que un algoritmo hash alcance las características de rendimiento anticipadas mencionadas al "distribuir los objetos [uniformemente] a través de los cubos". (Las implementaciones por defecto de objeto de hashCode/es igual a la cantidad de objetar la identidad. En general, esto se debe cambiar para cualquier subclase.)

Sin embargo, si su clase implementa hashCode mal (por ejemplo, devuelve 1 para todos los valores), entonces el rendimiento de HashSet/HashMap sufrirá mucho como resultado (para cualquier n no trivial). Es importante señalar que hashCode determina el cubo pero equals determina, así, la igualdad real que se puede utilizar incluso si el código hash es único y/o no hay colisiones (por ejemplo, para asegurarse de que la prueba/get no devuelve un falso positivo; podría eliminarse en un conjunto/inserto sin colisión).

Sólo asegúrese de seguir la configuración de los requisitos en Object WRT. hashCode y equals u objetos pueden perderse. Una función de hash deficiente que cumpla con las reglas seguirá funcionando, aunque con un rendimiento potencialmente deficiente. (Objeto mutable son especialmente problemáticos para su uso en los ADT de hash debido a que el código hash y/o igualdad no siempre pueden ser estables.)