Oct 10, 2018

[HDGEM] A hash table can trade space for speed

We can reduce the look up time from O(n) to O(1) by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in near constant time. 

I say "near" because if a collision occurred, a look up could degenerate to O(n)time. But look up in hash table should be amortized O(1) time as long as the hash function was chosen carefully.


--
Posted By Blogger to HDGEM at 2/14/2017 03:51:00 AM