Простой целочисленный хэш-набор Java

(См. Следующую версию.)

Следующая структура данных реализует набор на основе хэш-таблицы для int ценности:

com.github.coderodde.util.IntHashSet

package com.github.coderodde.util;

/**
 * This class implements a simple hash set for non-negative {@code int} values.
 * It is used in the {@link com.github.coderodde.util.LinkedList} in order to 
 * keep track of nodes that are being pointed to by fingers.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Aug 29, 2021)
 * @since 1.6 (Aug 29, 2021)
 */
class IntHashSet {

    private static final int INITIAL_CAPACITY = 8;
    private static final float MAXIMUM_LOAD_FACTOR = 0.75f;

    static final class IntHashTableCollisionChainNode {
        IntHashTableCollisionChainNode next;
        int integer;

        IntHashTableCollisionChainNode(
                int integer, 
                IntHashTableCollisionChainNode next) {
            this.integer = integer;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Chain node, integer = " + integer;
        }
    }

    void add(int integer) {
        if (contains(integer)) {
            return;
        }

        size++;

        if (shouldExpand())
            expand();

        final int targetCollisionChainIndex = integer & mask;
        final IntHashTableCollisionChainNode newNode = 
                new IntHashTableCollisionChainNode(
                        integer, 
                        table[targetCollisionChainIndex]);

        newNode.next = table[targetCollisionChainIndex];
        table[targetCollisionChainIndex] = newNode;
    }

    boolean contains(int integer) {
        final int collisionChainIndex = integer & mask;
        IntHashTableCollisionChainNode node = table[collisionChainIndex];

        while (node != null) {
            if (node.integer == integer) {
                return true;
            }

            node = node.next;
        }

        return false;
    }

    void remove(int integer) {
        if (!contains(integer)) {
            return;
        }

        size--;

        if (shouldContract()) 
            contract();

        final int targetCollisionChainIndex = integer & mask;

        IntHashTableCollisionChainNode current = 
                table[targetCollisionChainIndex];

        IntHashTableCollisionChainNode previous = null;

        while (current != null) {
            IntHashTableCollisionChainNode next = current.next;

            if (current.integer == integer) {
                if (previous == null) {
                    table[targetCollisionChainIndex] = next;
                } else {
                    previous.next = next;
                }

                return;
            }

            previous = current;
            current = next;
        }
    }

    public void clear() {
         size = 0;
         table = new IntHashTableCollisionChainNode[INITIAL_CAPACITY];
         mask = table.length - 1;
    }

    private IntHashTableCollisionChainNode[] table = 
            new IntHashTableCollisionChainNode[INITIAL_CAPACITY];

    private int size = 0;
    private int mask = INITIAL_CAPACITY - 1;

    // Keep add(int) an amortized O(1)
    private boolean shouldExpand() {
        return size > table.length * MAXIMUM_LOAD_FACTOR;
    }

    // Keep remove(int) an amortized O(1)
    private boolean shouldContract() {
        if (table.length == INITIAL_CAPACITY) {
            return false;
        }

        return MAXIMUM_LOAD_FACTOR * size * 4 < table.length;
    }

    private void expand() {
        IntHashTableCollisionChainNode[] newTable = 
                new IntHashTableCollisionChainNode[table.length * 2];

        rehash(newTable);
        table = newTable;
        mask = table.length - 1;
    }

    private void contract() {
        IntHashTableCollisionChainNode[] newTable = 
                new IntHashTableCollisionChainNode[table.length / 4];

        rehash(newTable);
        table = newTable;
        mask = table.length - 1;
    }

    private void rehash(IntHashTableCollisionChainNode[] newTable) {
        for (IntHashTableCollisionChainNode node : table) {
            while (node != null) {
                final IntHashTableCollisionChainNode next = node.next;
                final int rehashedIndex = rehash(node.integer, newTable);

                node.next = newTable[rehashedIndex];
                newTable[rehashedIndex] = node;
                node = next;
            }
        }
    }

    private static int rehash(
            int integer, 
            IntHashTableCollisionChainNode[] newTable) {
        return integer & (newTable.length - 1);
    }
}

com.github.coderodde.util.IntHashSetTest

package com.github.coderodde.util;

import java.util.Random;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Before;
import org.junit.Test;

public class IntHashSetTest {

    private final IntHashSet set = new IntHashSet();

    @Before
    public void beforeTest() {
        set.clear();
    }

    @Test
    public void add() {
        for (int i = 0; i < 500; i++) {
            set.add(i);
        }

        for (int i = 0; i < 500; i++) {
            assertTrue(set.contains(i));
        }

        for (int i = 500; i < 1_000; i++) {
            assertFalse(set.contains(i));
        }

        for (int i = 450; i < 550; i++) {
            set.remove(i);
        }

        for (int i = 450; i < 1_000; i++) {
            assertFalse(set.contains(i));
        }

        for (int i = 0; i < 450; i++) {
            assertTrue(set.contains(i));
        }
    }

    @Test
    public void contains() {
        set.add(10);
        set.add(20);
        set.add(30);

        for (int i = 1; i < 40; i++) {
            if (i % 10 == 0) {
                assertTrue(set.contains(i));
            } else {
                assertFalse(set.contains(i));
            }
        }
    }

    @Test
    public void remove() {
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        set.add(5);

        set.remove(2);
        set.remove(4);

        set.add(2);

        assertFalse(set.contains(4));

        assertTrue(set.contains(1));
        assertTrue(set.contains(2));
        assertTrue(set.contains(3));
        assertTrue(set.contains(5));
    }

    @Test
    public void clear() {
        for (int i = 0; i < 100; i++) {
            set.add(i);
        }

        for (int i = 0; i < 100; i++) {
            assertTrue(set.contains(i));
        }

        set.clear();

        for (int i = 0; i < 100; i++) {
            assertFalse(set.contains(i));
        }
    }

    @Test 
    public void bruteForceAdd() {
        long seed = System.currentTimeMillis();

        System.out.println(
                "--- IntHashSetTest.bruteForceAdd: seed = " + seed + " ---");

        Random random = new Random(seed);

        int[] data = new int[10_000];

        for (int i = 0; i < data.length; i++) {
            int datum = random.nextInt(5_000);
            data[i] = datum;
            set.add(datum);
        }

        for (int i = 0; i < data.length; i++) {
            assertTrue(set.contains(data[i]));
        }
    }

    @Test
    public void bruteForceRemove() {
        long seed = System.currentTimeMillis();

        System.out.println(
                "--- IntHashSetTest.bruteForceRemove: seed = " + seed + " ---");

        Random random = new Random(seed);

        int[] data = new int[10_000];

        for (int i = 0; i < data.length; i++) {
            int datum = random.nextInt(5_000);
            data[i] = datum;
            set.add(datum);
        }

        shuffle(data, random);

        for (int i = 0; i < data.length; i++) {
            int datum = data[i];

            if (set.contains(datum)) {
                set.remove(datum);
            } 

            assertFalse(set.contains(datum));
        }
    }

    private static void shuffle(int[] data, Random random) {
        for (int i = data.length - 1; i > 0; --i) {
            final int j = random.nextInt(i + 1);
            swap(data, i, j);
        }
    }

    private static void swap(int[] data, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

Запрос на критику

Пожалуйста, расскажите мне все, что придет в голову! ^^

5 ответов
5

Ошибка: массив слишком сильно сжимается

Логика в shouldContract похоже, он предназначен для предотвращения уменьшения размера ниже INITIAL_CAPACITY, но этого не происходит. Например, предположим, что текущий размер таблицы равен 16, тогда table.length == INITIAL_CAPACITY ложно и MAXIMUM_LOAD_FACTOR * size * 4 < table.length может быть истинным, поэтому выполняется изменение размера, и новый размер равен 4. Затем table.length == INITIAL_CAPACITY является все еще ложь, а также MAXIMUM_LOAD_FACTOR * size * 4 < table.length снова может быть истинным, если будет удалено больше элементов, и следующий размер будет равен 1. Вы можете видеть, к чему это идет: следующий размер после этого будет равен нулю. Это приводит к сбою повторного хеширования.

Код для воспроизведения:

for (int i = 0; i < 9; i++)
    set.add(i);
for (int i = 0; i < 9; i++)
    set.remove(i);

Модификаторы доступа несовместимы

clear является public но остальная часть «общедоступного интерфейса» имеет уровень доступа по умолчанию, который может быть нормальным, но тогда почему clear общественные. Рекомендую выбрать один из них.

Неотрицательный?

В описании сказано, что это набор для неотрицательных целых чисел, но, похоже, он подходит для любых целых чисел.

Слабый хеш (идентификационный хеш)

Идентификационное хеширование (т.е. использование значения в качестве хэш, применяя только сокращение диапазона) для целых чисел в основном работает, но может легко привести к неравномерному распределению некоторых значений по сегментам. Например, если все значения четные (или все нечетные), то используется только половина сегментов. Или, если все значения кратны 256, то можно использовать только 1 из 256 сегментов. Во многих случаях этого просто не произойдет, потому что входные данные хорошо распределены, но набор целых чисел, кратных степени двойки, не является редкостью. Опасность может быть уменьшена (не устранена полностью, но наборы значений, которые вызывают плохое поведение) с участием хеширование – довольно необычные наборы) путем применения некоторого “диффузного” биективного преобразования к значению перед его уменьшением, например (заимствуя “финализатор хеширования” из MurmurHash3):

static int hash(int x) {
    x ^= x >>> 16;
    x *= 0x85ebca6b;
    x ^= x >>> 13;
    x *= 0xc2b2ae35;
    x ^= x >>> 16;
    return x;
}

// elsewhere in the code ...
int targetCollisionChainIndex = hash(integer) & mask;

Конечно, здесь есть компромисс: этот хеш нельзя оценивать бесплатно.

    Просто неупорядоченный список вещей, которые пришли мне в голову:

    • У вас есть два rehash() методы, делающие очень разные вещи, int-возврат одного, вычисляя индекс для целого числа содержимого, а другой void один делает процесс перефразирования.

    • У вас есть (по крайней мере) два места, где вы вычисляете индекс массива для целого числа содержимого, одно из которых находится внутри add() метод, другой – int rehash() метод.

    • Вы заново изобрели колесо. Функционально HashSet<Integer> выполняет свою работу, хорошо протестирован и оптимизирован. Возможно, вы сделали свою реализацию из соображений эффективности, но я сомневаюсь, что ваш класс превосходит HashSet<Integer> относительно времени выполнения или объема памяти. Но если у вас есть данные о производительности, мне было бы любопытно их увидеть.

    • Ваше «хеширование» с использованием битовой маски может привести к ненужным конфликтам в некоторых (весьма вероятных) случаях использования.

    • Вы используете односвязный список в сегментах. В ваших тестовых примерах для remove() Я не нашел явных для крайних случаев: удаление первой записи и удаление последней записи из списка. Случайные тесты могут покрыть это с некоторой вероятностью, но «некоторая вероятность» – плохая идея для тестирования.

    • Встроенный JDK HashSet<Integer> на самом деле довольно плохо оптимизированная реализация. Это не только тратит время и память из-за примитивного (не) бокса, но и фактически HashMap маскируется и, таким образом, также тратит впустую пространство для хранения указателей на неиспользуемые значения карты и время для их обновления. Он также довольно склонен к столкновениям, и, хотя он справляется с ними прилично хорошо (по сути, возвращается к TreeMap), что само по себе добавляет немного сложности и накладных расходов на производительность. Что-то вроде HPPC IntHashSet было бы гораздо лучшим сравнением.

      – Илмари Каронен



    1. IntHashTableCollisionChainNode уже вложен в IntHashSet, делая IntHashTable часть его названия избыточна. Плюс тот факт, что он является частью «цепочки», подразумевается тем, как он используется, на самом деле это не свойство самого класса.

      Подумайте, возможно, просто IntHashSet.Node.

    2. IntHashTableCollisionChainNode может быть private

    3. Вы не указали, какую версию Java используете, но если она выше 10, вам следует использовать var для вывода типа по локальным переменным. Это снизит частоту таких вещей, как:

      final IntHashTableCollisionChainNode newNode = 
                  new IntHashTableCollisionChainNode(
                          integer, 
                          table[targetCollisionChainIndex]);
      

      Что может просто стать:

      final var newNode = new Node(integer, table[targetCollisionChainIndex]);
      
    4. Маркировка локальных переменных в Java довольно утомительна. ИМО, это много шума без особой отдачи. Взгляните на ключевые слова, используемые для объявления констант и переменных на разных языках:

       Language   | Constant keyword | Mutable keyword
      ------------|------------------+-----------------
       Java       | final            | <blank>
       JavaScript | const            | let
       Swift      | let              | var
       Rust       | let              | let mut
      

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

    Хороший, но я не согласен final: если ничего другого, он документирует, что переменная / ссылка не изменилась в текущем методе.

    – кодеродде

    Представление

    Если принять во внимание скорость (что кажется целью, так как нет никакой системы безопасности, такой как HashSet есть), я бы сказал, что вы в хорошем состоянии, но некоторые улучшения можно сделать.

    • Проверка contains Внутри add а также removes делает цикл кода дважды через узлы, когда элемент отсутствует. Подумайте о том, чтобы проверить позже в своем add а также remove метод.
    • Рассмотрите возможность кэширования часто используемых чисел, таких как table.length * MAXIMUM_LOAD_FACTOR знак равноnextExpandSize?).

    Читаемость

    Мне сложно читать код. Я читал несколько кодов, связанных с производительностью, и они стали более разборчивыми.

    • Рассмотрите возможность переименования IntHashTableCollisionChainNode чтобы просто Node. Он выражает то же самое, но намного короче.
    • Теперь мы близки к Java 17. Просто используйте var вместо полного имени типа.
    • Удалить final для локальных переменных. В вашем коде нет абсолютно никакой дополнительной ценности, тем более что в Java теперь есть концепция эффективных конечных переменных.
    • Рассмотрите возможность слияния expand а также contract в resize с параметром: код абсолютно идентичен, за исключением нового размера.
    • ИЛИ рассмотрите возможность слияния shouldExpand а также expand вместе (expandIfNeeded), а также shouldContract а также contract (contractIfNeeded).
    • Есть магические числа, такие как 4 а также 2. Выразите их как константы, такие как EXPAND_FACTOR а также CONTRACT_FACTOR.

    Тестирование

    • В bruteForceAdd а также bruteForceRemove тесты не воспроизводятся, потому что начальное число является текущей меткой времени. Если ваша реализация содержит ошибки, у вас может быть тот же тест, который иногда проходит успешно, а иногда – нет. Тесты на воспроизводимость. Так что лучше иметь постоянное семя.
    • В bruteForceRemove еще более проблематично, потому что есть условное удаление. Я бы написал это так:
    for (int i = 0; i < 10000; i++) {
      data[i] = i;
      set.add(i);
    }
    
    shuffle(data);
    
    for (var i : data) {
      assumeTrue(data.contains(i)); // not assert.
      data.remove(i);
      assertFalse(data.contains(i));
    }
    

      Я не собираюсь тратить время на детали вашей реализации, так как я думаю, что вы лаете не на то дерево.

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

      Рассмотрение источника java.util.EnumSet и java.util.JumboEnumSet может быть полезным в качестве примера обработки растрового изображения (фиксированного размера). Немного изобретательности покажет, как можно динамически изменять размер дизайна.

      Замечу, что в вашем коде нет синхронизации. Вы собираетесь добавить это, если синхронный доступ будет обеспечиваться пользователем или должна быть доступна оболочка? Если вы заставили свой класс реализовать интерфейс Set <>, тогда можно было бы использовать механизм оболочки SynchronizedSet …

        Добавить комментарий

        Ваш адрес email не будет опубликован. Обязательные поля помечены *