8-битный хэш для строки

Возьми первый символ от md5(строка) или sha1 или crc32 etc

в 8 бит не упаковать хеш. сплошные коллизии будут.

Может просто сумму всех символов использовать? Прогони на всех строках и проверь, есть ли коллизии.

Если строки заранее известны, почему бы им просто идентификаторы не приделать от 1 до 255?

Раз строки знаешь то просто поиграйся с xor, сдвигами/вращениями и сложением. Весьма вероятно тупой xor для 40 строк уже не даст коллизий.

в 8 бит и 2 символа без коллизии не упаковать

H(S) = S[0] + S[1]*31 + ... + S[N]*31^N

> строки заранее известны, их примерно 40

Пронумеруй их. // К.О.

вероятность отсутствия коллизий при ксоре в указанных условиях задачи 256 / 40 * 40 = 0.16

Могу предложить ТС использовать префиксное дерево, в котором в листах будут храниться значения «хеша». Так как, опять-таки по условию задачи, строк не более 256, для каждой можно назначить уникальный код..

обойтись бы без коллизий

Ага :)

crc8, поиграйся с полиномом...

в 8 бит не упаковать хеш. сплошные коллизии будут.

Почему это? Для 40 вариантов вроде и 6 бит хватило бы, только найти бы быструю функцию.

Если строки заранее известны, почему бы им просто идентификаторы не приделать от 1 до 255?

Потому что на входе строка, а не инденитификатор. «Приделывание» - это и есть искомая функция.

ксоре

Долго думал, что за приложение KDE )

префиксное дерево

Наверно, накладно по памяти, но вообще интересно, попробую.

Называется - «идеальное хеширование»

есть программы perfhex, gperf - как раз для генерации функций идеального хеша. Попробуй поизменять параметры генерации функции, может получится(а может и нет).

Специальные программы есть для этого. gperf к примеру

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

Ну вот я сейчас ради эксперимента взял 40 названий цветов и что то к больше чем 11 и из них мне хеш функцию без коллизии не подобрать руками. Причем тупой xor валится уже на 2.

var strs = ['Air Force blue','Alice blue','Alizarin','Almond','Amaranth','Amber','Amber','American rose','Amethyst','Anti-flash white','Antique brass','Antique fuchsia','Antique white','Ao','Apple','Apricot','Aqua','Aquamarine','Army green','Arsenic','Arylide yellow','Ash grey','Asparagus','Atomic tangerine','Auburn','Aureolin','AuroMetalSaurus','Baby blue','Baby blue eyes','Baby pink','Ball Blue','Banana Mania','Banana yellow','Battleship grey','Bazaar','Beau blue','Beaver','Beige','Bisque','Bistre','Bittersweet'];

var _hash = function(s)
{
  var a = 0, i = s.length; while(i--) { a += s.charCodeAt(i); a = (a << 3) | (a >>> 5); }
  return a & 255;
  //return (s.charCodeAt(0) + s.charCodeAt(s.length/2 - 1) + s.charCodeAt(s.length - 1)) & 255;
};

var _test = function()
{
  var map = {};
  var i = strs.length; while(i--)
  {
    var hash = _hash(strs[i]);
    if(hash in map) 
      return console.log('fail', i, hash);
    else
      map[hash] = 1;
  }
  
  console.log('ok');
};

_test();

Может конечно строки взял неудачные или сильно близкие.

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

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

зачем тогда хэш нужен, если тогда достаточно строки хранить в дереве? а тут ведь именно хэш почему-то нужен

зачем хэш? зачем дерево?

нужно отобразить конечное мн-во строк на конечное мн-во чисел.

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

алсо. автор, двоичный поиск тормозит изза кэш-промахов

для массива 0 1 2 3 4 5 6 7 8 9 лучше будет его переупорядочить, чтоб элементы, которые будут сравнены первее, шли впереди. лучше 1 клок ждать данных, чем сотню.

если хеш надо будет гонять часто учти этот момент.

0 1 2 3 4 5 6 7 8 9 -> 4 1 7 0 5 2 8 3 6 9

Конечное множество чисел нужно не само по себе, а для поиска ассоциированной со строкой информации. В случае сбалансированного дерева понадобится для 40 строк несколько сравнений строк. Вряд ли какая-то хэш-функция от строки будет работать намного быстрее, чем несколько сравнений строк.

языка не знаю, но такое

a = (a << 3) | (a >>> 5);

в сочетании с

return a & 255;

подсказывает мне, что a не восьмибитное, и в результате вычислений скорее всего получится число большее, чем 247

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

кстати. лютое бешеное спасибо ТС за то, что благодаря ему я теперь знаю как сделать парсер без деревьев на голом obstack.

Действительно, для случая статичного набора 40 строк достаточно загнать всё в отстортированный массив и далее работать двоичным поиском.

Пока у меня 25 строк; сумма символов дала 2 коллизии, crc8 - 3.
gperf пока под рукой нет. Вообще, это хороший вариант, потому что при добавлении новых слов make будет достаточно. Но идеальной функции он может и не дать, как я понимаю, поэтому ненадежно.
Так что поэкспериментирую еще с деревом и с бинарным поиском. Не то, что хотелось, но хотя бы динамичнее получится. Вопрос лишь, насколько это быстро.

Убери повторяющееся «Amber» и сделай s/Bisque/Bisque1/, ибо оно и 'Bistre' не очень дружат.
После этого можешь воспользоваться:

var _hash = function(s) {
    var a = 0, i = s.length;
    while (i--) {
        a += (s.charCodeAt(i) + i * i * 0.01)
    }
    return a & 255;
};

По-моему, если массив не отсортирован - это уже не двоичный поиск.

Прям волшебство :)

Спасибо за трюк. Просто ищем n в формуле a += s.charCodeAt(i) + i * i * n. Конкретно для этих слов n = [2, 10, 14, ...] :)

Проблема 'bistre' и 'bisque' заключается в том, что длины у них одинаковые и единственные символы, которые отличаются, 't' + 'r' == 's' + 'q', то есть по «весу» равны, а порядок их не учитывается. Но это можно исправить, умножая charcode на некоторую функцию f(i), которая вполне подбирается:

        var _hash = function(s) {
            var a = 0, i = s.length;
            while (i--) {
                a += s.charCodeAt(i) * (i + 44) + (i + 22)
            }
            return a & 255;
        };

> 8-битный хэш для строки

Чем плох 32-х битный виртуальный адрес первого символа строки(как 32-х битныйй хеш)? Если строки не пересекаются, самое дубовое и быстрое решение.
ЕМНИП, как-то так реализовано хеширование для строк в Qt.

тут даже покороче есть :) a += s.charCodeAt(i) * (i + 35); но суть мне ясна

Он отсортирован в том порядке, в котором может производиться сравнение. И таким образом минимизирует количество кэш-промахов.

Вообще выступление ckotinko доставило безмерно.

Плусую. Как раз тут бенчмарк пишу ибо этом меня вдохновило :)

Напиши на Perl или Python скрипт, который будет принимать список слов и выдавать C-шную функцию (пример для строк «api», «abi» и «foo»):

int keyword_to_integer(const char* p)
{
  switch (*p++) {
  case 'a' :
    switch (*p++) {
      case 'b' :
        switch (*p++) {
          case 'i' :
            return 1;
        }
        break;
      case 'p' :
        switch (*p++) {
          case 'i' :
            return 2;
        }
        break;
    }
    break;
  case 'f' :
    switch (*p++) {
      case 'o' :
        switch (*p++) {
          case 'o' :
            return 3;
        }
        break;
    }
    break;
  }

  return -1;
}

> алсо. автор, двоичный поиск тормозит изза кэш-промахов

Только идиоты будут оптимизировать двоичный поиск, особенно для 40 элементов, особенно, не зная полной задачи.

Хорошо пошутил, мне понравилось.

Что-то «перевыдумываете» вы. В такой ситуации можно конечно искать hash-функцию (и gperf наверное даже её найдет). Но прямой двоичный поиск будет ничуть не хуже, т.е. получить не hash, а просто номер ключа.

Причем можно заюзать gperf --switch=256 и получить тоже самое. Если нужно (хочется) супер-быстро, то просто начинать сравнение с длины, а дальше по по 4 байта...

как считал?

Во, можно еще вот так вые$%^$%ся:

while (head_ != end_) {
        /*!re2c
                "keyword1" {return 1;}
                "keyword2" {return 2;}
                "keyword3" {return 3;}
                "keyword4" {return 4;}
                "keyword5" {return 5;}
        */
}

re2c сам все сделает ;-)

>Как подобрать функцию?

ColorForth для подобных целей использует коды Шеннона-Фано. Хотя странно, вообще-то коды Хаффмана или арифметическое кодирование будут поэффективнее.

Вероятнострую модель сам подберешь.

В идеале, обойтись бы без коллизий.

Не бывает. По определению.

Хорошо пошутил, мне понравилось.

А что не так? Все строки известны заранее, хранятся в файле keywords.txt. Во время сборки (ну, или когда обновился keywords.txt) делаешь:

cat keywords.txt | ./tools/magic.py > keywords.c

Я не понимаю вопроса ТС?

Как-то так. На твоих известных строках коллизий не будет.

int hash(const char * str) {
  if (!strcmp(str, "stroka1")) {
     return 1;
  } else if (!strcmp(str, "stroka2")) {
     return 2;
  } ....
  } else if (!strcmp(str, "stroka40")) {
     return 40;
  } else {
     return crc32(str) % 256;
  }
}

>> В идеале, обойтись бы без коллизий.

Не бывает. По определению.

По какому такому определению? У ТС ключей меньше, чем допустимая мощность множества значений хеша.