хеш-функция

Чем тот же md5 не устраивает?

В самом общем случае такой функции не существует. Строка фиксированной длины являтся отличным хешем себя самой среди других строк этой же длины :)

мне не криптографическую... мне для поиска... надо чтоб ультрабыстрая...

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

Вот тут весьма интересная функция описана.

нашел сообщение на gamedev.ru об одной функции — она используется для rtti в stl.

тип строк сменил на wchar_t.

написал тестер с последовательным перебором. он выдает все подряд хеши в файл. имя файла — количество символов в строке.

потом собственно проверка: sort -u %d.res | wc -l сверяется с cat %d.res | wc -l

о результатах, если интересно, доложу.

ien, насчёт «супербыстро» - в ряде случаев для строк, например при хэшировании словарей естественных языков, есть решение которое даёт возможность осуществлять добавление/удаление/доступ со сложностью везде O(1).

Вот набросок (особо не тестировал), можете приспособить его к вашей задаче.

;;; REQUIRES: if-it anaphoric macro, memoizations from PAIP.

(defvar *base*          10)
(defvar *min-char-code* 65)
(defvar *max-char-code* 75)
(defvar *max-word-size* 5)

(defvar *max-hash-array-size*
        (/ (- (* (- *max-char-code* *min-char-code*)
                 (expt *base*
                       (1+ *max-word-size*)))
              (- *max-char-code* *min-char-code*))
           (1- *base*)))

(defvar *word-hash-array*
        (make-array *max-hash-array-size* :initial-element nil
                                          :element-type '(or string nil)
                                          :adjustable t))

(defun word-to-hash (string &key (base *base*) (min-char-code *min-char-code*))
  (let ((hash 0)
        (index 0))
    (dolist (char (coerce string 'list))
      (incf hash (* (expt base index) (- (char-code char) min-char-code)))
      (incf index 1))
    hash))

(memoize 'word-to-hash)

(defun set-word-to-hash-array (word)
  (setf (aref *word-hash-array* (word-to-hash word)) word))

(defun get-word-from-hash-array (word)
  (if-it (aref *word-hash-array* (word-to-hash word))
         it
         'not-hased))

(defun delete-word-from-hash-array (word)
  (setf (aref *word-hash-array* (word-to-hash word)) nil))

З.Ы. что это за ужасные пробелы при форматировании кода ?0_щ?

Да, как и все подобные хеши - прожорлив очень (память под массив), этим приходится платить за скорость.

adler32

> она используется для rtti в stl.

Вроде в текущей реализации по адресу vtbl определение происходит, не?

> Знает ли кто-нибудь такую быструю хеш-функцию, чтобы коллизии были только для разных по размеру строк?

Такой не может существовать в принципе.

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

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

если надо разные хеши для всех строк одной длины, то таким хешем может быть только сама строка.
невозможно каждому числу от 1 до 1000000 дать уникальные номера от 1 до 100.

Собственно что я откопал:

1) http://pastebin.org/315303

2) http://pastebin.org/315307

Первую начал проверять — хеш достаточно хорош. Второе не проверял, но создатель говорит, что это отменная вещь.

adler32 — занятный алгоритм...

Что касается длины строки... То, как известно, все зависит от алфавита. Длина строки может быть 30, но если там используются символы только 'a' и 'b', то больше 2^30 вариантов не получится. А такие строки можно перенумеровать уникальным 32-битным целым.

Для себя проблему решил. Всем спасибо.

CRC32

> чтобы коллизии были только для разных по размеру строк

Для конечных алфавитов, из которых составляются строки и хеш, такое невозможно.