LoginSignup
1
0

More than 3 years have passed since last update.

@koryo(Ryo Ko)

Java HashMap 中身を覗いて見ました

Last updated at Posted at 2021-02-20

Java の HashMap に、データを入れながら、中身を覗いて見ました。
Java Version : 1.8

InspectHashMap.java
package com;

import java.lang.reflect.Field;
import java.lang.reflect.Method;
import java.util.HashMap;
import java.util.Map;

public class InspectHashMap {

    public static void main(String[] args) throws Exception {
        //Method loadFactor = HashMap.class.getDeclaredMethod("loadFactor");
        //loadFactor.setAccessible(true);
        Field table = HashMap.class.getDeclaredField("table");
        table.setAccessible(true);
        Field threshold = HashMap.class.getDeclaredField("threshold");
        threshold.setAccessible(true);
        Method capacity = HashMap.class.getDeclaredMethod("capacity");
        capacity.setAccessible(true);

        int max = 25;
        Map<String, String> map = new HashMap<>();
        for (int ii = 1; ii <= max; ii++) {
            put(map, String.format("%03d", ii), table, threshold, capacity);
        }
    }

    private static void put(Map<String, String> map, String key$value, Field table, Field threshold, Method capacity) throws Exception {
        int $capacity = (int) capacity.invoke(map);
        System.out.println(String.format("%s : %d : mod(%d)", key$value, key$value.hashCode(), key$value.hashCode() % $capacity));
        map.put(key$value, key$value);
        System.out.println(String.format("%02d, %02d, %02d", map.size(), threshold.getInt(map), capacity.invoke(map)));
        Object[] nodes = (Object[]) table.get(map);
        System.out.println("--------------------------------------------------------------------");
        for (int index = 0; index < nodes.length; index++) {
            printNode(0, index, nodes[index]);
        }
        System.out.println("--------------------------------------------------------------------");
    }

    private static void printNode(int times, int index, Object node) throws Exception {
        if (times == 0) {
            System.out.print(String.format("[%03d]:", index));
        }
        if (node == null) {
            System.out.println(node);
            return;
        }
        System.out.print(node);
        System.out.print(" -> ");
        Field next = node.getClass().getDeclaredField("next");
        next.setAccessible(true);
        printNode(++times, index, next.get(node));
    }
}

25 個のキーを入れました。サイズ、拡張閾値、キャパシティの変化は以下の通り
※ new HashMap<>(); なので、負荷係数=0.75、初期容量=16

01, 12, 16
02, 12, 16
03, 12, 16
04, 12, 16
05, 12, 16
06, 12, 16
07, 12, 16
08, 12, 16
09, 12, 16
10, 12, 16
11, 12, 16
12, 12, 16
13, 24, 32 <---------- rehash 1回目
14, 24, 32
15, 24, 32
16, 24, 32
17, 24, 32
18, 24, 32
19, 24, 32
20, 24, 32
21, 24, 32
22, 24, 32
23, 24, 32
24, 24, 32
25, 48, 64 <---------- rehash 2回目

"001" の hashcode は 47665 なので、
47665 mod 16 = 1
47665 mod 32 = 17
47665 mod 64 = 49
よって、
"001" を put した時：(1番目になったことがわかる)

-[000]:null
-[001]:001=001 -> null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null

rehash 1回目後 (17番目になったことがわかる)

-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> null
-[020]:004=004 -> null
-[021]:005=005 -> null
-[022]:006=006 -> null
-[023]:007=007 -> null
-[024]:008=008 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null

rehash 2回目後 (49番目になったことがわかる)

-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:012=012 -> null
-[018]:013=013 -> null
-[019]:014=014 -> null
-[020]:015=015 -> null
-[021]:016=016 -> null
-[022]:017=017 -> null
-[023]:018=018 -> null
-[024]:019=019 -> null
-[025]:null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
-[032]:null
-[033]:null
-[034]:null
-[035]:null
-[036]:null
-[037]:null
-[038]:null
-[039]:null
-[040]:null
-[041]:null
-[042]:null
-[043]:null
-[044]:null
-[045]:null
-[046]:020=020 -> null
-[047]:021=021 -> null
-[048]:022=022 -> null
-[049]:001=001 -> 023=023 -> null
-[050]:002=002 -> 024=024 -> null
-[051]:003=003 -> 025=025 -> null
-[052]:004=004 -> null
-[053]:005=005 -> null
-[054]:006=006 -> null
-[055]:007=007 -> null
-[056]:008=008 -> null
-[057]:009=009 -> null
-[058]:null
-[059]:null
-[060]:null
-[061]:null
-[062]:null
-[063]:null

すべての実行結果を貼っどきます

001 : 47665 : mod(1)
01, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null
--------------------------------------------------------------------
002 : 47666 : mod(2)
02, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null
--------------------------------------------------------------------
003 : 47667 : mod(3)
03, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null
--------------------------------------------------------------------
004 : 47668 : mod(4)
04, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:004=004 -> null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null
--------------------------------------------------------------------
005 : 47669 : mod(5)
05, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:004=004 -> null
-[005]:005=005 -> null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null
--------------------------------------------------------------------
006 : 47670 : mod(6)
06, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:004=004 -> null
-[005]:005=005 -> null
-[006]:006=006 -> null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null
--------------------------------------------------------------------
007 : 47671 : mod(7)
07, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:004=004 -> null
-[005]:005=005 -> null
-[006]:006=006 -> null
-[007]:007=007 -> null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null
--------------------------------------------------------------------
008 : 47672 : mod(8)
08, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:004=004 -> null
-[005]:005=005 -> null
-[006]:006=006 -> null
-[007]:007=007 -> null
-[008]:008=008 -> null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null
--------------------------------------------------------------------
009 : 47673 : mod(9)
09, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:004=004 -> null
-[005]:005=005 -> null
-[006]:006=006 -> null
-[007]:007=007 -> null
-[008]:008=008 -> null
-[009]:009=009 -> null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:null
--------------------------------------------------------------------
010 : 47695 : mod(15)
10, 12, 16
--------------------------------------------------------------------
-[000]:null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:004=004 -> null
-[005]:005=005 -> null
-[006]:006=006 -> null
-[007]:007=007 -> null
-[008]:008=008 -> null
-[009]:009=009 -> null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
--------------------------------------------------------------------
011 : 47696 : mod(0)
11, 12, 16
--------------------------------------------------------------------
-[000]:011=011 -> null
-[001]:001=001 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:004=004 -> null
-[005]:005=005 -> null
-[006]:006=006 -> null
-[007]:007=007 -> null
-[008]:008=008 -> null
-[009]:009=009 -> null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
--------------------------------------------------------------------
012 : 47697 : mod(1)
12, 12, 16
--------------------------------------------------------------------
-[000]:011=011 -> null
-[001]:001=001 -> 012=012 -> null
-[002]:002=002 -> null
-[003]:003=003 -> null
-[004]:004=004 -> null
-[005]:005=005 -> null
-[006]:006=006 -> null
-[007]:007=007 -> null
-[008]:008=008 -> null
-[009]:009=009 -> null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
--------------------------------------------------------------------
013 : 47698 : mod(2)
13, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> null
-[020]:004=004 -> null
-[021]:005=005 -> null
-[022]:006=006 -> null
-[023]:007=007 -> null
-[024]:008=008 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
014 : 47699 : mod(19)
14, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> null
-[021]:005=005 -> null
-[022]:006=006 -> null
-[023]:007=007 -> null
-[024]:008=008 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
015 : 47700 : mod(20)
15, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> null
-[022]:006=006 -> null
-[023]:007=007 -> null
-[024]:008=008 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
016 : 47701 : mod(21)
16, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> 016=016 -> null
-[022]:006=006 -> null
-[023]:007=007 -> null
-[024]:008=008 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
017 : 47702 : mod(22)
17, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> 016=016 -> null
-[022]:006=006 -> 017=017 -> null
-[023]:007=007 -> null
-[024]:008=008 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
018 : 47703 : mod(23)
18, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> 016=016 -> null
-[022]:006=006 -> 017=017 -> null
-[023]:007=007 -> 018=018 -> null
-[024]:008=008 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
019 : 47704 : mod(24)
19, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> 016=016 -> null
-[022]:006=006 -> 017=017 -> null
-[023]:007=007 -> 018=018 -> null
-[024]:008=008 -> 019=019 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
020 : 47726 : mod(14)
20, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:020=020 -> null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> 016=016 -> null
-[022]:006=006 -> 017=017 -> null
-[023]:007=007 -> 018=018 -> null
-[024]:008=008 -> 019=019 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
021 : 47727 : mod(15)
21, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:020=020 -> null
-[015]:010=010 -> 021=021 -> null
-[016]:011=011 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> 016=016 -> null
-[022]:006=006 -> 017=017 -> null
-[023]:007=007 -> 018=018 -> null
-[024]:008=008 -> 019=019 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
022 : 47728 : mod(16)
22, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:020=020 -> null
-[015]:010=010 -> 021=021 -> null
-[016]:011=011 -> 022=022 -> null
-[017]:001=001 -> 012=012 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> 016=016 -> null
-[022]:006=006 -> 017=017 -> null
-[023]:007=007 -> 018=018 -> null
-[024]:008=008 -> 019=019 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
023 : 47729 : mod(17)
23, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:020=020 -> null
-[015]:010=010 -> 021=021 -> null
-[016]:011=011 -> 022=022 -> null
-[017]:001=001 -> 012=012 -> 023=023 -> null
-[018]:002=002 -> 013=013 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> 016=016 -> null
-[022]:006=006 -> 017=017 -> null
-[023]:007=007 -> 018=018 -> null
-[024]:008=008 -> 019=019 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
024 : 47730 : mod(18)
24, 24, 32
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:020=020 -> null
-[015]:010=010 -> 021=021 -> null
-[016]:011=011 -> 022=022 -> null
-[017]:001=001 -> 012=012 -> 023=023 -> null
-[018]:002=002 -> 013=013 -> 024=024 -> null
-[019]:003=003 -> 014=014 -> null
-[020]:004=004 -> 015=015 -> null
-[021]:005=005 -> 016=016 -> null
-[022]:006=006 -> 017=017 -> null
-[023]:007=007 -> 018=018 -> null
-[024]:008=008 -> 019=019 -> null
-[025]:009=009 -> null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
--------------------------------------------------------------------
025 : 47731 : mod(19)
25, 48, 64
--------------------------------------------------------------------
-[000]:null
-[001]:null
-[002]:null
-[003]:null
-[004]:null
-[005]:null
-[006]:null
-[007]:null
-[008]:null
-[009]:null
-[010]:null
-[011]:null
-[012]:null
-[013]:null
-[014]:null
-[015]:010=010 -> null
-[016]:011=011 -> null
-[017]:012=012 -> null
-[018]:013=013 -> null
-[019]:014=014 -> null
-[020]:015=015 -> null
-[021]:016=016 -> null
-[022]:017=017 -> null
-[023]:018=018 -> null
-[024]:019=019 -> null
-[025]:null
-[026]:null
-[027]:null
-[028]:null
-[029]:null
-[030]:null
-[031]:null
-[032]:null
-[033]:null
-[034]:null
-[035]:null
-[036]:null
-[037]:null
-[038]:null
-[039]:null
-[040]:null
-[041]:null
-[042]:null
-[043]:null
-[044]:null
-[045]:null
-[046]:020=020 -> null
-[047]:021=021 -> null
-[048]:022=022 -> null
-[049]:001=001 -> 023=023 -> null
-[050]:002=002 -> 024=024 -> null
-[051]:003=003 -> 025=025 -> null
-[052]:004=004 -> null
-[053]:005=005 -> null
-[054]:006=006 -> null
-[055]:007=007 -> null
-[056]:008=008 -> null
-[057]:009=009 -> null
-[058]:null
-[059]:null
-[060]:null
-[061]:null
-[062]:null
-[063]:null
--------------------------------------------------------------------

HashMap 意外と無駄が多いね。。。。

以上。

1
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0