Как рассчитать хороший хеш-код для списка строк?

Задний план:

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

Мы хотим иметь возможность быстро сопоставлять эти строки в запросе без повышения производительности при выполнении большого количества объединений.

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

Итак, как мне получить хороший hash-код? Я мог бы:

  • Xor hash-коды всей строки вместе
  • Xor с умножением результата после каждой строки (скажем, на 31)
  • Поместите всю строку вместе, затем получите hash-код
  • Другой способ

Так что думают люди?


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

(Если вам интересно, мы используем .NET и SqlServer)


Ошибка !, Ошибка!

Цитата из правил и правил для GetHashCode Эрика Липперта

Документация для System.String.GetHashCode отмечает, что две идентичные строки могут иметь разные хеш-коды в разных версиях CLR, и на самом деле они это делают. Не храните строковые hashи в базах данных и ожидайте, что они будут неизменными навсегда, потому что их не будет.

Поэтому String.GetHashcode () не должен использоваться для этого.

Стандартная практика Java – это просто написать

final int prime = 31; int result = 1; for( String s : strings ) { result = result * prime + s.hashCode(); } // result is the hashcode. 

Я не вижу причин не конкатенировать строки и вычислить hash-код для конкатенации.

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

Ваш первый вариант имеет единственное неудобство (String1, String2) создающее тот же hash-код (String2, String1) . Если это не проблема (например, потому что у вас есть заказ на исправление), это нормально.

« Кошка вся строка вместе, а затем получить hash-код » кажется более естественной и безопасной для меня.

Обновление . Как отмечается в комментарии, у этого есть недостаток, что список («x», «yz») и («xy», «z») даст тот же хеш. Чтобы этого избежать, вы можете присоединиться к строкам с разделителем строк, который не может появляться внутри строк.

Если строки велики, вы можете предпочесть hash каждый, cat hash-коды и перефразировать результат. Больше CPU, меньше памяти.

Другой способ, который появляется в моей голове, цепочка xors с повернутыми hashами на основе индекса:

 int shift = 0; int result = 1; for(String s : strings) { result ^= (s.hashCode() << shift) | (s.hashCode() >> (32-shift)) & (1 << shift - 1); shift = (shift+1)%32; } 

edit: прочитав объяснение, данное в эффективной java, я думаю, что код Geoff будет намного более эффективным.

Решение на основе SQL может основываться на функциях контрольной суммы и checksum_agg. Если я следую за ним правильно, у вас есть что-то вроде:

 MyTable MyTableId HashCode MyChildTable MyTableId (foreign key into MyTable) String 

с различными строками для данного элемента (MyTableId), хранящегося в MyChildTable. Чтобы вычислить и сохранить контрольную сумму, отражающую эти строки (никогда не изменившиеся), должно работать следующее:

 UPDATE MyTable set HashCode = checksum_agg(checksum(string)) from MyTable mt inner join MyChildTable ct on ct.MyTableId = mt.MyTableId where mt.MyTableId = @OnlyForThisOne 

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

Я надеюсь, что это не нужно, но так как вы не упоминаете ничего похожего на то, что используете только hash-коды для первой проверки, а затем проверяете, что строки на самом деле равны, я чувствую необходимость предупредить вас:

Hashcode равенство = равенство равенства

Будут множество наборов строк, которые дают одинаковый hash-код, но не всегда будут равными.

Поэтому я понимаю, что у вас фактически есть набор строк, которые нужно идентифицировать по hash-коду, и что набор строк, которые вам нужно идентифицировать, никогда не изменится?

Если это так, это не имеет особого значения, если используемая вами схема дает уникальные номера для разных строк / комбинаций строк. Я бы начал с просто конкатенирования строк и вычисления String.hashCode () и просмотра, если вы закончите с уникальными номерами. Если вы этого не сделаете, вы можете попробовать:

  • вместо конкатенации строк, объединить хеш-коды строк компонентов и попробовать разные множители (например, если вы хотите идентифицировать сочетания двухстрочных последовательностей, попробуйте HC1 + 17 * HC2, если это не дает уникальных чисел, попробуйте HC1 + 31 * HC2, затем попробуйте 19, затем попробуйте 37 и т. Д. – в сущности, любое небольшое количество нечетных чисел будет хорошо).
  • если вы не получите уникальные номера таким образом – или если вам нужно справиться с множеством возможностей расширения, тогда рассмотрите более сильный хеш-код. 64-битный hash-код является хорошим компромиссом между легкостью сравнения и вероятностью уникальности хешей.

Возможная схема для 64-битного хеш-кода следующая:

  • сгенерируйте массив из 256 64-битных случайных чисел с использованием довольно сильной схемы (вы можете использовать SecureRandom, хотя схема XORShift будет работать нормально)
  • выберите «m», другое «случайное» 64-битное нечетное число с более или менее половиной его битов
  • для генерации хеш-кода, пройти каждое значение байта, b, составить строку и взять b-й номер из вашего массива случайных чисел; затем XOR или добавьте его с текущим значением hashа, умноженным на «m»,

Таким образом, реализация, основанная на значениях, предлагаемых в Numerical Recipes, будет:

  private static final long[] byteTable; private static final long HSTART = 0xBB40E64DA205B064L; private static final long HMULT = 7664345821815920749L; static { byteTable = new long[256]; long h = 0x544B2FBACAAF1684L; for (int i = 0; i < 256; i++) { for (int j = 0; j < 31; j++) { h = (h >>> 7) ^ h; h = (h << 11) ^ h; h = (h >>> 10) ^ h; } byteTable[i] = h; } } 

Вышеупомянутое инициализирует наш массив случайных чисел. Мы используем генератор XORShift, но мы могли бы использовать любой довольно качественный генератор случайных чисел (создавая SecureRandom () с определенным семенем, тогда вызов nextLong () будет прекрасен). Затем, чтобы создать hash-код:

  public static long hashCode(String cs) { if (cs == null) return 1L; long h = HSTART; final long hmult = HMULT; final long[] ht = byteTable; for (int i = cs.length()-1; i >= 0; i--) { char ch = cs.charAt(i); h = (h * hmult) ^ ht[ch & 0xff]; h = (h * hmult) ^ ht[(ch >>> 8) & 0xff]; } return h; } 

Руководство для рассмотрения состоит в том, что, учитывая hash-код из n бит, вы обычно должны генерировать hashи в порядке 2 ^ (n / 2) строк, прежде чем вы получите столкновение. Или по-другому, с 64-битным хешем, вы ожидаете столкновения после примерно 4 миллиардов строк (так что если вы имеете дело до, скажем, нескольких миллионов строк, шансы на столкновение довольно незначительны ).

Другим вариантом будет MD5, который является очень сильным хешем (практически безопасным), но это 128-битный хеш, поэтому у вас есть небольшой недостаток иметь дело с 128-битными значениями. Я бы сказал, что MD5 является излишним для этих целей – как я уже сказал, с 64-битным hashем вы можете справиться достаточно безопасно с порядком нескольких миллионов строк.

(Извините, я должен уточнить – MD5 был разработан как безопасный хеш, просто потому, что он не был безопасным. «Безопасный» хеш – это тот, где данный конкретный хеш нецелесообразно преднамеренно строить ввод, который привел бы к этот hash. В некоторых случаях – но не так, как я понимаю в вашем – вам понадобится это свойство. С другой стороны, вам может понадобиться, если строки, которые вы используете с пользовательскими входными данными, т.е. злоумышленник может преднамеренно попытаться сбить с толку вашу систему. Вы также можете быть проиндексированы в следующем, что я написал в прошлом:

  • руководство по hash-кодам
  • безопасные хеш-коды в Java (включая некоторые измерения производительности)

Использование GetHashCode() не идеально подходит для объединения нескольких значений. Проблема в том, что для строк хеш-код является просто контрольной суммой. Это оставляет мало энтропии для подобных значений. например, добавление hash-кодов для («abc», «bbc») будет таким же, как («abd», «abc»), вызывая столкновение.

В тех случаях, когда вам нужно быть абсолютно уверенным, вы должны использовать настоящий алгоритм хеширования, такой как SHA1, MD5 и т. Д. Единственная проблема заключается в том, что они являются блочными функциями, которые трудно сравнивать hashи для равенства. Вместо этого попробуйте hash CRC или FNV1 . FNV1 32-бит супер просто:

 public static class Fnv1 { public const uint OffsetBasis32 = 2166136261; public const uint FnvPrime32 = 16777619; public static int ComputeHash32(byte[] buffer) { uint hash = OffsetBasis32; foreach (byte b in buffer) { hash *= FnvPrime32; hash ^= b; } return (int)hash; } } 

Вы можете использовать следующий метод для агрегирования hash-кодов: http://docs.oracle.com/javase/7/docs/api/java/util/Objects.html#hash (java.lang.Object …)

Давайте решим вашу проблему с корнем.

Не используйте hash-код. Просто добавьте целочисленный первичный ключ для каждой строки

Давайте будем гением компьютера.