Рассмотрите вопрос об оптимальной стратегии реализации hash_map, требующей минимального расхода памяти под такой ассоциативный контейнер. Затем рассмотрите вопрос об оптимальной стратегии реализации hash_map, достигающей минимального времени поиска. В обоих случаях решите, какими операциями пренебречь ради приближения к идеалу. Подсказка: имеется огромная литература посвященная хэшированию.
Мы эту задачку будем решать устно, так как она какаето философская. Давайте про минимальный расход памяти рассмотрим, Память у нас забирается в размере двух векторов, да у нас один вектор, таблица хэшей, она больше вектора значений в несколько раз я уже не помню как он увеличивается, так есть какие то коэффициенты которые проверяются и если таблица хэшей уже заполнена, то она автоматически увеличивается. Это сделано для того чтобы скорость возрастала, я честно когда читал не сильно понял.
От ссылка на наш hash_map http://www.kselax.ru/2013/06/shablon-hash_map/
«Затем рассмотрите вопрос об оптимальной стратегии реализации hash_map, достигающей минимального времени поиска.» Тут уже не сложно придумать что же делать? Как снизить скорость? Нужно просто сделать vector b равным vector v, ну это что бы они были одинакового размера, таблица хэшей равнялась v.
Остальную часть задачки пропустим, как то лень разбирать ее, хватит того что есть.
[youtube]http://www.youtube.com/watch?v=2uPyqwj8CJM[/youtube]