Почему в моем обычном закрытом хэш-наборе так много коллизий? - PullRequest
Новая
       5

Почему в моем обычном закрытом хэш-наборе так много коллизий?

4 голосов
/ 26 марта 2012

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

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

Некоторый код (Java): 

public class MyHashSet
{
    private long[] _entries;

    public MyHashSet(int numOfEntries)
    {
        int neededSize = (int)(numOfEntries / 0.65D);
        _entries = new long[neededSize];
    }

    public void add(long num)
    {
        int cell = ((Long) (num % _entries.length)).intValue();

        while (_entries[cell] != 0)
        {
            if (++cell >= _entries.length)  
                cell = 0;                   
        }

        _entries[cell] = num;
    }
...

У меня есть главный, который создаетобъект MyHashSet с 10 миллионами в качестве параметра, затем вызывает add () 10 миллионов раз с другим случайно сгенерированным (но положительным) длинным числом.В то время как на обычном Java HashSet эта вставка в целом занимает около секунды, для завершения с MyHashSet требуется около 13 секунд.Я добавил счетчик для коллизий, и, действительно, количество коллизий составляет 3-6 миллиардов - намного больше, чем ожидалось (я предполагаю, что около 30-40 миллионов ожидается).

Я что-то не так делаю?Что-то не так с самим хэшированием?Почему так много коллизий, и что я могу с этим поделать?

Спасибо!

PS: число 0,65 в коде означает, что таблица заполнится только на 65%,который я знаю, должен хорошо работать в закрытых хэш-сетах.В связи с этим, даже если я установлю его на 20%, вставка по-прежнему занимает> 10 секунд.

- РЕДАКТИРОВАТЬ -

Это довольно неудобно, но мой тестовый кодвоссоздайте объект Random (с System.currentTimeMillis () в качестве начального числа) в каждой итерации цикла, а не используйте один и тот же для всего цикла ..

После исправления требуется около 2-3секунд для вставки.Это все еще кажется слишком большим для сравнения - почему java HashSet по умолчанию вставляется в секунду, когда он более «сложен», чем MyHashSet?Я сейчас получаю около 9 миллионов столкновений.Я также попытался снять код регистрации, чтобы посмотреть, поможет ли он, но это все равно не поможет.Буду признателен за любые идеи и еще раз прошу прощения за путаницу.

Ответы [ 2 ]

3 голосов
/ 26 марта 2012

Первое, что я замечаю, это безвозмездный бокс на линии 

int cell = ((Long) (num % _entries.length)).intValue();

, который намного медленнее, чем 

int cell = (int) (num % _entries.length);

(обратите внимание, что num % _entries.length всегда будет помещаться в int, поскольку _entries.length сам по себе int.)

Следует признать, что Java 1013 * все равно будет страдать от подобных издержек, но это по крайней мере одна очевидная вещь, которую нужно исправить.

ТакжеВероятно, в ваших интересах убедиться, что размер таблицы является простым числом.Самый простой способ сделать это - BigInteger.valueOf((int)(numOfEntries / 0.65)).nextProbablePrime().intValue(), и, поскольку это единовременные затраты, это не должно слишком сильно повлиять на общую производительность.

С другой стороны, в Java HashSet используются размеры хеш-таблиц степени 2, поэтому он может использовать маску (в основном value & (_entries.length - 1)), а не %, что зачастую дороже.

1 голос
/ 26 марта 2012

Первый: исправьте свою функцию по модулю. В противном случае вы получите исключения ArrayOutOfBounds, и их легко исправить, не прибегая к реальным затратам производительности (только и). Кроме того, если вы на это, сделайте то, что предлагает Луи, и избавьтесь от бесполезного длинного состава.

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

Тогда вы должны либо использовать простое число для размера таблицы, как предлагает Луи, который имеет некоторые (теоретически доказуемые) преимущества, но медленнее, либо использовать следующую степень 2. В данный момент вы комбинируете недостатки обоих подходов. .

...