Associative array
Aka: map, dictionary
It stores key, value pairs. More commonly known as a map or dictionary.
| Pros | Cons |
|---|---|
| Provides fast key lookup | Depending on implementation, it might not be ordered |
| Inefficient lookup by values |
Implementations
Python: dict
m = dict(1=2, 2=4) # [1] = 2 [2] = 4
m[1] = 1 # [1] = 1 [2] = 4m.pop(1) # [2] = 4
m[3] = 6 # [2] =4 [3] = 6
C++: map
std::map<int, int> m { {1, 2}, {2, 4}}; // [1] = 2 [2] = 4
m[1] = 1; // [1] = 1 [2] = 4
m.erase(1); // [2] = 4
m[3] = 6; //[2] =4 [3] = 6
Java: Map
Map<Integer, Integer> m = new HashMap<>();
m.put(1, 2); // [1] = 2
m.put(2, 4); // [1] = 2 [2] = 4m.put(1, 1); // [1] = 1 [2] = 4
m.remove(1); // [2] = 4
m.put(3, 6); //[2] =4 [3] = 6
| Operations | Worst | Average |
|---|---|---|
| Delete | O(n) | |
| Insert | O(n) |
