[algorithm] Hash table runtime complexity (insert, search and delete)

Why do I keep seeing different runtime complexities for these functions on a hash table?

On wiki, search and delete are O(n) (I thought the point of hash tables was to have constant lookup so what's the point if search is O(n)).

In some course notes from a while ago, I see a wide range of complexities depending on certain details including one with all O(1). Why would any other implementation be used if I can get all O(1)?

If I'm using standard hash tables in a language like C++ or Java, what can I expect the time complexity to be?

The answer is


Ideally, a hashtable is O(1). The problem is if two keys are not equal, however they result in the same hash.

For example, imagine the strings "it was the best of times it was the worst of times" and "Green Eggs and Ham" both resulted in a hash value of 123.

When the first string is inserted, it's put in bucket 123. When the second string is inserted, it would see that a value already exists for bucket 123. It would then compare the new value to the existing value, and see they are not equal. In this case, an array or linked list is created for that key. At this point, retrieving this value becomes O(n) as the hashtable needs to iterate through each value in that bucket to find the desired one.

For this reason, when using a hash table, it's important to use a key with a really good hash function that's both fast and doesn't often result in duplicate values for different objects.

Make sense?


Depends on the how you implement hashing, in the worst case it can go to O(n), in best case it is 0(1) (generally you can achieve if your DS is not that big easily)


Perhaps you were looking at the space complexity? That is O(n). The other complexities are as expected on the hash table entry. The search complexity approaches O(1) as the number of buckets increases. If at the worst case you have only one bucket in the hash table, then the search complexity is O(n).

Edit in response to comment I don't think it is correct to say O(1) is the average case. It really is (as the wikipedia page says) O(1+n/k) where K is the hash table size. If K is large enough, then the result is effectively O(1). But suppose K is 10 and N is 100. In that case each bucket will have on average 10 entries, so the search time is definitely not O(1); it is a linear search through up to 10 entries.


Some hash tables (cuckoo hashing) have guaranteed O(1) lookup


Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to data-structures

Program to find largest and second largest number in array golang why don't we have a set datastructure How to initialize a vector with fixed length in R C compiling - "undefined reference to"? List of all unique characters in a string? Binary Search Tree - Java Implementation How to clone object in C++ ? Or Is there another solution? How to check queue length in Python Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Write code to convert given number into words (eg 1234 as input should output one thousand two hundred and thirty four)

Examples related to hash

php mysqli_connect: authentication method unknown to the client [caching_sha2_password] What is Hash and Range Primary Key? How to create a laravel hashed password Hashing a file in Python PHP salt and hash SHA256 for login password Append key/value pair to hash with << in Ruby Are there any SHA-256 javascript implementations that are generally considered trustworthy? How do I generate a SALT in Java for Salted-Hash? What does hash do in python? Hashing with SHA1 Algorithm in C#

Examples related to time-complexity

Find common substring between two strings Why is the time complexity of both DFS and BFS O( V + E ) How to find time complexity of an algorithm Hash table runtime complexity (insert, search and delete) matrix multiplication algorithm time complexity how to calculate binary search complexity What are the time complexities of various data structures? Complexities of binary tree traversals Time complexity of Euclid's Algorithm What does O(log n) mean exactly?

Examples related to hashtable

How do I encode a JavaScript object as JSON? Hash table runtime complexity (insert, search and delete) Looping through a hash, or using an array in PowerShell Hash function for a string hash function for string iterating through Enumeration of hastable keys throws NoSuchElementException error How do HashTables deal with collisions? Good Hash Function for Strings Iterating over and deleting from Hashtable in Java What happens when a duplicate key is put into a HashMap?