Реализуйте hash_map, используя Splay-деревья (см. D. Sleator, R.E. Tarjan, Self-Adjusting Binary Search Trees, JASM, Vol. 32, 1985).
Ничего мы эту задачу не будем делать, потому что много времени заберет разбор что такое Splay-деревья. Я уже когда то делал на тему красно-черное дерево, мучился долго с ним, а толку мало.
[youtube]http://www.youtube.com/watch?v=716FH5Q06jU[/youtube]
[youtube]http://www.youtube.com/watch?v=lnK8pV-AGUc[/youtube]