¿Por qué es importante establecer un número de cubos y distribuir los objetos entre ellos lo más uniformemente posible?
A HashSet debe ser capaz de determinar la membresía en O (1) tiempo en promedio. Desde el documentation:
Esta clase ofrece un rendimiento constante de tiempo para las operaciones básicas (añadir, eliminar, contiene y tamaño), asumiendo la función hash se dispersa adecuadamente los elementos entre los cubos.
El algoritmo utiliza una Hashset para lograr esto es para recuperar el código hash para el objeto y usar esto 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 del cucharón?
Aquí hay una compensación de espacio-tiempo. Aumentar la cantidad de cubos disminuye las posibilidades de colisiones. Sin embargo, también aumenta los requisitos de memoria. El conjunto hash tiene dos parámetros initialCapacity y loadFactor que le permiten ajustar cuántos intervalos 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.
Más información sobre estos parámetros se puede encontrar en la documentación para HashMap:
Esta aplicación proporciona un rendimiento constante de tiempo para las operaciones básicas (get y put), asumiendo la función de dispersión dispersa los elementos adecuadamente 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.
Entonces, ¿es mejor tener 1 enfoque de objeto por cubeta? – Jyotirup
Sí, pero HashSet hace eso por usted, siempre que el valor devuelto por hashCode() se distribuya correctamente. Si devuelve una constante de hashCode(), por ejemplo, todos los objetos terminarán en el mismo cubo. –
@Jyotirup: No es necesario lograr la situación ideal de exactamente 1 objeto por cubo. Es normal que haya algunas colisiones. –