Здравствуйте, mikkri, Вы писали:

M>Здравствуйте, Бизон, Вы писали:

Б>>Но время поиска в них эквивалентно логарифму, а не константа как в случае хэш таблицы

M>Какое интересное заблуждение. Время поиска в хеш-таблице константа только когда все ключи после нормализации различны. Что на практике верно очень редко. Рекомендую освежить/обновить знания.

Гы гы
Для особо одаренных переформулируем так:
если n-количество ключей, p — максимальное количество различных нормализованных ключей
то время доступа эквивалентно n/p. Отношение n/p поддерживается в таблице постоянным с помощью операции rehash.
Уменьшение значения этой величины уменьшает время доступа но увеличивает потребление памяти. Увеличиние приводит к обратным последствиям.
Возвращаясь к моему утверждению про скорость доступа:
1) Если ключи после нормализации различны то скорость доступа равна 1
2) Если ключи не различны то средняя скорость доступа константа, размер константы n/p

Все рассуждения верны для хорошо распределенных ключей.