LINUX.ORG.RU
решено Форум — Development  

Что-то вроде perfect hash

 


0

1

Нужен алгоритм создания хэша по заранее заданным значениям, с коллизиями по заданным значениям. На входе числа не более 255, на выходе не больше 2^32 (желательно 2^8 или хотя бы 2^16, но непринципиально).

Пример: 

вход       выход
1..4,25    9001
5,17,19    31337
8..12      100500
37         0

Естественно, входные диапазоны не пересекаются.

На ум пока приходит только построение КНФ, но может есть что-то с менее громоздким результатом?

UPD: Функция должна хорошо ложиться на C, хотелось бы обойтись без перечисления десятков «case x:» для диапазонов.

★★★★★

Последнее исправление: unC0Rr (всего исправлений: 1) 

switch(in) {
  case 0..4, 25: return 9001;
  case 5,17,19: return 31337;
  case 8..12,6: return 100500;
  case 37,42,7: return 0;
  case else: return 2^32;
}
anonymous
()
Ответ на: комментарий от anonymous

Это случайно не самая передовая техника, которая называется «Switch-технология»?

anonymous
()
Ответ на: комментарий от unC0Rr

функция на си

switch (in) {
case 0 ... 4:
case 25:
        return 9001;
case 5:
case 17:
case 19:
        return 31337;
case 8 ...12:
case 6:
        return 100500;
case 37:
case 42:
case 7:
        return 0;
default:
        return 1<<32;
}
gentoo_root ★★★★★
()
Ответ на: комментарий от gentoo_root

А ещё можно забить просто забить все ответы в массив (если вход от 0 до 255), тогда можно будет динамически менять функцию без пересборки программы.

gentoo_root ★★★★★
()
Ответ на: комментарий от gentoo_root

Да, начинаю склоняться к этому варианту. С другой стороны, если я просто перечислю все case, компилятор скорее всего сам построит эту таблицу, так что весь вопрос яйца выеденного не стоит.

unC0Rr ★★★★★
() автор топика
Ответ на: комментарий от unC0Rr

Это разве не C++

Нет.

какое-то нестандартное расширение языка C?

Это расширение gcc.

gentoo_root ★★★★★
()

А что мешает воспользоваться алгоритмом для построение perfect hash? Ну т.е я имею в виду подобрать перебором хеш функции которые не будут давать коллизий?

Если это интересно могу подробнее рассказать.

OxiD ★★★★
()
Ответ на: комментарий от OxiD

В общем случае я бы сделал табличку отображения диапазонов в некоторые числа, а для этих чисел построил совершенный хэш.

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

OxiD ★★★★
()
Ответ на: комментарий от OxiD

Если я отображу диапазоны в числа, хэш мне уже не нужен. Вообще задачу решил просто указывая все числа диапазона в case'ах.

unC0Rr ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development