Java hashtable non constant time operation

I am currently learning the hash table in Java. I have questions about the operation and performance speed of the hash table

I read that the hash table can be inserted, found and deleted in constant time o (1) I'm trying to figure out what makes hash table operations very time-consuming, and what will these operations be?

I think operations like size () will be in linear time because the speed depends on the size of the hash table, but I'm not sure

Any ideas will be appreciated!

Solution

In a naive implementation, the computational size will be linear, yes However, the cache size in a variable is a simple optimization, which is well worth a few extra bytes and the secondary performance loss of having to update the variable when adding and deleting elements

Remember, the insertion is O (1) amortization It is not always a constant time operation If the hash table grows excessively, the insertion will cause its size adjustment, that is, O (n) operation Fortunately, these adjustments are few, and their costs can be averaged in other o (n) insertions, adding only a constant factor on average

In addition, insertion, lookup and deletion are o (1) on average, but in the worst case, they can be o (n) Using ill - conditioned hash functions, their performance will be seriously reduced In the worst case, all elements will be added to a bucket in the hash table, which effectively converts the hash table into a linked list

In fact, in Java 8 they added an optimization to HashMap If a bucket is large enough and the key is comparable, it will use a binary tree instead of a linked list to improve the worst-case performance from O (n) to o (log n)