EN VI

Algorithm - Hashtable lookup time confusing if hash function is not constant?

Algorithm - Hashtable lookup time confusing if hash function is not constant

In the hashtable, we generally say that insertion/lookup time is O(1).

I've read that this is only true if hashing function used is of constant time and it's said that constant time depends on the length of our key that we use. In some cases, the insertion time becomes O(k).

If programming languages use hash functions like keccak256 or sha or whatever to determine hashCode for a key in hashtable, then I agree that it might be true that insertion time might take more than O(1) in hashtable. but I just tried keccak256 with a text of 10000 length and it was instant, which begs the question: how is it that hashing on long texts increase insertion time from O(1) to O(k) ? I'm not experienced in hash function itself, so no need to go explaining that part. Just an overview explanation why it's O(k) and not O(1) while for my long text it was instant, would be appreciated.

Solution:

Hash functions used for hash tables are typically much, much simpler than sha256 or keckak256. For strings, for example, Java uses a simple 32-bit polynomial hash. The calculation is documented here: https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#hashCode
Hash table insertion time is usually quoted as expected constant time, but that does assume fixed length keys. For variable length keys, the insertion time is absolutely increased to O(k) where k is the key length... but computers seem to be a lot faster than you think they are. You say "I just tried keccak256 with a text of 10000 length and it was instant", but it was not. Calculating that hash probably took only a few microseconds, however, so I'm sure it looked instant to you. Do it a few million times and that starts to add up.