Can hash tables really be O(1)?

by

You have two variables here, m and n, where m is the length of the input and n is the number of items in the hash.

The O(1) lookup performance claim makes at least two assumptions:

  • Your objects can be equality compared in O(1) time.
  • There will be few hash collisions.

If your objects are variable size and an equality check requires looking at all bits then performance will become O(m). The hash function however does not have to be O(m) – it can be O(1). Unlike a cryptographic hash, a hash function for use in a dictionary does not have to look at every bit in the input in order to calculate the hash. Implementations are free to look at only a fixed number of bits.

For sufficiently many items the number of items will become greater than the number of possible hashes and then you will get collisions causing the performance rise above O(1), for example O(n) for a simple linked list traversal (or O(n*m) if both assumptions are false).

In practice though the O(1) claim while technically false, is approximately true for many real world situations, and in particular those situations where the above assumptions hold.

More Related Contents:

  1. Big O, how do you calculate/approximate it?
  2. Optimizing Conway’s ‘Game of Life’
  3. Can an array be grouped more efficiently than sorted?
  4. What is tail call optimization?
  5. How can building a heap be O(n) time complexity?
  6. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  7. Big-O for Eight Year Olds? [duplicate]
  8. How do I check if a number is a palindrome?
  9. Is there an O(n) integer sorting algorithm?
  10. Which algorithm is faster O(N) or O(2N)?
  11. Algorithm to generate anagrams
  12. Generate all unique substrings for given string
  13. Efficiency of purely functional programming
  14. design a stack such that getMinimum( ) should be O(1)
  15. Time complexity of Sieve of Eratosthenes algorithm
  16. How to check if line segment intersects a rectangle?
  17. How to read values from numbers written as words?
  18. What is the fastest way to get the value of π?
  19. Find the first un-repeated character in a string
  20. What is a bubble sort good for? [closed]
  21. Iterating over a Binary Tree with O(1) Auxiliary Space
  22. How do I find a factorial? [closed]
  23. Quicksort superiority over Heap Sort
  24. Best way of calculating n choose k?
  25. Peak detection of measured signal
  26. Time Complexity of two for loops [duplicate]
  27. Algorithm for permutations of operators and operands
  28. Convert light frequency to RGB?
  29. Difference between Big-Theta and Big O notation in simple language
  30. Postfix notation to expression tree

Leave a Comment