время доступа к хешу - это лучшее время O (1) и наихудший случай O (n). Мне интересно, каков средний случай?
Для хэша, который не близок к полному, средний случай примерно равен O (1).Детали в некоторой степени зависят от разрешения коллизий и от того, насколько полон хэш.Обычно эффективность начинает снижаться примерно на 80%.
На практике O (1). Смотри http://en.wikipedia.org/wiki/Hash_table#Performance_analysis