Хорошая хеш-функция для использования в интервью для целых чисел, строк?

Ответ 1

Вот простой рецепт Эффективная java страница 33:

• Хранить некоторое постоянное ненулевое значение, например, 17, в переменной int, называемой результатом.
• Для каждого значимого поля f в вашем объекте (каждое поле, принятое во внимание равный метод, то есть), выполните следующие действия:
  • Вычислить код х хеш-кода для поля:
    • Если поле является логическим, вычислить (f? 1: 0).
    • Если поле является байтом, char, short или int, compute (int) f.
    • Если поле длинное, вычислите (int) (f ^ (f → > 32)).
    • Если поле является поплавком, вычислите Float.floatToIntBits(f).
    • Если поле является двойным, вычислите Double.doubleToLongBits(f) и затем хеш, полученный в результате так же, как на этапе 2.1.iii.
    • Если поле является ссылкой на объект, и этот класс равен методу сравнивает поле путем рекурсивного вызова равных, рекурсивно invoke hashCode на поле. Если более сложное сравнение требуется, вычислить "каноническое представление" для этого поля и invoke hashCode на каноническом представлении. Если значение поле равно null, return 0 (или некоторая другая константа, но 0 - традиционная). ГЛАВА 3 МЕТОДЫ ОБЩИЕ ДЛЯ ВСЕХ ОБЪЕКТОВ
    • Если поле представляет собой массив, рассматривайте его так, как если бы каждый элемент был отдельным полем. То есть вычислить хэш-код для каждого значимого элемента, применяя эти правила рекурсивно и объединить эти значения на шаг 2.b. Если каждый элемент в поле массива является значительным, вы можете использовать один из Методы Arrays.hashCode добавлены в версию 1.5.
  • Объедините хэш-код c, вычисленный на шаге 2.1, в результат следующим образом: result = 31 * result + c;
• Результат возврата.
• Когда вы закончите писать метод hashCode, спросите себя, равные экземпляры имеют одинаковые хэш-коды. Напишите модульные тесты, чтобы проверить свою интуицию! Если равные экземпляры имеют неравные хэш-коды, выясните, почему и устраните проблему.

Ответ 2

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

• Если он используется в хэшированных структурах данных, например хэшмапах, вы хотите, чтобы он был максимально простым (быстрый для выполнения) и избегал конфликтов (большинство распространенных значений сопоставляются с разными значениями хэша). Хорошим примером является целочисленное хеширование с одним и тем же целым числом - это стандартная реализация hashCode() в java.lang.Integer

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

• Если вам нужны быстрые хеш-значения псевдо-случайных-ах (например, для симуляции), вы можете, как правило, модифицировать генератор псевдослучайных чисел для их создания. Мой личный фаворит:

public static final int hash(int a) {         
      a ^= (a << 13);
      a ^= (a >>> 17);        
      a ^= (a << 5);
      return a;   
}

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

public static <T> int hashCode(T[] data) {
    int result=0;
    for(int i=0; i<data.length; i++) {
        result^=data[i].hashCode();
        result=Integer.rotateRight(result, 1);
    }
    return result;
}

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

Ответ 3

Для целых чисел я обычно иду с k% p, где p = размер хеш-таблицы и является простым числом, а для строк я выбираю hashcode из класса String. Достаточно ли этого для интервью с крупной технологической компанией? - phoenix 2 дня назад

Может и нет. Это не редкость, чтобы обеспечить хэш-функцию хэш-таблице, реализация которой неизвестна вам. Кроме того, если вы используете хэширование, которое зависит от реализации с использованием простого числа ковшей, то производительность может ухудшиться, если реализация изменится из-за новой библиотеки, компилятора, порта ОС и т.д.

Лично я считаю, что важным в интервью является четкое понимание идеальных характеристик универсального хэш-алгоритма, который в основном заключается в том, что для любых двух клавиш ввода со значениями, варьирующимися всего на один бит, каждый бит на выходе имеет около 50/50 вероятность переключения. Я обнаружил, что вполне контр-интуитивно понятно, потому что многие функции хеширования, которые я впервые увидел, использовали бит-сдвиги и XOR, а переброшенный входной бит обычно перевернул один выходной бит (обычно в другом битовом положении, поэтому 1-вход-бит-влияет-многие -output-bits был немного откровенным моментом, когда я читал его в одной из книг Knuth. Благодаря этим знаниям вы, по крайней мере, способны тестировать и оценивать конкретные реализации независимо от того, как они реализованы.

Один из подходов, о котором я расскажу, потому что он достигает этого идеала и его легко запомнить, хотя использование памяти может сделать его медленнее, чем математические подходы (может быть и быстрее, в зависимости от аппаратного обеспечения) - просто использовать каждый байт на входе для поиска таблицы случайных чисел. Например, с учетом 24-битного значения RGB и int table[3][256], table[0][r] ^ table[1][g] ^ table[2][b] является отличным хэш-значением sizeof int - действительно "идеальным", если входы случайным образом разбросаны по значениям int (вместо того, чтобы увеличивать - см. Ниже). Этот подход не идеален для длинных или произвольных ключей, хотя вы можете начать пересмотр таблиц и битовую смещение значений и т.д.

Все, что сказано, иногда можно сделать лучше, чем этот рандомизированный подход для конкретных случаев, когда вам известны шаблоны во входных ключах и/или количество задействованных ведер (например, вы можете знать, что клавиши ввода смежны от 1 до 100 и 128 ковшей, поэтому вы можете передавать ключи без каких-либо столкновений). Если, однако, вход перестает соответствовать вашим ожиданиям, вы можете получить ужасные проблемы с столкновением, в то время как "рандомизированный" подход никогда не должен становиться намного хуже, чем предполагает загрузка (size()/buckets). Еще одно интересное понимание заключается в том, что, когда вам нужен быстрый и посредственный хеш, вам необязательно включать все входные данные при генерации хэша: например, в прошлый раз, когда я посмотрел на код хеширования строки Visual С++, он выбрал десять букв, равномерно расположенных вдоль текста для использования в качестве входных данных....