Я создал несколько реализация hashCode целого числа для использования в hashTable, но ни один из них, по-видимому, не закрыл равномерное распределение. Итак, какова была бы лучшая реализация hashCode целого числа, предполагающего размер хэш-таблицы, около сотни, а целые числа - порядка нескольких тысяч? Заранее спасибо.Какова наилучшая реализация hashCode целого числа?
Я предлагаю «лучшую» реализацию, что бы это значит, почти наверняка
Integer.valueOf(value).hashCode()
И, согласно [Java docs] (http://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#hashCode()), метод hashCode() ' 'Integer' возвращает примитивное значение' int', представленное 'Integer'. –
Ну ... Я не думаю, что решение _generic_ обязательно является лучшим. На самом деле оптимизация состоит в том, чтобы опровергаться вместо обобщения. –
Поскольку ваш хэш-таблица достаточно мала, функция по модулю будет самой простой реализацией, и если входные случайные числа, распределение должно быть случайным.
public int hashCode(int x){
return x%tableSize;
}
Лучшая реализация будет заключаться в использовании умножения, как описано here.
(x*someNumber) % table size;
другие функции хеширования описаны here, проверить их. Надеюсь, это поможет.
Если ключи ваших данных равномерно распределены, просто используйте целое число как ключ. Если ваши ключи неравномерно распределены, вам необходимо изменить целое число таким образом, чтобы его распределение было более равномерно по спектру всех целых чисел. Как это сделать, зависит от того, как распределяются ваши ключи и точная реализация карты.
Вы уверены, что не используете преждевременную оптимизацию? На карте всего 100 записей это действительно не имеет большого значения, если у вас есть постоянное время поиска (отлично распределенное) или линейное время поиска (каждая запись имеет ключевое столкновение). Итерирование 100 пунктов происходит так быстро, за пределами бенчмаркинга вы, скорее всего, не заметите разницы. Было бы интересно оценить, не будет ли список в среднем быстрее, чем карта с таким небольшим набором данных.
Итак, вы тысяч значений по оси X, и вы хотите, чтобы «превратить» их в гораздо меньший диапазон, от сотни, по оси Y. Очевидно, вы можете разделить на 10 или получить модуль, но вы также хотите распределить их как можно более равномерными вдоль целевого диапазона.
Я думаю, вам нужна функция сжатия.
Вы можете, например, применить к вводу функцию sine и умножить на размер хеш-таблицы. Какое значение должно иметь период? Это зависит: чем ближе вы ожидаете входные значения, тем более высокий период (так что два близких значения будут давать два очень разных результата). И наоборот: если ожидаемые значения входных значений не будут близки, это может сделать небольшой период.
private int hashCode(int input, int tableSize)
{
return (int)(tableSize*Math.sin(PERIOD*input));
}
функция лавина Доработка из MurmurHash3:
int h = key;
h ^= h >>> 16;
h *= 0x85ebca6b;
h ^= h >>> 13;
h *= 0xc2b2ae35;
h ^= h >>> 16;
Почему бы не просто использовать само целое, как его собственный хэш? –
Если ваши исходные целые числа хорошо распределены, вы можете применить '% 100' как hashcode – dotvav
Поскольку набор из 32-битных целых чисел равномерно распределен сам по себе, я предполагаю, что у вас есть конкретное подмножество целых чисел, с которыми вы работаете, , Поэтому вам необходимо рассмотреть ограничения на ваши данные и их фактическое распределение, чтобы разработать хэш-код, который равномерно распределяет это подмножество. Вы не указали эту информацию в своем вопросе. – RealSkeptic