Как я вычисляю хороший хэш-код для списка строк?

Единственное неудобство вашего первого варианта - (String1, String2) с тем же хэш-кодом (String2, String1) . Если это не проблема (например, потому что у вас есть порядок исправлений), все в порядке.

« Сложите всю строку вместе, а затем получите хэш-код » мне кажется более естественным и безопасным.

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

Если строки большие, вы можете предпочесть хешировать каждую, назначать хэш-коды и повторно хэшировать результат. Больше ЦП, меньше памяти.

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

Хэш-код равенство! = равенство значений

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

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

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, я думаю Код Джеффа был бы намного эффективнее.

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

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

Решение на основе SQL может быть основано на функциях контрольной суммы и checkum_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

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

Я не вижу причин не объединять строки и вычислять хэш-код для объединения.

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

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

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

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;
    }
}

Итак, я понимаю, у вас фактически есть некоторый набор строк, который вам нужно идентифицировать с помощью хэш-кода, и этот набор строк, который вам нужно идентифицировать среди никогда не менять?

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

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

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

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

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

  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 () было бы хорошо). Затем, чтобы сгенерировать хэш-код:

  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;
  }

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

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

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

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