Почему чем больше «1» битов в моем ключе, тем больше времени требуется для помещения в хэш-карту?

Question

Я делаю проект для класса, который фокусируется на хранении огромной матрицы с почти 0 значениями в памяти и выполнении некоторой математической математики для нее. Моей первой мыслью было использовать HashMap для хранения элементов матрицы и хранить только ненулевые элементы, чтобы избежать использования огромных объемов памяти.

Я хотел создать ключ для HashMap, который бы представлял номер строки и столбца элемента таким образом, чтобы при доступе к этой записи на карте я мог повторно извлечь оба значения. Я не знаю Java так же хорошо, как C # - в C # я бы сделал struct с Row и Column членами, но в Java я быстро понял, что типов пользовательских значений нет. С приближением крайнего срока я сделал безопасную ставку и сделал Key длинной. Я сохранил данные строки (32-битное целое) в первых 32 битах и ​​данные столбца в последних 32, используя очень простое смещение битов. [РЕДАКТИРОВАТЬ: Я также хотел бы отметить, что мой HashMap инициализируется с определенным начальным размером, который точно представляет количество значений, которые я храню в нем, и никогда не превышается.]

[Примечание: причина, по которой я хочу иметь возможность снова извлекать данные строки / столбца, заключается в значительном увеличении эффективности умножения матриц, с O(n^2) до O(n) и меньшего n для загрузки]

Что я заметил после реализации этой структуры, так это то, что для считывания матрицы 23426 x 23426 из текстового файла, в котором заданы только ненулевые элементы, требуется колоссальные 7 секунд, но для вычисления собственных значений требуется всего 2 секунды. мы обязаны дать! После выборочного комментирования методов я пришел к выводу, что большая часть этого 7-секундного промежутка времени расходуется на сохранение моих значений в HashMap.

public void Set(double value, int row, int column) {
    //assemble the long key, placing row and column in adjacent sets of bits
    long key = (long)row << SIZE_BIT_MAX; //(SIZE_BIT_MAX is 32)
    key += column;
    elements.put(key, value);
}

Это код для установки значения. Если я использую этот метод вместо:

public void Set(double value, int row, int column) {
    //create a distinct but smaller key (around 32 bits max)
    long key = (long)(row * matrixSize) + column;
    elements.put(key, value);
}

Чтение занимает всего 2 секунды. Обе эти версии ключа различны для каждого элемента, оба имеют длинный тип, и фактический код для создания любого из них имеет минимальную сложность. Это elements.put(key, value), который составляет разницу между 7 секундами и 2.

Мой вопрос: почему? Различие, которое я вижу между этими ключевыми версиями, состоит в том, что первая имеет биты, установленные на 1 повсюду и чаще, в то время как вторая имеет все свои старшие 32 бита, установленные на 0. Я гоняюсь за красной сельдью, или это довольно существенная разница? в производительности результат чего-то внутреннего в методе HashMap.put?

Answer 1

Посмотрите, как Long реализует метод hashCode() (по крайней мере, в OpenJDK 7):

public int hashCode() {
    return (int)(value ^ (value >>> 32));
}

Это означает, что ваш ключ вставляется обратно в 32 бита; все младшие биты довольно часто взаимно компенсируют друг друга, что приводит к множеству коллизий, которые требуют HashMap, чтобы тратить дополнительное время на поиск свободного слота в корзине. Ваш второй метод позволяет избежать этой проблемы, поскольку каждый сгенерированный хэш-код ключа является уникальным значением (поскольку у вас есть только 23426 x 23426 = 548777476 элементов, которые хорошо вписываются в 32 бита).

Итак, причиной является выбор ключа, а не количество установленных битов.

Однако, что именно вы имеете в виду под «типами пользовательских значений?»

public class MatrixKey {
    private final int row;
    private final int column;
    public MatrixKey(int row, int column) {
        this.row = row;
        this.column = column;
    }
    public int getRow() { return row; }
    public int getColumn() { return column; }
}

Этот класс может стать отличным ключом для Map в Java, если вы реализуете hashCode() и equals(). Просто убедитесь, что вы не реализуете его метод hashCode, как это делает Long. :)

Answer 2

Из документации JDK 6 для Long.hashCode() (обратите внимание, что ваш примитив long автоматически помещается в объект Long - тогда как в примитивах C # на самом деле являются объектами):

Возвращает хэш-код для этого Long.Результатом является исключающее ИЛИ двух половин примитивного значения long, которое содержится в этом объекте Long.То есть, хеш-код является значением выражения:

(int)(this.longValue()^(this.longValue()>>>32))

Я думаю, что с учетом этого определения это объясняет, почему:

частота столкновений уменьшается, когда вывводить больше энтропии и таким образом распределять ее больше через верхнюю половину значения long. ( edit : я неправильно прочитал порядок, поэтому вот контр-аргумент ниже)

Коллизии могут быть более вероятными при расширении до диапазона long - в конце концов, в Java хэш-коды имеют размер int, поэтому вы можете иметь только ограниченное количество одинакового распределения.Если вы знаете, что оно «равномерно» распределено по диапазону int, тогда ваши коллизии уменьшаются.Если вы распространите это по диапазону long, это значительно увеличит ваши шансы на столкновение.

Вот из HashMap документации Java (выделено мной):

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

Примечание: вы получите еще больший прирост производительности, настроив initial capacity и load factor - обратитесь к документации HashMap для получения дополнительной информации.

Answer 3

В зависимости от реализации вы можете столкнуться с хеш-коллизиями.

Если все ваши хеш-значения окажутся в одном и том же «контейнере», реализация обычно выбрасывает их в список некоторого типа.В этом случае время доступа значительно сократится.