[решено] Хеш группы чисел - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - [решено] Хеш группы чисел (http://forum.oszone.net/showthread.php?t=260271)

Хеш группы чисел

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

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

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

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

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