Waiting time paradox #2: почему успешный поиск в хэш-таблице дольше не успешного?

…Продолжение предыдущей статьи про waiting time paradox: на этот раз разберемся, почему успешный поиск в хэш-таблице обычно дольше, чем не-успешный

Возьмем классическую хэш-таблицу с разрешением коллизий цепочками: K пар ключ-значение, B корзинок со связными списками для разрешения коллизий, вот это все. Мы ищем в этой таблице разные ключи (а зачем еще нужна хэш-таблица?). Для каких-то ключей в таблице находится соответствие, для каких-то – нет.

Вопрос: что больше – среднее количество сравнений при успешном поиске, или среднее количество сравнений при неуспешном поиске?

За идею этой статьи я тоже благодарен профессору Куперу, и его статье Teletraffic Theory for Hash-Structured Files. Но прежде чем вы броситесь ее читать, я отмечу, что утверждение, из которого вырос этот пост – это лишь одно из замечаний в самом конце статьи. Статья же на 99% фокусируется на другом: там рассматривается поведение хэш-таблицы на диске в динамике – т.е. когда ключи добавляются-удаляются с какой-то частотой. В привычных современным программистам терминах это описание кэша, основанного на хэш-таблице, в который ключи добавляются с какой-то частотой, и имеют некое "время жизни", прежде чем их удалят. Короче: там вообще не об этом

Интуитивный ответ: среднее количество ключей в корзинке K/B, для успешного поиска нужно перебрать, в среднем, половину из них, а для неуспешного поиска – все.

Конечно, если бы интуитивный ответ был верен – я бы не стал об этом писать (это само по себе можно считать примером sampling bias). Дело в том, что вероятность найти/не найти ключ в корзинке – коррелирует с количеством ключей в корзинке. Где более вероятно найти заданный ключ: в корзинке, где лежит только 1 ключ, или в корзинке, где лежит 10 ключей? Как правило, чем больше ключей в корзинке – тем больше вероятность, что искомый ключ среди них все-таки есть, и наоборот.

А значит если в какой-то корзинке мы нашли ключ – вероятно, что эта корзинка была более заполнена, по сравнению с типичной ("средней"). И наоборот: если мы знаем, что в какой-то корзинке мы ключ искали, но не нашли – вероятно, что та корзинка была менее заполнена, чем типичная.

Если это не очевидно, можно помочь воображению вырожденным примером: если мы нашли ключ в какой-то корзинке, то совершенно точно в этой корзинке было >0 ключей. А вот если мы ключ в корзинке не нашли – вполне возможно (хотя и не обязательно), что корзинка была пуста. То есть когда мы будем считать средний размер корзинок для случая успешного поиска – в эту сумму точно не попадут корзинки размером 0. А вот в сумму для среднего по не-успешным поискам какие-то пустые корзинки попадут. Значит суммы для среднего размера "успешных"/"не успешных" корзинок определенно будут отличаться – хотя бы на это слагаемое

Похоже, мы снова имеем дело с чем-то вроде (обобщенного) парадокса времен ожидания, aka size-biased sampling: в хэш-таблице обычно лишь небольшое количество корзинок содержат много ключей, но именно в этих корзинках мы будем чаще всего находить нужный нам ключ – просто потому, что в таких корзинках больше кандидатов! И значит именно эти размеры корзинок будут с бОльшим весом входить в сумму для "среднего размера корзинки где мы нашли ключ". И наоборот – для в сумму для "среднего размера корзинки, где мы не нашли искомый ключ" будут с бОльшим весом входить корзинки с нетипично малым количеством ключей (например, пустые).

А велика ли разница?

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

Оказывается, и это под вопросом. Однозначного ответа тут нет – в общем случае результат может быть и такой и эдакий. Но утверждается, что как раз для типичного (практически важного) случая хэш-таблицы с небольшим количеством коллизий (низким load factor-ом) эффект от inspection/waiting time paradox оказывается достаточно велик, и средние размеры "успешных"/"не успешных" корзинок различаются более чем в два раза:

…In both models, numerical calculations show that, if the chain is not too long, the average length of an unsuccessful search, which is defined to be the number of accesses required to reach the end of the chain, is less than the average length of successful search, which goes only to the "middle" of the chain

(та самая статья)

То есть "if the chain is not too long", то эффект от "парадокса времен ожидания" перебивает двухкратную разницу в средней длине поиска – и оказывается, что успешный поиск требует больше сравнений (в среднем), чем неуспешный, даже несмотря на то, что успешный поиск перебирает (в среднем) лишь половину ключей в корзинке

Но в статье не приводятся конкретные цифры, просто констатируется факт, так что разбираться подробнее придется самому

Во-первых, почему "if the chain is not too long" – почему важно, чтобы цепочки (=размеры корзинок) не были слишком большими? Можно порассуждать, почему. Неизвестно, как выглядит формула для size-biased sampling в этом случае, но логично предположить, что все упирается в вариабельность (коэффициент вариации) – как и для обычного парадокса времен ожидания. То есть чем больше вариабельность – отношение стандартного отклонения к среднему – тем больше эффект. Но чем больше в среднем ключей на корзинку в хэш-таблице, тем меньше вариабельность их количества – это центральная предельная теорема. Тогда все звучит логично: условие "не очень длинных цепочек" означает, что эффект size-biased sampling оказывается достаточно велик только тогда, когда размер корзинок имеет большую вариабельность, а это случается когда корзинки еле-еле заполнены – то есть когда у хэш-таблицы низкий load factor.

Во-вторых – а есть ли мальчик? Прежде чем разбираться, как возникает этот эффект, надо проверить, а есть ли он вообще (мало ли, что там пишут, может я все неправильно понял). Благо несложно симулировать поиск в хэш-таблице, и записывать размер корзинки, где он происходил. На графике ниже результаты такой симуляции для хэш-таблицы из 128 корзинок, и разного числа ключей/load factor-а:

Действительно: пока загрузка (load factor) таблицы меньше примерно 1.8-2.2 – успешный поиск дороже, чем не успешный, а по мере роста загрузки таблицы соотношение между ними приближается к 1/2.

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

Можно это описать математически? (beware!)

Давайте попробуем. У нас есть хэш-таблица с B корзинками, и мы кладем в нее K ключей. При этом ключи как-то распределятся по корзинкам. Как?

Попробуем оценить распределение приближенно: если ключи случайные, и хэш-функция достаточно хорошая, то вероятность попадания каждого конкретного ключа в конкретную корзинку это просто 1/(кол-во корзинок) = 1/B.

Значит (в первом приближении) вероятность того, что в корзинке окажется b ключей это вероятность, что из K попыток с вероятностью успеха 1/B мы получим b успехов – т.е. биномиальное распределение: $$bin(K, 1/B) = C^b_K \big(\frac{1}{B}\big)^b\big(1-\frac{1}{B}\big)^{K-b}$$

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

Биномиальное распределение удобно тем, что про него мы много знаем можем посмотреть в википедии. А именно: среднее значение для него $$\mathbb{E}[b]=\frac{K}{B}$$ (ну, это и так очевидно), а еще я сердцем чую, что нам понадобится дисперсия, так она равна $$\mathbb{D}[b]=\frac{K}{B}(1-\frac{1}{B})$$

Теперь попробуем посчитать среднюю длину успешных и неуспешных поисков.

Я начну с неуспешных, потому что они проще. Если мы ищем произвольный ключ, которого нет в таблице, то чтобы убедиться, что его там нет, нужно перебрать все ключи в той корзинке, в которую нас закинула хэш-функция. Но раз мы предполагаем, что хэш-функция у нас хорошая, а ключ – произвольный, то мы будем равновероятно попадать в корзинки всех существующих в хэш-таблице размеров. А значит среднее количество сравнений, которое потребуется, чтобы не-найти ключ – это просто средний размер корзинки, $$\mathbb{E}[L_u]=\mathbb{E}[b]=\frac{K}{B}$$

Теперь об успешных поисках – это только чуть посложнее. Возьмем случайный ключ из тех, что присутствуют в хэш-таблице. Какова вероятность, что такой ключ окажется из корзинки i? Эта вероятность равна доле всех ключей, которая хэшируется в эту корзинку. Но мы знаем, какие ключи хэшируются в эту корзинку – это те ключи, которые сейчас там лежат. То есть случайно выбранный ключ, из тех, что присутствуют в хэш-таблице, найдется в корзинке i с вероятностью (количество ключей в корзинке i)/(общее количество ключей) = $$\frac{b_i}{K}$$

А сколько сравнений нужно, чтобы найти ключ уже внутри корзинки? В среднем $$\frac{1+2+3+..+b_i}{b_i} = \frac{b_i+1}{2}$$.

Так что среднее количество сравнений по всем ключам получается такое:

$$E[L_s]= \sum_{i=0}^B \frac{b_i}{K}\frac{b_i+1}{2} = \frac{1}{2}\Big(\frac{\sum_{i=0}^Bb_i^2}{K} + \frac{\sum_{i=0}^Bb_i}{K}\Big) = \frac{1}{2}\Big(\frac{B}{K}\frac{\sum_{i=0}^Bb_i^2}{B} + 1\Big) = \frac{1}{2}(\frac{\mathbb{E}[b^2]}{\mathbb{E}[b]}+1) = \frac{1}{2}(\mathbb{E}[b]+\frac{\mathbb{D}[b]}{\mathbb{E}[b]}+1)$$

(Вот ведь не зря сердце чуяло – пригодится, пригодится дисперсия!)

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

Осталось немного позаниматься алгеброй: подставить среднее и дисперсию для биномиального распределения, посчитать отношение $$\frac{\mathbb{E}[L_s]}{\mathbb{E}[L_u]}$$, и сравнить его с единицей:
$$\frac{\mathbb{E}[L_s]}{\mathbb{E}[L_u]}=\frac{\frac{1}{2}(\mathbb{E}[b]+\frac{\mathbb{D}[b]}{\mathbb{E}[b]}+1)}{\mathbb{E}[b]} = \frac{B}{K}+\frac{K+1}{2K} \overset{K \gg 1}{\approx} \frac{B}{K}+\frac{1}{2}$$

(количество ключей K обычно >>1, так что (K+1)/K ~ 1)

Чтобы эта штука была больше единицы, достаточно, чтобы K/B было больше 2. Теперь уже можно ответить на исходный вопрос: если K/B (=load factor) < 2, то успешный поиск в среднем дольше неуспешного, и наоборот

Напомню, что java.util.HashMap по-умолчанию имеет load factor=0.75 – гораздо ниже порога. То есть все описанное выше применимо к абсолютному большинству хэш-таблиц в любой джава-программе.

Можно прикинуть и во сколько раз больше сравнений нужно будет, в среднем, для успешного поиска при load factor=0.75: 1/0.75+1/2 ~ 1.85, почти в 2 раза

Если такая большая разница кажется вам нереальной, то вспомните про пустые корзинки. В хэш-таблице с загрузкой 0.75 не менее четверти корзинок – пусты. Это значит, что >1/4 всех неуспешных запросов завершаются без единого сравнения ключей, просто потому, что хэш-функция отправила их в пустую корзинку. Но каждый успешный запрос завершается не менее чем за одно сравнение ключей. Если мы предположим идеальную раскладку таблицы, без коллизий, то 3/4 всех не-успешных поисков будут завершаться за 1 сравнение, и 1/4 за 0 сравнений, и все успешные запросы будут завершаться за 1 сравнение. То есть среднее количество сравнений при неуспешном поиске это 3/4 от успешного.

Это гарантированное сравнение, которое присутствует в каждом успешном поиске – это та самая единица в формуле, которая играет свою роль. Если бы ее не было, то эффект все равно проявлялся бы, но только при load factor < 1, и был бы заметно слабее

Насколько теория похожа на симуляцию, видно на вот этом графике. (Мне пришлось построить обратное отношение: не-успешных поисков к успешным – потому что иначе в нуле получается вертикальная асимптота, и такой график неудобно смотреть)

Честно говоря, даже слишком хорошо. На физпрактикум мне такое было бы неловко сдавать – обвинили бы в подгонке :)

Все вышесказанное, конечно, применимо не только к поиску: и обновление, и удаление существующего ключа так же будет (как правило) дольше, чем вставка нового, или попытка удаления не существующего