HashMap rehash / redimensionner la capacité
HashMap a une phrase à partir de la documentation:
si la capacité initiale est supérieure au nombre maximum d'entrées divisé par le facteur de charge, aucune opération de reprise ne sera jamais se produire.
notez comment la documentation dit resucée, pas taille - même si une rechute ne se produit que lorsqu'une redimensionnement se produit; c'est alors que la taille interne des seaux est deux fois plus grande.
Et bien sûr HashMap fournit un tel constructeur où nous pourrions définir ce capacité initiale.
construit un HashMap vide avec la capacité initiale spécifiée et le facteur de charge par défaut (0.75).
OK, semble assez facile:
// these are NOT chosen randomly...
List<String> list = List.of("DFHXR", "YSXFJ", "TUDDY",
"AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR");
int maxNumberOfEntries = list.size(); // 9
double loadFactor = 0.75;
int capacity = (int) (maxNumberOfEntries / loadFactor + 1); // 13
Donc la capacité est 13 (en interne, c'est 16 - next puissance de deux), de cette façon nous garantissons que la partie de documentation ne se répète pas. Ok, nous allons tester ceci, mais d'abord introduire une méthode qui ira dans un HashMap et regarder les valeurs:
private static <K, V> void debugResize(Map<K, V> map, K key, V value) throws Throwable {
Field table = map.getClass().getDeclaredField("table");
AccessibleObject.setAccessible(new Field[] { table }, true);
Object[] nodes = ((Object[]) table.get(map));
// first put
if (nodes == null) {
// not incrementing currentResizeCalls because
// of lazy init; or the first call to resize is NOT actually a "resize"
map.put(key, value);
return;
}
map.put(key, value);
Field field = map.getClass().getDeclaredField("table");
AccessibleObject.setAccessible(new Field[] { field }, true);
int x = ((Object[]) field.get(map)).length;
if (nodes.length != x) {
++HashMapResize.currentResizeCalls;
System.out.println(nodes.length + " " + x);
}
}
Et maintenant, nous allons tester ceci:
static int currentResizeCalls = 0;
public static void main(String[] args) throws Throwable {
List<String> list = List.of("DFHXR", "YSXFJ", "TUDDY",
"AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR");
int maxNumberOfEntries = list.size(); // 9
double loadFactor = 0.75;
int capacity = (int) (maxNumberOfEntries / loadFactor + 1);
Map<String, String> map = new HashMap<>(capacity);
list.forEach(x -> {
try {
HashMapResize.debugResize(map, x, x);
} catch (Throwable throwable) {
throwable.printStackTrace();
}
});
System.out.println(HashMapResize.currentResizeCalls);
}
Eh bien,resize a été appelé et donc les entrées ont été rabâchées, pas ce que dit la documentation.
comme nous l'avons dit, les clés n'ont pas été choisies au hasard. Ils ont été mis en place pour qu'ils déclenchent la static final int TREEIFY_THRESHOLD = 8; propriété - lorsqu'un seau est converti en arbre. Eh bien pas vraiment, car nous avons besoin de frapper aussi MIN_TREEIFY_CAPACITY = 64 pour l'arbre à apparaître, jusqu'à ce que resize se produit, ou un seau est doublé dans la taille; ainsi le ressassage des entrées se produit.
je ne peux que astuce pour pourquoi HashMap la documentation est erronée dans cette phrase, puisque avant java-8, un seau n'a pas été converti en arbre; ainsi la propriété tiendrait, à partir de java-8 et plus ce n'est plus vrai. Puisque je ne suis pas sûr de cela, je ne vais pas ajouter cela comme réponse.
1 réponses
La ligne de la documentation,
si la capacité initiale est supérieure au nombre maximum d'entrées divisé par le facteur de charge, aucune opération de reprise ne se produira jamais.
en effet date d'avant que l'implémentation de tree-bin n'ait été ajoutée dans JDK 8 ( JEP 180). Vous pouvez voir ce texte dans le JDK 1.6 HashMap documentation. En fait, ce texte remonte à JDK 1.2 lorsque le cadre de Collections (y compris HashMap) a été introduit. Vous pouvez trouver des versions non officielles des docs JDK 1.2 sur le web, ou vous pouvez télécharger une version à partir du archives si vous voulez voir par vous-même.
je crois que cette documentation était correcte jusqu'à ce que l'implémentation tree-bin soit ajoutée. Cependant, comme vous l'avez observé, il y a maintenant des cas où c'est incorrect. La politique n'est pas seulement que le redimensionnement peut se produire si le nombre d'entrées divisé par le facteur de charge dépasse la capacité (en fait, longueur de la table). Comme vous l'avez remarqué, redimensionne pouvez se produit si le nombre d'entrées dans un seul seau dépasse TREEIFY_THRESHOLD (actuellement 8) mais la longueur de la table est plus petite que MIN_TREEIFY_CAPACITY (actuellement 64).
Vous pouvez voir cette décision dans le treeifyBin() méthode de HashMap.
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
ce point dans le code est atteint quand il y a plus que des entrées TREEIFY_THRESHOLD dans un seul seau. Si la taille de la table est ou au-dessus de MIN_TREEIFY_CAPACITY, cette bin est treeified; sinon, la table est simplement redimensionnée.
notez que cela peut laisser des bacs avec un peu plus d'entrées que TREEIFY_THRESHOLD pour les petites tailles de table. Ce n'est pas terriblement difficile à démontrer. Tout d'abord, certains HashMap réflective-code de dumping:
// run with --add-opens java.base/java.util=ALL-UNNAMED
static Class<?> classNode;
static Class<?> classTreeNode;
static Field fieldNodeNext;
static Field fieldHashMapTable;
static void init() throws ReflectiveOperationException {
classNode = Class.forName("java.util.HashMap$Node");
classTreeNode = Class.forName("java.util.HashMap$TreeNode");
fieldNodeNext = classNode.getDeclaredField("next");
fieldNodeNext.setAccessible(true);
fieldHashMapTable = HashMap.class.getDeclaredField("table");
fieldHashMapTable.setAccessible(true);
}
static void dumpMap(HashMap<?, ?> map) throws ReflectiveOperationException {
Object[] table = (Object[])fieldHashMapTable.get(map);
System.out.printf("map size = %d, table length = %d%n", map.size(), table.length);
for (int i = 0; i < table.length; i++) {
Object node = table[i];
if (node == null)
continue;
System.out.printf("table[%d] = %s", i,
classTreeNode.isInstance(node) ? "TreeNode" : "BasicNode");
for (; node != null; node = fieldNodeNext.get(node))
System.out.print(" " + node);
System.out.println();
}
}
maintenant, ajoutons un tas de cordes qui tombent toutes dans le même seau. Ces chaînes sont choisies de telle sorte que leurs valeurs de hachage, telles que calculées par HashMap, sont toutes 0 mod 64.
public static void main(String[] args) throws ReflectiveOperationException {
init();
List<String> list = List.of(
"LBCDD", "IKBNU", "WZQAG", "MKEAZ", "BBCHF", "KRQHE", "ZZMWH", "FHLVH",
"ZFLXM", "TXXPE", "NSJDQ", "BXDMJ", "OFBCR", "WVSIG", "HQDXY");
HashMap<String, String> map = new HashMap<>(1, 10.0f);
for (String s : list) {
System.out.println("===> put " + s);
map.put(s, s);
dumpMap(map);
}
}
à partir d'une taille de table initiale de 1 et d'un facteur de charge ridicule, cela met 8 entrées dans le seau Solitaire. Ensuite, chaque fois qu'une autre entrée est ajoutée, la table est redimensionnée (doublée) mais toutes les entrées finissent dans le même seau. Cela aboutit finalement à une table de taille 64 avec un seau ayant une chaîne linéaire de noeuds ("noeuds de base") de longueur 14, avant d'ajouter la prochaine entrée convertit finalement ceci en arbre.
Sortie du programme est que suit:
===> put LBCDD
map size = 1, table length = 1
table[0] = BasicNode LBCDD=LBCDD
===> put IKBNU
map size = 2, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU
===> put WZQAG
map size = 3, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG
===> put MKEAZ
map size = 4, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ
===> put BBCHF
map size = 5, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF
===> put KRQHE
map size = 6, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE
===> put ZZMWH
map size = 7, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH
===> put FHLVH
map size = 8, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH
===> put ZFLXM
map size = 9, table length = 2
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM
===> put TXXPE
map size = 10, table length = 4
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE
===> put NSJDQ
map size = 11, table length = 8
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ
===> put BXDMJ
map size = 12, table length = 16
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ
===> put OFBCR
map size = 13, table length = 32
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR
===> put WVSIG
map size = 14, table length = 64
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR WVSIG=WVSIG
===> put HQDXY
map size = 15, table length = 64
table[0] = TreeNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR WVSIG=WVSIG HQDXY=HQDXY