Menu
I am trying to understand how is iterating through a hashtable implemented. I just cannot imagine it. I am particularly interested in the speed of such iteration. For example:
QHash<int, std::string> hashTable;
...
for (auto it = hashTable.begin(); it != hashTable.end(); ++it)
std::cout << it.value() << std::endl;
Is this an O(hashTable.size()) operation?
I tried to dig in the source code, but could not find the proper definition.
367
Hashing is implemented in two steps: An element is converted into an integer by using a hash function. This element can be used as an index to store the original element, which falls into the hash table. The element is stored in the hash table where it can be quickly retrieved using hashed key.
The Hashtable class implements a hash table, which maps keys to values. Any non-null object can be used as a key or as a value. To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.
Hashtable is a kind of Hash map but is synchronized. Hash map is non–synchronized, permits one null key & multiple null values, not-thread safe i.e. cannot share between many threads without proper synchronization, the key/values pairs are stored in Hashtable.
It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.
Some implementations of hash tables also maintain a linked list of all entries to allow fast iteration (a so-called "linked hash-map").
When they don't, the only way is to iterate over all buckets of the hash table, while also iterating over the elements in each bucket.
The speed of this operation depends on the fill state of the table. When it's very low, a lot of empty buckets need to be iterated, which wastes time. When the table is filled well, and one or more elements are in each bucket, it's almost like iterating a linked list. On a perfect hash map where each bucket contains exactly one element, it's like iterating an array.
124
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
