Is there a built in implementation of hash table in python which finds the key based on value in O(c) time (c - constant). I guess dictionaries in python finds the key just by iterating through the values.
Asked
Active
Viewed 4,509 times
-4
-
2Python dictionary **is** a hash table: http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented – justhalf Aug 25 '14 at 06:36
-
2What makes you think Python dictionaries are O(n)? Why would that make sense? – Alexander Gessler Aug 25 '14 at 06:39
-
2That was a terrible guess, which a small amount of research could have disproved. – jonrsharpe Aug 25 '14 at 07:08
1 Answers
2
Python's dict is a hash-table (see this StackOverflow answer)
And from Python wiki:
Python's dictionary implementation reduces the average complexity of dictionary lookups to O(1) by requiring that key objects provide a "hash" function
