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

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

12 голосов
/ 21 мая 2011


В интервью я сталкивался с ситуациями, когда мне нужно было использовать хеш-функцию для целых чисел или для строк.В таких ситуациях какие из них мы должны выбрать?Я был неправ в этих ситуациях, потому что в итоге я выбрал те, которые вызывают много коллизий, но затем хэш-функции имеют тенденцию быть математическими, и вы не можете вспомнить их в интервью.Существуют ли какие-либо общие рекомендации, по крайней мере, интервьюер удовлетворен вашим подходом к целым числам или строковым значениям?Какие функции были бы адекватны для обоих входов в «ситуации интервью»

Ответы [ 3 ]

8 голосов
/ 21 мая 2011

Вот простой рецепт из Эффективной Java-страницы 33 :

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

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

  • Если она используется в хешированные структуры данных , подобные хеш-картам, вы хотите, чтобы он был максимально простым (быстрым для выполнения) и избегал коллизий (наиболее распространенные значения отображаются в разные хеш-значения).Хороший пример - целочисленное хеширование того же целого числа - это стандартная реализация 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;
}

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

2 голосов
/ 24 мая 2011

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

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

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

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

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

...