### General - stores key value pairs - can add & remove elements, update values associated with keys, check if a key exists, & find length of hashmap in $O(1)$ - (for arrays, checking the existence of an element takes $O(n)$) - you can iterate over both the keys & values - called dictionaries in python - is an [[Unordered Data Structures|Unordered Data Structure]] - require unique, immutable key; meaning arrays would fail, in python you would need a tuple which is immutable ### Disadvantages - biggest disadvantage is that for smaller input sizes, they can be slower due to overhead - can also take up more space than arrays - 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, but resizing a hash table is much more expensive since each existing key needs to be re-hashed ``` # Declaration: a hash map is declared like any other variable. The syntax is {} hash_map = {} # If you want to initialize it with some key value pairs, use the following syntax: hash_map = {1: 2, 5: 3, 7: 2} # Checking if a key exists: simply use the `in` keyword 1 in hash_map # True 9 in hash_map # False # Accessing a value given a key: use square brackets, similar to an array. hash_map[5] # 3 # Adding or updating a key: use square brackets, similar to an array. # If the key already exists, the value will be updated hash_map[5] = 6 # If the key doesn't exist yet, the key value pair will be inserted hash_map[9] = 15 # Deleting a key: use the del keyword. Key must exist or you will get an error. del hash_map[9] # Get size len(hash_map) # 3 # Get keys: use .keys(). You can iterate over this using a for loop. keys = hash_map.keys() for key in keys: print(key) # Get values: use .values(). You can iterate over this using a for loop. values = hash_map.values() for val in values: print(val) ``` ### Counting - tracking the frequency of things - anytime you need to count anything, think of hashmaps - very common hashmap pattern - hashmaps can also be used to for [[Arrays|Array]] subarray problems that require an 'exact' constraint - as we do a 'sliding window' and iterate through all possible ending indices for viable subarrays, we can build a prefix sum through the keys of a hashmap $count$ - we can also keep a variable $curr$ that has our current prefix sum, that will be added to the hashmap - at every possible ending index, the possible subarrays are the number instances of $curr - k$ that already exist in the hashmap - the exact subarray constraint uses the count hashmap with sliding window end index