Разное - [решено] Хеш группы чисел

[crashtuak]

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

[Iska]

crashtuak, язык какой?

[Iska]

crashtuak, массив чисел от строки отличается носителем буквы. Допусти это массив 32-разрядных знаковых целых. Тогда можно применить любой алгоритм хеширования, какой придёт в голову. Например:



Код:

Код: Выделить всё

typedef unsigned long array_hash;
array_hash make_hash(const long *first, const long *last) {
  array_hash hash = 0;
  for(; first<last; ++first) {hash=(array_hash)(hash*91284645 + *first);}
 /*число вбил от балды, желательно нечётное*/
  return hash;
}

если процессор 32-разрядный, то использовать array_hash = unsigned long, Если 64-, то array_hash = unsigned long long



Качество хеша - так себе, но есть большая вероятность, что будут отбиваться последовательности с одинаковым началом, что поможет при последующем линейном поиске. Массивы хранить уже сортированными.

[crashtuak]

pva, спасибо, пробил на имеющихся данных - работает хорошо, повторений не было.