¿Por qué un factor de carga más alto en HashMap aumentaría el costo de búsqueda?

Question

De JavaDoc de HashMap:

Como regla general, el factor de carga por defecto (0,75) ofrece un buen compromiso entre costes 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, incluidas get y put).

Si tenemos un valor más alto, ¿por qué aumentaría el costo de búsqueda?

Answer 1

se define de Load Factor tabla Hash como

n/s, la relación entre el número de entradas almacenadas n y el tamaño s de la matriz de la tabla de cubos.

El alto rendimiento de la tabla hash se mantiene cuando el número de colisiones es bajo. Cuando el factor de carga es alto, la probabilidad de colisiones aumenta.

Answer 2

Tiene que ver con cómo se implementa una HashTable debajo del capó, utiliza códigos hash y dado que el algoritmo para calcular el código hash no es perfecto, puede tener algunas colisiones, aumentar el factor de carga aumentar la probabilidad de tener colisiones y, en consecuencia reducir el rendimiento de la búsqueda ...

Answer 3

factor de carga predeterminado (0,75).

If declare load factor as 
1 the restructuring process only happens when number of elements are exceeding the capacity of the HashMap. 

Answer 4

Aquí debemos entender primero lo que la capacidad y el factor de carga significa:

capacidad: este es el número de cubos en cualquier tabla hash en cualquier punto dado en el tiempo.

factor de carga: El factor de carga es una medida de qué tan lleno está permitida la tabla hash para llegar antes de que su capacidad se incrementa automáticamente

manera más el factor de carga es más ocupado una tabla hash podría llegar antes de que la capacidad se incrementó .

• ahora, dada la mejor aplicación posible de hashCode() sólo un valor tope en una cubeta aquí de búsqueda costo será mínimo
• en peor de los casos todos los valores irán en el mismo cubo y la búsqueda costo sería máxima
• en un caso promedio también, esto seguramente depende de hashCode() la ejecución, sino un factor más que jugar aquí es el factor de carga, a medida que la colección esté más ocupada, habrá más posibilidades de colisión y, por lo tanto, un factor de carga mayor aumentará el costo de búsqueda en un escenario no ideal.

Answer 5

El factor 0,75 carga se puede interpretar de esta manera utilizando la fórmula (n/s, la relación entre el número de entradas almacenadas n y el tamaño s de la matriz de la tabla de cubos.):

Supongamos que tiene 75 valores que necesita almacenar en la tabla hash y tiene 100 bloques de matriz vacíos para almacenarlos, aquí las posibilidades de colisión se reducen al mínimo y el factor de carga es 0,75.

Ahora suponga que tiene 75 valores para almacenar y solo 10 bloques de matriz vacíos (factor de carga 7.5) esto significa que tendrá colisión y empleará cualquiera de las técnicas de resolución de colisiones que aumentarán su tiempo de búsqueda.

Ahora, de otra manera, tiene 75 entradas y 1000 bloques de matriz vacíos (factor de carga 0,075) esto dará lugar a muchos bloques vacíos, lo cual es una gran pérdida de espacio.

Por lo tanto, la regla general es que a medida que aumenta el valor del factor de carga, el tiempo de búsqueda aumentará y, a medida que se acerque a 0, se desperdiciará más espacio de almacenamiento.

Por lo tanto, es un tradeof en el espacio.