Привет, Хабр!

Полгода назад я задумался, как можно было бы получить элемент из бинарного дерева за O(log(N)). Ответ пришёл довольно быстро — Lazy Propagation. Но реализовать это в коде я поленился. Сейчас надо сдавать дипломный проект в университете, поэтому я занимаюсь чем угодно, только не им. Именно так я и сел это реализовывать.

Три дня назад я задумался об объединении сортировки подсчётом и деревом. Обсудив её с коллегой, пришли к следующему решению: вместо TreeSet использовать HashMap (при чём здесь вообще TreeSet, можно посмотреть ниже). Но и этого мне показалось мало, так что я решил реализовать собственную хэш-таблицу и посмотреть, что из этого выйдет. Результаты показались мне довольно интересными.