Compare and contrast a hash table vs. an STL map. How is a hash table implemented? If the number of inputs is small, what data structure options can be used instead of a hash table?

**Solution:**

Compare and contrast Hash Table vs. STL map

In a hash table, a value is stored by applying hash function on a key. Thus, values are not stored in a hashtable in sorted order. Additionally, since hash tables use the key to find the index that will store the value, an insert/lookup can be done in amortized time (assuming only a few collisions in the hashtable). One must also handle potential collisions in a hashtable.

In an STL map, insertion of key/value pair is in sorted order of key. It uses a tree to store values, which is why an insert/lookup is required. There is also no need to handle collisions An STL map works well for things like:

- find min element
- find max element
- print elements in sorted order
- find the exact element or, if the element is not found, find the next smallest number

How is a hash table implemented?

- A good hash function is required (e.g.: operation % prime number) to ensure that the hash values are uniformly distributed.
- A collision resolving method is also needed: chaining (good for dense table entries), probing (good for sparse table entries), etc.
- Implement methods to dynamically increase or decrease the hash table size on a given criterion. For example, when the [number of elements] by [table size] ratio is greater than the fixed threshold, increase the hash table size by creating a new hash table and transfer the entries from the old table to the new table by computing the index using new hash function.

What can be used instead of a hash table, if the number of inputs is small?

You can use an STL map Although this takes time, since the number of inputs is small, this time is negligible.

### Like this:

Like Loading...

*Related*