Ruby’s Hash, пожалуй, самый полезный тип данных в языке. Используя структуру, которая хорошо подходит для моделирования реальных проблем, в сочетании с быстрым поиском, он часто является основой сценариев, веб-страниц и сложной бизнес-логики. Он даже когда-то использовался внутренне Ruby для хранения всех ваших функций, переменных и констант (хотя современный Ruby подходит к этому по-другому, используя предсказание ветвлений горячих путей и кеширование методов сайта вызова; это еще один пост!) Мы часто принимаем это как должное что это «просто работает». Сегодня мы собираемся вникнуть во внутренности Hash, выяснив, почему он работает, насколько он эффективен и как он реализован. Вперед!
Реализация
big_four_stock_prices = { :google => 801.23, :apple => 115.57, :facebook => 128.35, :microsoft => 57.19 } Что тут происходит? Давайте пройдемся по нему.
Во-первых, среда выполнения выделяет непрерывный блок памяти для структуры данных. Далее он хеширует первый ключ:
:google.hash => 3592
hash функция объявлена в классе ядра Ruby, так что она доступна для любого класса с таким в цепочке наследования. Фактическое число будет варьироваться в зависимости от ряда факторов, но важно то, что оно остается неизменным на протяжении сеанса.
Далее мы должны сохранить значение. Значение помещается в то, что называется «корзина» (или «корзина», если вы пришли из других языков). Хэш Ruby первоначально выделит 11 сегментов, поэтому нам нужно решить, в каком сегменте хранить наше значение хэша. Для этого среда выполнения просто выполняет следующие вычисления:
:google.hash % 11 => 5
Это означает, что значение для :google , которое является 801.23 , помещается в 5-ю 801.23 хеш-таблицы с идентификатором для его ключа, который выглядит примерно так:
[:google, 801.23]
Он повторяет этот процесс для остальных пар ключ / значение. Чтобы вытащить его обратно, интерпретатор просто повторяет вычисление и вытаскивает значение из корзины. Просто верно? Давайте в крайние случаи.
Столкновения
Более проницательные читатели среди вас, возможно, заметили тот факт, что если существует только 11 возможных сегментов, то рано или поздно в результате вычисления будут помещены два значения в один сегмент. Что происходит потом? Что ж, реализация хэша в Ruby будет хранить элементы в одной корзине в виде связанного списка. Если идентификатор (ключ) совпадает с сохраненным (он проверяет это с equal? ), Он возвращает значение, а если нет, он просто продолжает просмотр списка.
Конечно, этот процесс может занимать много времени — что, если элемент разделил корзину с 1000 другими? Теоретически для возврата желаемого значения может потребоваться много времени, и весь смысл использования хеш-таблицы в том, что она быстра. Руби, конечно, тебя охватила. Это достигается путем сохранения промежуточного итогового среднего количества элементов в каждой корзине по всей таблице. Когда это значение превышает 5, Ruby отбрасывает массив из 11 бинов, создает новый, и именно в этот момент Ruby перефразирует значения. Благодаря этому связанные списки в корзинах становятся короткими, что сокращает общее время поиска.
Время поиска является ключевым пунктом продажи для хэша. Для обозначения Big O, склоняемого среди вас, хеш-таблица будет искать значения в постоянное время; то есть, поскольку число значений в таблице увеличивается, время поиска остается тем же. На практике это ближе к O (log n) , но давайте не будем слишком педантичными!
Важность хорошего алгоритма хеширования
Чтобы закрепить наше понимание реализации хеширования, давайте попробуем провести небольшой эксперимент: что произойдет, если пользовательская хеш-функция каждый раз будет возвращать одно и то же целое число? Наша ментальная модель хэша предполагает, что это добавит каждый элемент в связанный список в том же бункере, и время поиска элемента в конце этого списка будет намного выше. Давайте попробуем с некоторым кодом:
require 'benchmark' class GoodHash end class BadHash def hash 7 end end hashing_algorithm == BadHash # switch to GoodHash for inverse 17.times do |ex| lookup_key = nil size = 2**ex test_hash = {} (1..size).each do |n| index = hashing_algorithm.new lookup_key = index if n > size/2 and lookup_key.nil? test_hash[index] = rand end Benchmark.bm do |bench| bench.report("Hash size: #{size} elements 10000 times\n") do 10000.times do test_hash[lookup_key] end end end end
Это сгенерирует хеш (разных размеров), подобный этому:
test_hash = { #<BadHash:0x007f92941eaae0> => 0.029655456018705673, #<BadHash:0x007f92941e3c68> => 0.973576967117432, #<BadHash:0x007f92941e1508> => 0.2443654110192186, #<BadHash:0x007f92941d1ab8> => 0.7536013342129247 }
Давайте пройдемся по коду:
Сначала мы создаем класс GoodHash , который использует собственный алгоритм хэширования Ruby. Затем мы повторяем цикл 17 раз (65536 пунктов, кажется, хорошее место, чтобы остановиться!), Возводя в степень основание 2 к степени ( ex ). Затем мы вставляем случайное значение в test_hash используя в качестве ключа экземпляр GoodHash . Мы смотрим на это значение 1000 раз и сравниваем результаты, прежде чем повторить процесс с BadHash
Результаты (показания взяты из «реальной» колонки):
| Размер хеша | GoodHash | BadHash |
|---|---|---|
| 1 | 0.002808 | 0.003077 |
| 2 | 0.002841 | 0.003663 |
| 4 | 0.003018 | 0.004167 |
| 8 | 0.005757 | 0.004750 |
| 16 | 0.003502 | 0.006898 |
| 32 | 0.003174 | 0.011138 |
| 64 | 0.002843 | 0.019534 |
| 128 | 0.003080 | 0.041806 |
| 256 | 0.003159 | 0.086643 |
| 512 | 0.003137 | 0.147724 |
| 1024 | 0.003179 | 0.287432 |
| 2048 | 0.002843 | 0.554049 |
| 4096 | 0.002828 | 1.101022 |
| 8192 | 0.005380 | 2.192948 |
| 16384 | 0.003037 | 4.385111 |
| 32768 | 0.002830 | 8.739381 |
| 65536 | 0.002830 | 17.314654 |
Это доказывает нашу гипотезу довольно убедительно. По мере увеличения количества элементов в хэше время поиска с классом BadHash увеличивается в геометрической прогрессии, в то время GoodHash реализация GoodHash остается GoodHash сгруппированной примерно в одно и то же время. Значения в столбце GoodHash также иллюстрируют перефразирование Ruby после переполнения сегментов.
Интересно, что Ruby 2.0 и выше не работает так для меньших хэшей. Если ваш хеш равен 6 элементам или меньше, он сохраняется в виде списка массивов и прослеживается до тех пор, пока ключ не совпадет с поиском. В то время как хеш-таблицы быстрые, безусловно, самая большая стоимость — это вычисление хеш-значения; процесс аккуратно обошел стороной этот подход. В случае, если хэш увеличивается до 7 элементов, массив отбрасывается и используется традиционный хэш. Это показано в таблице результатов, как и запись с размером хэша 8.
Как Ruby выделяет контейнеры?
Поскольку количество бинов не увеличивается линейно с количеством элементов в них, как Ruby решает, сколько бинов должно иметь хеш? Что ж, Ruby вычисляет список простых чисел, близких к степеням 2. Преимущество этого состоит в том, что число в сочетании со значением хеш-функции с меньшей вероятностью будет иметь общий фактор. Если это не так, то вычисление модуля, которое мы рассмотрели ранее, может давать одно и то же число каждый раз, что поместит все в один и тот же мусорный бак, что мало чем отличает нас от предыдущего эксперимента.
Вывод
Для погружения во внутренности Ruby это было относительно просто. Хотя мы довольно широко рассмотрели хэши, важно знать, когда и где их использовать. Безусловно, самыми большими затратами на хеширование являются перефразирование, вычисление хэша и разбивка на сегменты, поэтому следует помнить об этом, когда производительность является фактором ( реализация JRuby избегает полагаться на хэши изнутри именно по этой причине ). Однако, как правило, хэш является отличным инструментом для поиска, учитывая его интеллектуальный дизайн и тщательную оптимизацию. Теперь мы точно знаем, как работает хеш, почему он так производителен, и никогда не переопределяем хеш-функцию для объекта!