Каков эффективный HashCode () для малых значений x, больших y?

m отображает значения x, y на декартову плоскость с помощью HashMap. Каким будет эффективный HashCode для очень маленьких значений x, очень больших значений y?

В настоящее время я использую:

 public int hashCode() {
    return ((y * 31) ^ x);

 // & Typical x,y values would be, (with many collisions on x):
  [4, 1000001] [9, 1000000] [5, 999996] [6, 999995] [4, 999997] 
  [6, 999997] [6, 1000003] [10, 999994] [8, 999997] [10, 999997] 
  [5, 999999] [4, 999998] [5, 1000003] [2, 1000005] [3, 1000004] 
  [6, 1000000] [3, 1000005]

Я вставляю обе пары x, y в ключ хэш-карты с помощью метода .put, чтобы избежать дублирования пар x, y. Не уверен, что это самое эффективное решение.

 Makoto10 нояб. 2012 г., 02:57
Можете ли вы гарантировать, что ценности нет превышает 2 ^ 63-1? Я'буду следить за очень большими значениями y, как это.

Ответы на вопрос(3)

Решение Вопроса

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

Я запустил эту программу и получил 0 столкновений:

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class Testing {

    public static void main(String[] args) {
        int minX = 0;
        int minY = 100000;
        int maxX = 20;
        int maxY = 2000000;

        Map<integer, integer=""> hashToCounts = new HashMap<integer, integer="">();
        for (int x = minX; x < maxX; x++) {
            for (int y = minY; y < maxY; y++) {
                int hash = hash(x, y);
                Integer count = hashToCounts.get(hash);
                if (count == null)
                    count = 0;
                hashToCounts.put(hash, ++count);
            }
        }

        int totalCollisions = 0;
        for (Entry<integer, integer=""> hashCountEntry : hashToCounts.entrySet())
            if (hashCountEntry.getValue() > 1)
                totalCollisions += hashCountEntry.getValue() - 1;

        System.out.println("Total collisions: " + totalCollisions);
    }

    private static int hash(int x, int y) {
        return 7 + y * 31 + x * 23;
    }
}
</integer,></integer,></integer,>

И вывод:

Всего столкновений: 0

Обратите внимание, что моя функция была.7 + y * 31 + x * 23

Конечно, нене поверьте мне на слово. Вмешайтесь в диапазоны, чтобы настроить его на свой набор данных и попробуйте рассчитать его самостоятельно.

Используя ваш(y * 31) ^ x дал мне:

Всего столкновений: 475000

И используя только:x * y

Всего столкновений: 20439039

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

Вот некоторые хорошие правила для хэширования:

Перепутайте своих операторов. Смешивая операторов, вы можете сделать так, чтобы результаты варьировались больше. Используя простоx * y в этом тесте у меня было очень большое количество столкновений.Используйте простые числа для умножения. Простые числа имеют интересные двоичные свойства, которые делают умножение более изменчивым.Избегайте использования операторов сдвига (если вы действительно не знаете, что выделаю). Они вставляют множество нулей или единиц в двоичное число, уменьшая волатильность других операций и потенциально даже сокращая возможное количество выходов.

x * y будет хорошо работать, особенно если результат будет соответствовать.int

Вы можете использовать HashSet: это 'Внутренне HashMap с только ключами, без значений. Это сделало бы намерение избежать дублирования более очевидным.

трудно предсказать. HashMap выполняет некоторую перефразировку, используя метод hash (), показанный ниже, затем берет младшие биты X. Итак, в идеальном мире, игнорируя метод hash (), который мешает, ваши младшие биты должны быть хорошо распределены.

static int hash(int h) {
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

Я обычно начинаю с чего-то действительно простого, например x ^ y (или x смещено на что-то ^ y или наоборот), и создайте HashMap и посмотрите, не слишком ли много коллизий.

Ваш ответ на вопрос