LINUX.ORG.RU

Так сделано в 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.

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 1 )
Ответ на: комментарий от ox55ff

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

den73 ★★★★★ ()

Вот ещё:

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;

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

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 1 )
Ответ на: комментарий от den73

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

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

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

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

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

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

anonymous ()
Ответ на: комментарий от LINUX-ORG-RU

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

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

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

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

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

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

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

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

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

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

LINUX-ORG-RU ★★★★★ ()
Ответ на: комментарий от LINUX-ORG-RU

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

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 4 )
Ответ на: комментарий от den73

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

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

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

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

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

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

LINUX-ORG-RU ★★★★★ ()

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

anonymous ()
Ответ на: комментарий от LINUX-ORG-RU

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

den73 ★★★★★ ()
Ответ на: комментарий от anonymous-angler

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

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

anonymous ()

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

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

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

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

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

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

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

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

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

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 3 )

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

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

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

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

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

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

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 1 )
Ответ на: комментарий от den73

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

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

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

Владимир

anonymous ()

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

Legioner ★★★★★ ()
Для того чтобы оставить комментарий войдите или зарегистрируйтесь.