Hashing

A hash map is an unordered data structure that stores key-value pairs. A hash map can add and remove elements in $O(1)$, as well as update values associated with a key and check if a key exists, also in $O(1)$.

The biggest disadvantage of hash maps is that for smaller input sizes, they can be slower due to overhead. Because big O ignores constants, the $O(1)$ time complexity can sometimes be deceiving - it’s usually something more like $O(10)$ because every key needs to go through the hash function, and there can also be collisions. When different keys convert to the same integer, it is called a collision.

Hash tables can also take up more space. Dynamic arrays are actually fixed-size arrays that resize themselves when they go beyond their capacity. Hash tables are also implemented using a fixed size array. The problem is, a hash table may use an array that is significantly larger than the number of elements stored, resulting in a huge waste of space, and also resizing a hash table is much more expensive because every existing key needs to be re-hashed.

Time complexity functions only involve the variables you define. When we say that hash map operations are $O(1)$, the variable we are concerned with is usually $n$, which is the size of the hash map. However, this may be misleading. For example, hashing a string requires $O(m)$ time, where $m$ is the length of the string. The constant time operations are only constant relative to the size of the map. Hash map operations are $O(1)$, irrelevant of the size of the map.

A set uses the same mechanism for hashing keys into integers. The difference between a set and hash table is that sets do not map their keys to anything. Sets are more convenient to use when you only care about checking if elements exist. You can add, remove, and check if an element exists in a set all in $O(1)$.

Sets don’t track frequency. If you have a set and add the same element 100 times, the first operation adds it and the next 99 do nothing.

Count the number of subarrays with an “exact” constraint.