Let's say of have a python dictionary d with k entries. We know python implements dictionaries as hash tables. We implemented a hash table as a list of size m which contains a list for every possible output of the hash function. That raises the question, how many iterations are performed by a loop of the form
for key in d: do something at O(1)
Assuming there are more dictionary entries than the table size (k<m) as is the desired case,
It would make sense for it to run at O(k). However, if python's dict is implemented like our hash table, I assume it would have to go over all the lists in the table making it O(m). Is it possible to implement it so it runs in O(k)? Does python's dict do that?