Написать хеш-функцию в Java

Question

Я пытаюсь создать структуру данных HashMap() в Java.HashMap должен работать максимум N = 1000 операций, а ключи - только положительные целые числа.Я сделал следующее:

class MyHashMap {
        final ListNode[] nodes = new ListNode[1000];
        // "put", "get" and "remove" methods which take
        // collisions into account using "chaining".
}

, чтобы принять решение о размещении моей новой пары ключ-значение в nodes Мне всегда нужно вычислять индекс.Я использую функцию:

 public int getIndex(int key) { return Integer.hashCode(key) % nodes.length;}

, которая возвращает целое число от 0 до nodes.length.Но как я могу написать Hash-функцию в Java самостоятельно, которая отображает целые числа в некоторый индекс без использования Integer.hashMap(key)?Кроме того, процедура в порядке, мне не нужен код.

Answer 1

Ну, во-первых, hash - это нечто уникальное или очень редко повторяющееся значение.

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

public int get(int key) {
    return (-1 ^ key) % nodes.length;
}

Answer 2

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

ПРИМЕЧАНИЕ. Если вы не знаете, что ключ не может быть отрицательным, вы должны использовать Math.abs, чтобы убедиться, что он неотрицательный.

static final int K = 0x7A646E4D; // some large prime.

public int getIndex(int key) { 
    return Math.abs(key * K % nodes.length);
}

Более быстрое решение - отказаться от использования %, использовать умножение и сдвиг. например,

public int getIndex(int key) { 
    return (int) ((key * K & 0xFFFF_FFFFL) * nodes.length >>> 32);
}

Это превращает key * K в дробь и работает быстрее, чем %

Answer 3

Integer.hashCode(key) просто возвращает key как результат.Вы можете написать:

public int getIndex(int key) { 
    return key % nodes.length;
}

Таким образом, вы не используете Integer.hashCode(key).

Не видя ваш класс ListNode, у вас может возникнуть проблема с вашей структурой MyHashMap, поскольку вы устанавливаете множество элементов для одного элемента массива.Например, ключи 3 и 1003 будут сохранены в одном элементе узла.Вы должны сделать MyHashMap списком списка (или массивом списков или чем-то подобным).