Сколько хеш-ведер
Вы также можете использовать эту ссылку в Chrome для получения более подробной информации, чем это сделал инспектор.
chrome://net-internals/#events
Показывает журнал всех запросов браузера при открытии
5 ответов
Хорошее правило ползунка (не всегда идеал, ну, в общем, просто правило ползунка) состоит в том, чтобы перефразировать, если хеш-таблица заполнена до 80%. Это означает, есть ли у Вас 100 блоков и 80 объектов внутри, независимо сколько коллизии Вы имели прежде, это заставляет время увеличивать способность.
, Насколько необходимо увеличить его? Ну, нет также никакого идеального значения. Простое решение должно удвоить способность на каждом увеличении. Таким образом, это переходит в 200, 400, 800, и так далее. Если Вы будете думать, что это слишком много (в конце концов, то это спрыгнет с памяти на 8 МБ к 16 МБ, когда хеш-таблица станет действительно большой, и Вы никогда не можете заполнять 16 МБ), выберите, меньшее выращивают фактор. По крайней мере, 1/3, рекомендуют (рост его от 100 до 133), я сказал бы, возможно, позволить ему вырасти на 50% каждый раз как компромисс.
Примечание, что все это также зависит, как обрабатываются коллизии. Простой способ обработать их (мой любимый) состоит в том, чтобы сохранить объекты в связанном списке, когда существует коллизия. Если 3 объекта помещаются в тот же ключ, существуют все еще, до только 3 выдерживают сравнение для нахождения его. Начиная со связанного списка очень неэффективны для поиска, можно хотеть увеличить способность ранее, например, если 60%-я способность используется для хранения хеш-таблицы быстро. OTOH, можно сделать что-то более сложное и сохранить статистику о количестве коллизий. Пока у Вас едва есть любые коллизии (если у Вас есть очень хорошая хеш-функция) нет никакой потребности перефразировать вообще, даже если 99% ее способности используются. Также, если Вы обрабатываете коллизии сложным способом (например, каждый узел является снова отсортированной таблицей, и можно выполнить двоичный поиск в них) поиск мог бы все еще быть достаточно быстрым, если таблица загружается в 200% (таким образом, у Вас есть вдвое больше объектов как способность). В этом случае Вы могли сохранить статистику, насколько большой самая большая отсортированная таблица и когда это становится больше, чем, скажем, 8 записей, Вы думаете, что это становится слишком медленным, и затем Вы перефразируете.
Перефразирование является очень медленным, таким образом, его нужно избегать максимально часто. Таким образом, если необходимо перефразировать, только вырастите способность слишком мало, иначе необходимо перефразировать снова довольно скоро при добавлении большего количества объектов. Таким образом, когда необходимо перефразировать, сделайте способность значительно больше, чем количество объектов в настоящее время в таблице, все остальное - слишком мало способности.
Обычно Вы высматриваете коэффициент загрузки (неофициально, Вы уже сказали, что), который официально определяется как О± = n / N, т.е. отношение привыкших к общим блокам. Для хэш-таблицы, чтобы функционировать правильно (или по крайней мере рассуждать о ее производительности в математическом элементе), это должен быть О± < 1.
Все остальное действительно до эмпирических тестов: Если Вы видите, что Ваша хэш-таблица не выполняет хороший запуск в О± > 0.5, затем убедиться остаться под тем значением. Это значение также зависит от Вашего разрешения коллизий techique. Хеширование с объединением в цепочку может потребовать других коэффициентов загрузки, чем хеширование с открытым обращением. Еще одним фактором является местность кэша. Если Ваша таблица станет слишком большой, она не впишется в оперативную память. Так как Ваш доступ в массив случаен, загружение из кэша может стать узким местом.
При использовании Линейного Хеширования сама таблица автоматически заботится об изменении размеров путем поддержания постоянного коэффициента загрузки.
Обычно существует два типа хеш-таблиц: откройтесь и закрытый.
В открытой хеш-таблице Вы находите правильный блок на основе хеша, и затем создаете список объектов, зависающих от того блока.
В закрытой хеш-таблице Вы находите начальный блок с помощью значения хэш-функции, и если это занято, Вы зондируете для следующего значения. В упрощенном случае можно сделать это путем поиска следующего свободного блока, или можно создать второе значение хэш-функции из объекта и ступить тем (хотя необходимо удостовериться, что это главное по модулю размер хэш-таблиц, таким образом, Вы посетите все блоки).
открытая хеш-таблица обычно не изменяется. Вы устанавливаете начальный размер, чтобы быть тем, что Вы чувствуете, разумно для проблемы. Поскольку другие указали, что Вы могли изменить размеры на открытой хеш-таблице, но обоснование о производительности этой структуры данных теперь становится очень трудным. Если Вы изменяете размеры, когда длина данного блока является L тогда, Вы могли бы заканчивать тем, что изменили размеры на просто L объекты в целой хеш-таблице, которая очень неэффективна.
А закрылся, хеш-таблица изменена когда коэффициент загрузки (нет. из объектов в хеш-таблице / нет. из блоков), поражает некоторое предопределенное значение. Я склонен использовать 80%, но точное значение вряд ли будет слишком очень важно.
преимущество закрытой хеш-таблицы - то, что амортизировал , стоимость вставки объекта всегда O (1) (принятие хорошей хеш-функции). Вставка конкретного объекта могла бы быть O (N) из-за стоимости изменения размеров, но это делается очень нечасто.
Зависит от типа хэш-таблицы, которую Вы создаете. При использовании фиксированной основанной на массиве хэш-таблицы (в противоположность связанным спискам для блоков), необходимо изменить размеры массива или когда таблица полна или когда Вы поразили макс. тестовое количество (в зависимости от того, заботитесь ли Вы больше о скорости или памяти). При использовании связанных списков память не является таким же большим беспокойством с тех пор и не должна зондировать для вакуумов, таким образом изменение размеры не является столь же большим из соглашения.
ключ с хэш-таблицами является алгоритмом хеширования, не количеством блоков. Идеально, Вы всегда хотите самое большее один объект в каждом блоке, таким образом, необходимо идеально изменять размеры когда количество объектов в хэш-таблице = количество блоков. Если Ваши данные не равномерно распределяются, Вы лучше из с лучшим хеш-алгоритмом, чем лучшее изменяет размеры стратегии.