Способы разрешения коллизий

В продолжение темы о хэшмапах, как структура данных таковые полагаются полностью на хэшфункцию - что логично. Но поскольку коллизии в общем случае неизбежны (исключения - идеальные хэш- и identity-функции), то их разрешать как-то всё равно да и приходится. И основополагающих принципа существует всего два:

1) Закрытая адресация (она же separate chaining) - способ был впервые описан во внутреннем меморандуме в IBM в 1953 году. Это как раз классическая схема, которая была использована и в старой гошной мапе. Базовый случай - хэшфункцией мы адресуем связной список из вхождений (вхождение есть пара ключ-значение), где уже линейно искомое значение и ищем. Гошная мапа просто немного уменьшила футпринт за счёт связного списка бакетов, где бакет держит сразу до 8 вхождений, и сравнения по верхушке хэша, что даёт хороший бонус для значений, у которых операция сравнения является довольно дорогой (те же строки).

2) Открытая адресация - появилась чуть позже, пускай и с разницей всего в пару лет (что неудивительно - основой послужил как раз-таки тот самый меморандум с закрытой адресацией). В ней больше не используется концепция двухмерного массива, и заместо все значения лежат в одном большом массиве (где вхождения называют слотами). Само разрешение коллизий тогда работает достаточно просто - всё так же адресуем слот в массиве по хэшу, и если он нам не подходит (для вставки - уже оккупирован, для лукапа - не совпадает ключ), тогда мы просто идём дальше и смотрим следующий слот. Правда, как именно мы выбираем следующий слот - тоже тема для отдельного разговора: есть linear probing, когда мы сдвигаем индекс слота на константу (обычно 1), есть quadratic probing, когда мы, соответственно, сдвигаем индекс уже на результат какого-нибудь квадратического уравнения. Есть совсем уж страшное double hashing, когда сдвиг разрешается второй хэш-функцией. Суть методов quadratic probing и double hashing заключается исключительно в том, чтобы снизить так званую кластеризацию - неравномерное распределение элементов, когда они скапливаются на каком-то одном промежутке (double hashing даёт наилучший результат, но по производительности самый худший, а вот quadratic probing есть золотая середина с достаточно тонко подобранными значениями). Плоха кластеризация тем, что без перебора слотов в общем случае не обойтись, а это линейная сложность - всё-таки хотелсь бы амортизированную константу, пускай качество самой хэш-функции и отыгрывает здесь гораздо большую роль - но мир, увы, не идеален.


Конечно, помимо вышеперечисленных двух способов, существуют и другие разновидности (Coalesced hashing, Cuckoo hashing, Hopscotch hashing, Robin Hood hashing), но все они, так или иначе, основываются на открытой адресации.


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

Swissmap, на которую сейчас в го переходят, кстати, тоже есть таблицей на открытой адресации. Только они добавили ещё так званую метадату - отдельный (на самом деле, не очень) массив чаров, что и обращения к памяти более локализирует (более кэш-френдли => гуд), и по которой sse инструкциями гулять можно. В общем - быстро и красиво. Но сложна.

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

Это решается счётчиком просмотренных слотов. Но этот способ интересен тем, что ограничение количества попыток нахождения слота также является один из способов борьбы с кластеризацией. Если я правильно понял, то если вставка валится из-за того, что свободный слот не был найден в промежутке i..i+n (где n - максимальное количество тех самых попыток, или же просмотра слотов), то мапа инициирует ресайз.

ПыСы забыл добавить линк на описание способов открытой адресации, только более формальным языком: https://math.gsu.by/wp-content/uploads/courses/structure/L8.6.4.html

Tariff: A Python package that imposes tariffs on Python imports
Article, Comments

https://jasonfantl.com/posts/What-is-Entropy/

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

https://litter.catbox.moe/a8z45n.7z

А вот и сам слив фочана

Here’s the leak btw

The entire source code: https://files.catbox.moe/d56ws8.7z
Full list of all jannies/mods/admins (in username:email:role format): https://files.catbox.moe/vqkxwf.txt
Dump of the jannies private IRC channel that they all use to communicate on: https://files.catbox.moe/93d0r8.rar
Dump of the entire /j/ board (a board private only to board jannies): https://files.catbox.moe/czivhs.7z

Жуть, жуть

во-вторых этот код валиден

Все знают про фатальный недостаток - мем, касающийся Поттеринга, и отсылающийся к переписыванию уже работающего, при этом производя bloatware (какого хуя системд имеет отношение к буту?).

А что насчёт NIH - not invented here, как синдром, возникающий при выборе чего-либо? Если это что-то изобретено не здесь - мы это не берём.

И как диаметральная противоположность - NIT, not invented there. Каюсь, и сам слегка подвержен.

Никаких выводов. Никакой морали. Минутка просвящения.

Rejection Sampling and Uniform Distribution

Одна из характеристик хорошей rand-функции — равномерное распределение. Это означает, что каждое возможное значение имеет одинаковую вероятность быть выбрано

Представим, что у вас есть функция rand7(), которая равномерно возвращает случайное число в диапазоне [1, 7]. Наша задача — написать функцию rand10() с диапазоном [1, 10], сохранив равномерное распределение. Дальше вместо rand7() будут использоваться переменные a и b. Скорее всего, вы сходу предложите одну из примитивных реализаций. Вот примеры:

func rand10() int {  
    a, b := rand7(), rand7()
    return a + b % 3
}

func rand10() int {  
    a, b := rand7(), rand7()
    return (a * b) % 10 + 1
}

Обе реализации неправильны

В первом варианте b % 3 даёт остатки от деления на 3, т.е. 0, 1 или 2 не с одинаковой вероятностью. Остаток 1 встречается чаще остальных, из-за чего получается неравномерное распределение итоговых значений.

Во втором варианте количество способов получить каждое произведение a * b тоже неравномерное.
Например:
- 1 = 1 * 1 → 1 комбинация
- 6 = 1*6, 2*3, 3*2, 6*1 → 4 комбинации
- 12 = 2*6, 3*4, 4*3, 6*2 → 4 комбинации
- 36 = 6*6 → 1 комбинация
и так далее

(...) % 10 + 1 ещё больше усугубляет ситуацию, потому что например при product = 2, 12, 22, 32, 42 мы будем везде получать значение 3

На графиках можно наглядно увидеть перекос, перебрав все 49 возможных комбинаций a и b.

Правильное решение

Рассмотрим формулу:
((a - 1) * 7 + b ) % 10 + 1

Она почти равномерна: значения от 1 до 10 встречаются почти с одинаковой частотой, за исключением 10, которое появляется всего 4 раза, тогда как остальные — по 5 раз.

Причина проста - всего комбинаций 7 × 7 = 49, нам не хватает числа 50.

Можно ли без него? Можно - проблема решается с помощью rejection sampling - мы отбрасываем значения больше 40. На языке кода мы делем пересчёт if num > 40. Тогда остаются только 40 комбинаций, которые можно равномерно разбить на 10 групп по 4 значения, что и видно на последней диаграмме

Финальный код:

func rand10() int {  
    for {  
       a, b := rand7(), rand7()
       num := (a-1)*7 + b  
  
       if num <= 40 {  
          return 1 + (num-1)%10  
       }  
    }  
}

Задача на Leetcode: https://leetcode.com/problems/implement-rand10-using-rand7/

Кратенький фанфакт. Обычно используется 0 как литерал для null pointer (говоря о С, макрос NULL там тоже обычно раскрывается в (void*)0 (иногда может в просто 0 или 0L)). Но совершенно не гарантируется стандартом, что 0 будет валидным null pointer для архитектуры! Вот тут hall of shame для именно таких динозавров с nullptr != 0.

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

Сейчас компилятор (что С, что плюсовый) сам подставляет корректный нулевой адрес вместо литерала 0 в контексте указателей.

Ну, то есть, получили, что ноль не всегда ноль. Ноль в контексте инта - ноль. Ноль в контексте указателя - нихуя не гарантированно ноль. Ноль ноль!