Recent students that I've encountered seem to insist that hash tables are O(1). However hash collisions are inevitable, therefore whatever you're using as a bucket is the real determinant of performance. If the bucket is a linked list, your hash lookup performance will become O(n). Then the argument becomes one of just increasing the number of buckets. But you never know how many you'll need, so collisions are inevitable. And yet kids still insist that hashes are O(1). Why are colleges confusing kids about hashes?