sirve - Distribución de cubos Hashcode en java
object equals java (3)
Supongamos que necesito almacenar 1000 objetos en Hashset, ¿es mejor tener 1000 cubos que contengan cada objeto (generando un valor único para hashcode para cada objeto) o tener 10 cubos que contengan aproximadamente 100 objetos?
Una de las ventajas de tener un cubo único es que puedo guardar el ciclo de ejecución al llamar al método equals ().
¿Por qué es importante haber establecido el número de cubos y distribuir los objetos entre ellos lo más uniformemente posible?
¿Cuál debería ser el objeto ideal para la relación de cubo?
¿Por qué es importante haber establecido el número de cubos y distribuir los objetos entre ellos lo más uniformemente posible?
Un HashSet debería poder determinar la membresía en O (1) tiempo en promedio. De la documentación :
Esta clase ofrece un rendimiento de tiempo constante para las operaciones básicas (agregar, eliminar, contener y tamaño), asumiendo que la función de dispersión dispersa los elementos correctamente entre los cubos.
El algoritmo que usa Hashset para lograr esto es recuperar el código hash para el objeto y usarlo para encontrar el cubo correcto. Luego itera sobre todos los elementos en el cubo hasta que encuentre uno que sea igual. Si la cantidad de elementos en el contenedor es mayor que O (1), la búsqueda tomará más tiempo que O (1).
En el peor de los casos, si todos los elementos comparten el mismo cubo, llevará un tiempo O (n) para determinar si un objeto está en el conjunto.
¿Cuál debería ser el objeto ideal para la relación de cubo?
Hay una compensación de espacio-tiempo aquí. Aumentar la cantidad de cubos disminuye las posibilidades de colisiones. Sin embargo, también aumenta los requisitos de memoria. El conjunto de hash tiene dos parámetros, initialCapacity y loadFactor que le permiten ajustar cuántos cangilones debe crear HashSet . El factor de carga predeterminado es 0.75 y esto está bien para la mayoría de los propósitos, pero si tiene requisitos especiales, puede elegir otro valor.
Se puede encontrar más información sobre estos parámetros en la documentación de HashMap :
Esta implementación proporciona un rendimiento en tiempo constante para las operaciones básicas (get y put), suponiendo que la función hash dispersa los elementos correctamente entre los cubos. La iteración sobre las vistas de recopilación requiere un tiempo proporcional a la "capacidad" de la instancia de HashMap (el número de segmentos) más su tamaño (el número de asignaciones de valores-clave). Por lo tanto, es muy importante no establecer la capacidad inicial demasiado alta (o el factor de carga demasiado bajo) si el rendimiento de la iteración es importante.
Una instancia de HashMap tiene dos parámetros que afectan su rendimiento: capacidad inicial y factor de carga. La capacidad es el número de segmentos en la tabla hash, y la capacidad inicial es simplemente la capacidad en el momento en que se crea la tabla hash. El factor de carga es una medida de cuán completa está permitida la tabla hash antes de que su capacidad aumente automáticamente. Cuando el número de entradas en la tabla hash excede el producto del factor de carga y la capacidad actual, la capacidad se duplica aproximadamente llamando al método Rehash.
Como regla general, el factor de carga predeterminado (.75) ofrece una buena compensación entre los costos de tiempo y espacio. Los valores más altos disminuyen la sobrecarga de espacio, pero aumentan el costo de búsqueda (que se refleja en la mayoría de las operaciones de la clase HashMap, incluidos get y put). El número esperado de entradas en el mapa y su factor de carga se deben tener en cuenta al establecer su capacidad inicial, a fin de minimizar el número de operaciones de repetición. Si la capacidad inicial es mayor que la cantidad máxima de entradas dividida por el factor de carga, nunca se producirán operaciones de repetición.
Aproximadamente una cubeta por elemento es mejor para el procesador, demasiados cubos son malos para la memoria. Java comenzará con una pequeña cantidad de cubos y automáticamente aumentará la capacidad de su HashSet una vez que se comience a llenar, por lo que realmente no necesita preocuparse a menos que su aplicación tenga problemas de rendimiento y haya identificado un hashset como la causa.
Si tiene varios elementos en cada segmento, las búsquedas comienzan a tomar más tiempo. Si tiene muchos contenedores vacíos, está usando más memoria de la que necesita y la iteración de los elementos lleva más tiempo.
Sin embargo, esto parece una optimización prematura a la espera de que suceda: el constructor predeterminado está bien en la mayoría de los casos.
Object.hashCode() son de tipo int , solo puedes tener 2 ^ 32 valores diferentes, por eso creas cubos y distribuyes objetos entre ellos.
Editar: Si está usando 2^32 cubos para almacenar 2 ^ 32 objetos, entonces definitivamente obtendrá operaciones que le darán una complejidad constante, pero cuando inserte uno por uno para almacenar 2^32 objetos, entonces el reajuste funcionará, lo que significa que estamos usando Object[] como cubos, cada vez que exceda la longitud de la array creará una nueva matriz con mayor tamaño y copiará elementos en esta. este proceso aumentará la complejidad. Es por eso que hacemos uso de equals y hashcode en razón y eso lo hacen los Hashsets al proporcionar un mejor hashing algorithm .