Постарайтесь выявить, где сосредоточены основные временные затраты в вашем hash_map, и каковы они. Сравните эти результаты с аналогичными результатами для стандартного map, а также для какого-либо иного hash_map.
Решим эту задачку чисто на теоретическом уровне. Самые большие временные затраты это при вызове функции resize() которая просто изменяет размер hash_map. Где еще могут быть большие затраты? Ну и могут еще быть временные затраты при вызове допустим случайно при операции поиска operator[] произошла проверка и у нас как бы размер вектора или хеш таблица не соответсвует и тогда происходит вызов resize() и из за этого может быть еще сильнее увеличится время, но это редкие случаи, не часто такое происходит.
Да и для аналогичного map возможно тоже resiz(), будет жрать время, но я не знаю, я этого не проверял, как то лень тестить, просто теоретически прикольнее решать быстрее.
[youtube]http://www.youtube.com/watch?v=0_wRyLvwPts[/youtube]