Они и в случае size_t -> size_t будут быстрее, если хэш-функция подобрана правильно. Если данные случайные и распределены равномерно, то это вообще просто - обычный остаток от деления подойдет, и значения функции будут распределены равномерно. Если данные неслучайные, то нужно подбирать функцию по тестовым наборам. Если данные целиком зависят от пользователя, то хэш-таблицу применять в этом случае нельзя, так как это потенциальный DoS. Кстати, насколько я знаю, hash_map использует для разрешения коллизий не списки, а те же красно-черные деревья, так что даже в худшем случае она не будет медленнее.
Booster Ну так я написал про неизвестные данные. И про потенциальный DoS тоже, когда все данные попадают в одну ячейку таблицы. Поиск: O(1+x) для хэш-таблиц, O(log(N)) для деревьев. Вставка: O(1) для хэш-таблиц, O(log(N)) для деревьев. Удаление: O(1+x) для хэш-таблиц, O(log(N)) для деревьев. x - коэффициент заполнения, обычно держится в интервале [0.5,1]. Где тут деревья быстрее? Не вижу. P.S. В худшем случае поиск и удаление - O(N) для хэш-таблиц со списками, и не говорите, что я этого не знал.
Блин, Вы считать умеете? Если таблица размером ~64кб (K = 16384 элементов), то средняя длина списка получается (0x80000000 / 16384) * N / 16384 = 8 * N. если в мапе ~ 1000 элементов, то сложность будет ~8000 операций. + какой оверхед по памяти? для дерева какая будет сложность?
Не понял? Откуда такая формула? Средняя длина списка равна N / K. Если N ~ K, то средняя длина будет равна 1. N - это число элементов, а не размер диапазона size_t. По-моему, тут как раз не я не разбираюсь в алгоритмах, Лол
У вас такое представление, будто коллизии - абсолютное зло. Это не так. Для хэш-таблиц коллизии - абсолютно нормальное дело, и если не доходит до вырожденных случаев, то они никак не влияют на скорость. Кто сказал, что она обязательно высокая? Ничего, что она зависит от хэш-функции, размера таблицы и самих входных данных и обычно является наоборот низкой? Средняя длина списка в любом случае всегда в точности равна N / K. Почему - советую вспомнить определение слова "средняя" и подумать самому.
Atlantic, Вы, наверное, не понимаете. Мы обсуждаем конкретную практическую задачу (где ключ изменяется от 0x00000000 до 0x7FFFFFFF) о целесообразности применения хеш таблиц. В данной задаче она высокая. Вы это понимаете?
В какой задаче? Какой набор из чисел size_t вставляется в таблицу? Случайный и равномерно распределенный или специально подобранный под хэш-функцию, чтобы убить скорость в ноль? Так какая у нас задача? Ну раз "в данной задаче она высокая", тот тут по умолчанию данные специально подбираются под хэш-функцию, чтобы все тормозило. Тогда и говорить не о чем.
Я не понимаю, почему так туго доходит. Ключ - случайное число в диапазоне от 0x00000000 до 0x7FFFFFFF.
Распределение равномерное? В таком случае со всей ответственностью заявляю - вероятность коллизий является максимально возможно низкой, даже если хэш-функция - простейшая F(X) = X % K. Потому что значения хэш-функции также будут случайны и распределены равномерно. Надеюсь, это не надо доказывать. Должно быть и так понятно. P.S. Но могу и доказать
Hash table в целом более эффективна по скорости, но у таблицы есть дополнительный расход на эту самую таблицу, плюс конечно не всегда она более эффективна. Опять таки возьмём случай с 7FFFFFFF ключей и таблицу к примеру размером 0xFFFF и если ключей у нас будет по максимуму, значит делим 7FFFFFFF на 0xffff, получаем что 0x8000 элементов будут в одном индексе таблицы, это явно уступает гарантированным log(0xFFFFFFFF).
Пусть F(X) = X % K, где K > 1. Нужно посчитать вероятность того, что для двух случайных равномерно распределенных X1 и X2 из диапазона 0...2^31-1 будет выполняться равенство F(X1)=F(X2). 1) Пусть F(X1) = Y. 2) Вероятность того, что F(X2) = Y будет по определению равна числу всех X, таких, что F(X) = Y, деленному на размер диапазона (2^31). 3) F(X) = Y при всех X = Y + K * M, 0 <= M < (2^31 - Y) / K. 4) То есть таких X будет не больше ceil((2^31 - Y) / K). 5) Отсюда вероятность того, что F(X2) = Y равна ceil((2^31 - Y) / K) / 2^31 6) По цепочке неравенств можно получить оценку этой вероятности сверху: ceil((2^31 - Y) / K) / 2^31 <= ceil(2^31 / K) / 2^31 <= (2^31 / K + 1) / 2^31 = 1 / K + 2^-31 Итак, вероятность коллизии двух значений функции будет не больше чем (1 / K + 2^-31). Что лишь чуть-чуть больше, чем идеально низкая для такой функции вероятность (1 / K). Посчитать среднее число коллизий в таблице размера K, содержащей N элементов можно по известным формулам из теории вероятностей. P.S. Холиварить на эту больше не собираюсь, переубеждать кого-то в чем-то нет смысла. Если не умеете видеть те случаи, когда хэш-таблицы применимы, а когда - нет, это только ваши проблемы. P.P.S. Конкретно для этой задачи (отображение size_t -> size_t) я бы использовал std::map. Если бы скорость не устраивала - использовал бы хэш-таблицу. Если же нужна упорядоченность или данные неслучайные, а std::map слишком медленный - написал бы реализацию структуры данных trie: _http://habrahabr.ru/blogs/algorithm/111874/
Во-первых, для 7FFFFFFF ключей и таблица будет не FFFF размером, а больше, во-вторых, где взять столько памяти, в третьих, для деревьев потребуется еще больше памяти, потому что два указателя на узел.
Atlantic А если неизвестно сколько будет ключей? Положим у кого-то их будет мало, у кого-то много. Сколько вы зарезервируете для этого случая? Я клоню к тому, что просто нет универсальных структур и алгоритмов. Нельзя тупо выбросить одно и использовать другое.
Стандартный прием - рост хэш-таблицы, если коэффициент заполнения достигнет установленного предела. Только асимптотика будет уже рассчитываться как амортизированная стоимость всех операций. Но лучше конечно использовать таблицы там, где заранее известен максимальный объем данных.
По другому нужно считать. Нужно считать вероятность встречи коллизии после вставки n+1-го элемента мапу. Из этого рассчитывать среднюю длину списка (исключая пустые списки).
