Hashmaps and hashsets - Sam647254/Programetoj GitHub Wiki

The hashing function

The hashing function is a function that computes a "hashed value" of a given value in O(1) time. This hashed value will be used as the index used to retrieve the value in a hashmap or hashset.

Hashmap

A map (or sometimes called a dictionary or associative array) stores values under keys, which are unique with in a map (i.e. the same key can't have two different values). You have frequently used this data structure, as it is the basis for Python's dict.

Ideally, insertions, updates, and retrieval take O(1) time, but this may vary based on the hashing method used. For example, if all of the keys are hashed to the same hashed value, they will have to be placed in a list under that hashed value, making the operations take O(n) time. For practical purposes, you can assume that all operations take O(1) time.

The hashmap is used in situations in which you wish to store a value under a given key, and then retrieve that value using the key.

Hashset

In a set, the stored values are unique (i.e. inserting the same value twice will not add a second copy into the set). Similar to a hashmap, but the values cannot be individually retrieved. You use a hashset whenever you need to check whether a set includes a value. Python has the built-in set, which is a hashset. Common operations include union, intersection, and difference. It is also possible to iterate through a set, but the order is non-deterministic.