Вопрос по производительности HashTable узлов LinkedList - PullRequest
Новая
       8

Вопрос по производительности HashTable узлов LinkedList

0 голосов
/ 09 ноября 2018

Я реализовал HashTable с сегментами переменного размера при инициализации класса, просто массив связанных списков, измеренных во время выполнения.

Проблема заключается в том, что при небольшом количестве сегментов, в которых должен быть пройден связанный список (может достигать приблизительно 5 тыс. Узлов глубиной), он превосходит HashTable с большим количеством сегментов, различающихся на три порядка больше. 

    int SMALL_BUCKET_SIZE = 10;
    int BIG_BUCKET_SIZE = 10000;

    HashTable<String, Integer> smallHashTable = new HashTable<>(SMALL_BUCKET_SIZE);
    HashTable<String, Integer> bigHashtTable = new HashTable<>(BIG_BUCKET_SIZE);

Я бы ожидал, что большая HashTable будет O (1) для поиска, где меньшая хеш-таблица имеет более высокую частоту столкновений, что занимает больше времени из-за обхода связанных узлов, но мои цифры ниже показывают меньшую таблицу, превосходящую более широкую. таблица.

Fetch SmallTable: 0.000007
Fetch BigTable: 0.000018

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

Fetch SmallTable: 0.0000013630
Fetch BigTable: 0.0000002560

Мой вопрос касается правильности моей логики, а также дополнительных движущихся частей здесь. Я вставил свой тест вместе со ссылкой на реализацию HashTable и базовых структур Node.

Ищет глубину / опыт от людей, которые могут предоставить интерактивную обратную связь относительно переменных, которые влияют на это, таких как длина ключа и частота хэширования, плотность сегментов и т. Д.

HashTableTest.java 

@Test
public void canInitializeHashTableWithBucketsForPerformance() throws InterruptedException {
    double smallTableTime, bigTableTime;
    int SMALL_BUCKET_SIZE = 10;
    int BIG_BUCKET_SIZE = 10000;

    HashTable<String, Integer> smallHashTable = new HashTable<>(SMALL_BUCKET_SIZE);
    HashTable<String, Integer> bigHashtTable = new HashTable<>(BIG_BUCKET_SIZE);
    List<String> strings = generateRandomStringKeys(1000);

    strings.forEach(string -> bigHashtTable.put(string, 10));
    strings.forEach(string -> smallHashTable.put(string, 10));

    Consumer<String> bigHashGet = bigHashtTable::get;
    Consumer<String> smallHashGet = smallHashTable::get;

    String theString = strings.get(strings.size() - 1);

    smallTableTime = getElapsedTimeFactoringOutJavaOptimization(theString, smallHashGet);
    bigTableTime = getElapsedTimeFactoringOutJavaOptimization(theString, bigHashGet);

    System.out.println(String.format("Fetch SmallTable: %.10f", smallTableTime));
    System.out.println(String.format("Fetch BigTable:   %.10f", bigTableTime));

    assertTrue(smallTableTime > bigTableTime);
}

public double getElapsedTimeFactoringOutJavaOptimization(String s, Consumer<String> aMethod) {
    long start = 0, end = 0;

    for (int i = 0; i < 1000; i++) {
        start = System.nanoTime();
        aMethod.accept(s);
        end = System.nanoTime();
    }

    return (end - start) / 1_000_000_000D;
}

public List<String> generateRandomStringKeys(int numOfRandomKeys) {
    List<String> keys = new ArrayList<>();

    for (int i = 0; i < numOfRandomKeys; i++) {
        byte[] array = new byte[10];
        new Random().nextBytes(array);
        keys.add(new String(array, Charset.forName("UTF-8")));
    }

    return keys;
}

Тест можно найти здесь - Github - HashTableTest.java

Здесь также можно найти реализацию - Github - HashTable.java

1 Ответ

0 голосов
/ 09 ноября 2018

Здесь много чего не так, но несколько включают:

  • Выполнение этой операции 1000 раз и взятие разницы nanoTime для каждого из них не делает ваш эталон действительным. Серьезно, используйте JMH. Или, по крайней мере, запустить его примерно десять миллионов раз.
  • Ваша хеш-таблица на самом деле не работает по-разному для таблиц разных размеров. Вы используете table[getHash(key) % RADIX], что в основном означает однако большой размер таблицы, вы используете в ней только 10 сегментов и делаете вид, что остальные не существуют.
  • System.identityHashCode не является полезной хэш-функцией, особенно для строк, особенно когда вы надеетесь найти элемент, который там находится ... или нет.
  • Пока вы на нем, вы не используете Node.next в качестве поля и с тем же успехом можете от него избавиться.
...