Java Hashtable Non-Constant Time Operations

Question

I am currently studying hash tables in Java and I had a question about operations of hash tables and their performance speed.

I read that a hash table can implement operations like insert, find, and remove in constant time, O(1). I am trying to figure out what makes a hash table's operation non-constant-time and what would some of those operations be?

I would think operations like size() would be in linear time because the speed depends on the size of the hash table but I am not sure.

Any ideas on this would be much appreciated!

Answer 1

In a naive implementation calculating the size would be linear, yes. But it's an easy optimization to cache the size in a variable, and well worth the extra couple of bytes and the minor performance hit of having to update that variable as elements are added and removed.

Keep in mind that insertion is O(1) amortized. It's not always a constant time operation. If the hash table grows overly full an insertion will cause it to be resized, an O(n) operation. Luckily, those resizes are rare and their cost can be averaged out among the other O(n) inserts, adding only a constant factor on average.

Also, insertion, finding, and removal are all O(1) on average, but they can be O(n) in the worst case. With a pathologically bad hash function their performance will severely degrade. In the worst case, all elements will be added to one single bucket in the hash table, effectively turning the hash table into a linked list.

Actually, in Java 8 they added an optimization to HashMap. If a bucket is large enough and keys are Comparable it'll use a binary tree instead of a linked list, improving worst case performance from O(n) to O(log n).