java - que - Elegir la capacidad inicial de un HashSet con un número esperado de valores únicos e inserciones

map java ejemplo

Question

Ok, esta es mi situación:

Tengo una matriz de estados, que puede contener duplicados. Para deshacerse de los duplicados, puedo agregarlos a un conjunto.

Sin embargo, cuando creo el conjunto, quiere que se definan la capacidad inicial y el factor de carga, pero ¿en qué deberían estar configurados?

De googlear, he encontrado:

String[] allStates = getAllStates();
Set<String> uniqueStates = new HashSet<String>(allStates.length, 0.75);

El problema con esto es que allStates puede contener entre 1 y 5000 estados. Por lo tanto, el conjunto tendrá una capacidad de más de 5000, pero solo con un máximo de 50.

Entonces, alternativamente, establezca que el tamaño máximo del conjunto se puede configurar para que sea el número máximo de estados, y el factor de carga sea 1.

Creo que mis preguntas realmente son:

• ¿Qué debería establecer la capacidad inicial para ser cuando no sabe cuántos elementos deben estar en el conjunto?
• ¿Realmente importa en qué se establece cuando la mayor cantidad que puede contener es 50?
• ¿Debería incluso estar preocupado por eso?

Answer 1

Adivina bien. No hay una regla dura Si sabes que probablemente habrá entre 10 y 20 estados, comenzaría con ese número (20).

Answer 2

La apuesta segura es ir por un tamaño que es demasiado pequeño.

Debido a que el cambio de tamaño se mejora mediante un algoritmo de crecimiento exponencial (ver el podcast de de hace unas semanas), ir pequeño nunca le costará tanto. Si tienes muchos sets (afortunado), entonces tendrá importancia el rendimiento si son demasiado grandes.

El factor de carga es complicado. Sugiero dejarlo en el valor predeterminado. Entiendo: por debajo de 0.70f usted está haciendo que la matriz sea demasiado grande y, por lo tanto, más lenta. Por encima de 0.80f y comenzará a llegar a muchos choques clave. Presumiblemente, los algoritmos de exploración requerirán factores de carga más bajos que los algoritmos de cubo.

También tenga en cuenta que la "capacidad inicial" significa algo ligeramente diferente de lo que parece que la mayoría de la gente piensa. Se refiere a la cantidad de entradas en la matriz. Para obtener la capacidad exacta para una cantidad de elementos, divida por el factor de carga deseado (y redondee apropiadamente).

Answer 3

Suponiendo que sepa que no habrá más de 50 estados (¿se refiere a los Estados Unidos?), La

Set<String> uniqueStates = new HashSet<String>(allStates.length, 0.75);

citado es definitivamente incorrecto. Te sugiero que vayas por una capacidad inicial de 50 / 0.75 = 67, o tal vez 68 para estar en el lado seguro.

También siento la necesidad de señalar que probablemente estás pensando demasiado en esto. Cambiar el tamaño de la lista de arrays dos veces, de 16 a 64, no le dará un golpe de rendimiento notable a menos que esto esté justo en la parte más crítica del rendimiento del programa.

Entonces la mejor respuesta es probablemente usar:

new HashSet<String>();

De esta forma, no regresarás un año después y te darás cuenta de por qué elegiste esos argumentos de constructor tan extraños.

Answer 4

Use el constructor donde no necesita especificar estos valores, entonces se eligen los valores predeterminados razonables.

Answer 5

Yo segundo Zarkonnen. Tu última pregunta es la más importante. Si sucede esto en un punto de acceso de su aplicación, puede valer la pena el esfuerzo de mirarlo e intentar optimizarlo, de lo contrario los ciclos de CPU son más baratos que la quema de sus propias neuronas.

Answer 6

Si tuviera que optimizar esto, y puede ser apropiado hacerlo, parte de su decisión dependerá de cuántos duplicados espera que tenga la matriz.

• Si hay muchos duplicados, querrá una capacidad inicial más pequeña. Las tablas hash grandes y dispersas son malas al iterar.

• Si no se espera que haya muchos duplicados, querrá una capacidad inicial tal que la matriz completa pueda caber sin cambiar el tamaño.

Supongo que quieres lo último, pero esto es algo que vale la pena considerar si persigues esto.

Answer 7

Primero, voy a decir que en tu caso definitivamente estás pensando demasiado. Sin embargo, probablemente haya situaciones en las que uno quiera hacerlo bien. Así que esto es lo que entiendo:

1) La cantidad de elementos que puede contener en su HashSet = capacidad inicial x factor de carga. Entonces, si desea poder mantener n elementos, debe hacer lo que Zarkonnen hizo y dividir n por el factor de carga.

2) Bajo las cubiertas, la capacidad inicial se redondea a una potencia de dos por tutorial de Oracle .

3) El factor de carga no debe ser mayor a .80 para evitar colisiones excesivas, como lo señaló Tom Hawtin - tackline .

Si solo acepta los valores predeterminados (capacidad inicial = 16, factor de carga = .75), terminará doblando su conjunto en tamaño 3 veces. (Tamaño máximo inicial = 12, primer aumento hace capacidad 32 y tamaño máximo 24 (32 * .75), segundo aumento hace capacidad 64 y tamaño máximo 48 (64 * .75), tercer aumento hace capacidad 128 y tamaño máximo 96 (128 * .75).)

Para obtener su tamaño máximo más cerca de 50, pero mantenga el conjunto lo más pequeño posible, considere una capacidad inicial de 64 (una potencia de dos) y un factor de carga de .79 o más. 64 * .79 = 50.56, por lo que puede obtener los 50 estados allí. Especificar 32 <capacidad inicial <64 dará como resultado que la capacidad inicial se redondee a 64, por lo que es lo mismo que especificar 64 al frente. Especificar la capacidad inicial <= 32 dará como resultado un aumento de tamaño. Usar un factor de carga <.79 también dará como resultado un aumento de tamaño a menos que su capacidad inicial> 64.

Entonces mi recomendación es especificar la capacidad inicial = 64 y el factor de carga = .79.