Как увидеть распределение ключей в HashMap?

Ответ 1

Я попробовал подтипирование и повторение таблицы Entry [], но это не видно

Использовать API Reflection!

public class Main {
    //This is to simulate instances which are not equal but go to the same bucket.
    static class A {
            @Override
            public boolean equals(Object obj) { return false;}

            @Override
            public int hashCode() {return 42; }
        }

    public static void main(String[] args) {
            //Test data  
            HashMap<A, String> map = new HashMap<A, String>(4);
            map.put(new A(), "abc");
            map.put(new A(), "def");

            //Access to the internal table  
            Class clazz = map.getClass();
            Field table = clazz.getDeclaredField("table");
            table.setAccessible(true);
            Map.Entry<Integer, String>[] realTable = (Map.Entry<Integer, String>[]) table.get(map);

            //Iterate and do pretty printing
            for (int i = 0; i < realTable.length; i++) {
                System.out.println(String.format("Bucket : %d, Entry: %s", i, bucketToString(realTable[i])));
            }
    }

    private static String bucketToString(Map.Entry<Integer, String> entry) throws Exception {
            if (entry == null) return null;
            StringBuilder sb = new StringBuilder();

            //Access to the "next" filed of HashMap$Node
            Class clazz = entry.getClass();
            Field next = clazz.getDeclaredField("next");
            next.setAccessible(true); 

            //going through the bucket
            while (entry != null) {
                sb.append(entry);
                entry = (Map.Entry<Integer, String>) next.get(entry);
                if (null != entry) sb.append(" -> ");
            }
            return sb.toString();
        }
}

В конце вы увидите что-то подобное в STDOUT:

 Bucket : 0, Entry: null 
 Bucket : 1, Entry: null 
 Bucket : 2, Entry: [email protected]=abc -> [email protected]=def 
 Bucket : 3, Entry: null

Ответ 2

HashMap использует ключи, созданные методом hashCode() ваших ключевых объектов, поэтому, я думаю, вы действительно спрашиваете, как равномерно распределены эти значения хэш-кода. Вы можете получить ключевые объекты с помощью Map.keySet().

Теперь реализации OpenJDK и Oracle HashMap не используют ключевые хэш-коды напрямую, а применяют другую функцию хэширования к предоставленным хэшам, прежде чем распределять их по ведрам. Но вы не должны полагаться на эту деталь реализации или использовать ее. Поэтому вы должны игнорировать это. Поэтому вы должны просто убедиться, что методы hashCode() ваших ключевых значений хорошо распределены.

Изучение фактических хеш-кодов некоторых объектов с образцовыми ключевыми значениями вряд ли скажет вам что-нибудь полезное, если ваш метод хеш-ключа не очень низок. Вы бы лучше сделали базовый теоретический анализ вашего метода хэш-кода. Это не так страшно, как может показаться. Вы можете (действительно, не иметь другого выбора, кроме как сделать это) предположить, что методы хеш-кода поставляемых Java-классов хорошо распределены. Тогда вам просто нужно проверить, что средства, которые вы используете для объединения хеш-кодов для ваших данных, ведут себя хорошо для ожидаемых значений ваших членов данных. Только если ваши члены данных имеют значения, которые сильно коррелируют в своеобразной форме, это может быть проблемой.

Ответ 3

Вы можете использовать отражение для доступа к скрытым полям:

HashMap map = ...;

// get the HashMap#table field
Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);

Object[] table = (Object[]) tableField.get(map);
int[] counts = new int[table.length];

// get the HashMap.Node#next field
Class<?> entryClass = table.getClass().getComponentType();
Field nextField = entryClass.getDeclaredField("next");
nextField.setAccessible(true);

for (int i = 0; i < table.length; i++) {
    Object e = table[i];
    int count = 0;
    if (e != null) {
        do {
            count++;
        } while ((e = nextField.get(e)) != null);
    }
    counts[i] = count;
}

Теперь у вас есть массив счетчиков записей для каждого ведра.

Ответ 4

Client.java

public class Client{
        public static void main(String[] args) {

            Map<Example, Number> m = new HashMap<>();
            Example e1  = new Example(100);  //point 1
            Example e2  = new Example(200);  //point2
            Example e3  = new Example(300);  //point3
            m.put(e1, 10);
            m.put(e2, 20);
            m.put(e3, 30);
            System.out.println(m);//point4
        }
    }

Example.java

public class Example {
    int s;
    Example(int s) {
        this.s =s;
    }
    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return 5;
    }
}

Теперь в точке 1, точке 2 и 3 в Client.java мы вставляем 3 ключа типа Example в hashmap m. Так как hashcode() переопределен в Example.java, все три ключа e1, e2, e3 возвращают одинаковый хэш-код и, следовательно, одно и то же ведро в hashmap.

Теперь проблема заключается в том, как увидеть распределение ключей.

Подход:

• Вставить точку отладки в point4 в Client.java.
• Отладить java-приложение.
• Проверьте m.
• Внутри m вы найдете массив таблиц типа HashMap $ Node и размер 16.
• Это буквально хеш-таблица. Каждый индекс содержит связанный список объектов Entry, которые вставляются в hashmap. Каждый ненулевой индекс имеет хэш-переменную, которая соответствует хеш-значению, возвращаемому методом hash() Hashmap. Это хэш-значение затем отправляется методу indexFor() HashMap, чтобы узнать индекс массива таблицы, в который будет вставлен объект Entry. (Обратите внимание на ссылку @Rahul в комментариях к вопросу, чтобы понять концепцию хэша и indexFor).
• В случае, взятом выше, если мы проверим таблицу, вы найдете все, кроме одного ключа null.
• Мы вставили три ключа, но мы видим только один, т.е. все три ключа были вставлены в одно и то же ведро. Такой же индекс таблицы.
• Осмотреть элемент массива table (в этом случае это будет 5), key соответствует e1, а value соответствует 10 (точка1) Переменная
• next здесь указывает на следующий node связанного списка, т.е. следующий объект Entry, который в нашем случае (e2, 200).

Таким образом, вы можете проверить hashmap.

Также я бы порекомендовал вам пройти внутреннюю реализацию hashmap, чтобы наизусть понять HashMap.

Надеюсь, что это помогло.