хеш-функция для строк юникода

Так сделано в SBCL 1.4.2:

(defun %sxhash-substring (string &optional (count (length string)))
  (declare (optimize (speed 3) (safety 0)))
  (declare (type string string))
  (declare (type index count))
  (macrolet ((set-result (form)
               `(setf result (ldb (byte #.sb!vm:n-word-bits 0) ,form))))
    (let ((result 0))
      (declare (type (unsigned-byte #.sb!vm:n-word-bits) result))
      (unless (typep string '(vector nil))
        (dotimes (i count)
          (declare (type index i))
          (set-result (+ result (char-code (aref string i))))
          (set-result (+ result (ash result 10)))
          (set-result (logxor result (ash result -6)))))
      (set-result (+ result (ash result 3)))
      (set-result (logxor result (ash result -11)))
      (set-result (logxor result (ash result 15)))
      (logand result most-positive-fixnum))))
;;; test:
;;;   (let ((ht (make-hash-table :test 'equal)))
;;;     (do-all-symbols (symbol)
;;;       (let* ((string (symbol-name symbol))
;;;           (hash (%sxhash-substring string)))
;;;      (if (gethash hash ht)
;;;          (unless (string= (gethash hash ht) string)
;;;            (format t "collision: ~S ~S~%" string (gethash hash ht)))
;;;          (setf (gethash hash ht) string))))
;;;     (format t "final count=~W~%" (hash-table-count ht)))

Но в Активном Обероне нет LOGXOR.

Работай на байтовом уровне. Зачем тебе знать юникод это или win1251.

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

Вот ещё:

https://stackoverflow.com/questions/3721422/looking-for-a-good-64-bit-hash-for-file-paths-in-utf16

Один из ответов:

ui64 res = 10000019;
for(i = 0; i < len; i += 2)
{
  ui64 merge = ucase(path[i]) * 65536 + ucase(path[i + 1]);
  res = res * 8191 + merge; // unchecked arithmetic
}
return res;

(там нужна была ещё нечувствительность к регистру)

Вот ещё статейка, но она не про юникод:

https://sohabr.net/habr/post/219139/

привожу просто для полноты коллекции.

Так как свойства не заданы, то бери первую букву как хеш.

Никакой разницы не будет. XXH32_update работает с 32 битными значениями, XXH64_update с 64 битными, а XXH3_64/128bits_update с 64/128 битами. Так что чтобы туда не отправил, оно все равно будет оперировать 4-16 байтами.

А какая разница? Те же самые алгоритмы и реализованные функции и используй.

Если юникодом ты называешь UTF-8, то сначала нормализуй, а затем делай хэш для получившихся байт.

Например затем что 2 визуально одинаковые строки юникода могут иметь разный хэш, взависимости от того, нормализованы они или нет, и каким из способов.

Ну, это если мы про UTF-8.

2 визуально одинаковые строки

all
a11

И никакого юникода

Так как свойства не заданы, то бери первую букву как хеш.

Первая буква может быть разной длины.

Первая буква может быть разной длины.

Как короткая I и длиная Щ? Не путай буквы, знакоместо, лигатуры(связка букв) и тд

Нет, это массив 32-разрядных чисел, в основном ASCII и кириллица.

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

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

О, спасибо за эти слова.

Развивая эту тему.

Дарю идею - хеш за константное время (не зависящее от длины строки): берем «случайную» букву или несколько «случайных» букв из строки. Надо всего лишь написать детерминированную функцию, берущую «случайную» букву.

Не, ты не понял. Юникод это просто метод расшифровки байтового потока и хоть ты в лоб расшибись в байт больше 255 не засунешь и нормализовать там нечего, понятное дело что в потоке байт юникода всегда в начале имеются одинаковые последовательности 0x 0xx 0xxx0 xxxx но они от символа к символу часто разные я сомневаюсь что они на хеши сильно то влияют эти одинаковости. Если у тебя юникод типа Ъ в виде 16/32 битных чисел типа жирно, но надёжно. То char * dst = (char*)src и суёшь dst хеш функции и всё. Ей насрать что у тебя там в какой кодировке и какие там последовательности, поток чисел прыгающих от 0 до 255 и всё. Суть то получить от «строки» чиселко и всё. А что там за данные в этой строке глубоко пох =)

Я djb у себя использую,работает быстро,а колизии меня тож не особо парят, словарь делаю побольше и всё.

А число кстати хочу 64 разрядное

Аналогично любой тип данных кастуешь к 64 и скармливаешь. Правда тебе придётся в этом случае проверять длинна то кратная этим 64 и добавлять если что байтики. а то сигфолт или белиберда рандомная будет, ну или кастовать к char, брать кусок из 8 байт и кормить функции, а когда последних байт будет меньше чем 8 добавлять, но… короче накладные расходы от этого не превысят ли расходы на несколько циклов при касте любых данных к char и использования тупа тех функций что ты по ссылке привёл?

Да, у меня Ъ юникод и я не хочу делать такое приведение типа. Хотя понятно, что можно. И результаты будут разные. В utf8 там будут во всех байтах не нули, а после насильного преобразования к char* там в байтах будет от половины до 3/4 нулей. В такой ситуации утверждение о том, что разницы в качестве хеширования нет, выглядит довольно смелым. Кроме того, результат ещё может зависить от endianness, а хотелось бы машинно-независимую формулу. Ну я на самом-то деле уже какую-то формулу от фонаря наваял - на самом деле главное, чтобы вообще работало :) Так что данная тема пусть будет чисто ради общего развития.

результат ещё может зависить от endianness, а хотелось бы машинно-независимую формулу.

UTF8 наиболее машинонезависмое представление уникода.

Тред не читал, но тут наверняка тебе уже сказали про самые быстрые в мире хеш функции, которые какраз жрут 64 бита, но внутрях делают всё по своему их там надрочили да нахакали дай боже. Просто бери и используй =)

а хотелось бы машинно-независимую формулу.

Ну тут я не знаю. На этом моя квалификация всё, окончена =)

Выплюньте эту старую дребедень. Есть же xxhash, t1ha и wyhash.

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

У тебя шрифт настолько говной воняет, или тяжёлые проблемы со зрением?

Тогда пофиг, можно толкать как есть.

У тебя шрифт настолько…

Ровно настолько, насколько твой байт.

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

Ну я это и пытался, впрочем, уже забил. Однако насчёт криптографии не соглашусь, потому что яйцеголовые дядьки работают на кого надо, и этот миф про криптографию придуман специально, чтобы не было проблем с прослушиванием населения. Пруф: алгоритмы шифрования, которые применяют в АНБ, засекречены (дисклеймер: это сведения из русской википедии), и некоторые американские шифровальные машины засекречены (это из какой-то статьи).

алгоритмы шифрования, которые применяют в АНБ, засекречены

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

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

Думается, что там кормушка везде. Ведь согласись, что heartbleed или пароль для груба из 28 бекспейсов никак не относятся к алгоритмам шифрования или к ГСЧ, а кормушку предоставляют. А почему кормушка работает? Потому что все пользуются openssl и грубом, реализовав в обобщённом виде рекомендацию «не пилите своё, доверьтесь нам», относительно которой рекомендация «не пилите свои алгоритмы шифрования, доверьтесь умным дядям» является лишь частным случаем. Впрочем, это уже не по теме.

Охуеть, все те же сетевые шизофренники

Диванный аналитик такой диванный.

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

эмм — а прочитать байты массива чисел нельзя?

Я выше написал, почему мне эта идея не нравится.

У меня не C++

Делом займись

а ок... не ну дело конечно твое...

а просто посмотреть как там у других?

Это можно. Когда в следующий раз буду страдать от этого, посмотрю, спасибо (уже ведь в лиспе посмотрел, у меня он под рукой, а плюсов настроенных под рукой нет).

Если б я этим делом не занялся два года назад, может смог бы и мимо пройти.

Делириум, будьте сегодня аккуратны … Я не хочу, чтобы вас избили десантники за то, что вы не такой как все …

Владимир

Посмотри в исходники Java. Не думаю, что в мире есть что-то лучше.