Исходное сообщение
"Результаты измерения производительности BerkeleyDB" Отправлено parad, 15-Апр-09 11:18
> Если хеш автоматически не меняет свой размер, то с ростом количества записей скорость доступа будет уменьшаться как O(количества ключей / количество ячеек в хеш-таблице), что по сути есть O(n). скорость доступа всегда O(1), даже если при возникновении коллизии мы проведем повторную операцию хеширования получим O(2) = O(1). есть методы заполнения позволяющие иметь кпд хеша 95% при максимум 3х вычеслениях хеша на операцию записи/чтения, что O(3) = O(1). тот метод, который возможно, вы имеете в виду (перебор в цикле всех последующих ячеек до нахождения свободной) описывается для облегчения понимания в начале каждого учебника, но никак не может быть использован в качестве рабочего варианта, т.к. сводит быстрый доступ по индексу к банальнобу перебору всех значений. > Хеш-таблица подходит для случаев, когда количество ключей сравнимо с размером таблицы, т.е. максимум в несколько раз больше. Читайте выше и дальше - это тоже самое начало любого учебника, есть методы быстрого заполнения хеша на 95%.