📚 Map

Map

fundamentals

→  dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys. / map data structure is defined as a data structure that stores a collection of key-value pairs, where each key is associated with a single value / maps provide an efficient way to store and retrieve data based on a unique identifier(the key)

 

→ Tuples can be used as keys if they contain only strings, numbers, or tuples; if a tuple contains any mutable object either directly or indirectly, it cannot be used as a key. You can’t use lists as keys, since lists can be modified in place using index assignments, slice assignments, or methods like append() and extend().

→ It is best to think of a dictionary as a set of key: value pairs, with the requirement that the keys are unique (within one dictionary). A pair of braces creates an empty dictionary: {}. Placing a comma-separated list of key:value pairs within the braces adds initial key:value pairs to the dictionary; this is also the way dictionaries are written on output.

→ The main operations on a dictionary are storing a value with some key and extracting the value given the key. It is also possible to delete a key:value pair with del. If you store using a key that is already in use, the old value associated with that key is forgotten(change a value). It is an error to extract a value using a non-existent key.

 

→ need for map data structure

(1) fast lookup: unordered maps allow for constant-time(O(1)) average-case lookup of elements based on their unique keys

(2) efficient insertion & deletion

(3) unique keys: ensure that each key is unique, allowing for efficient association of data with specific identifiers

(4) flexible data storage: store a wide variety of data types(as both keys and values) providing a flexible and versatile data storage solution

(5) intuitive representation: the key-value pair structure of maps offers an intuitive way to model and represent real-world data relationships.

 

→ properties of map data structure

(1) Key-Value association: allow you to associate arbitrary values with unique keys. Enables efficient data retrieval and manipulation based on keys

(2) Unordered: elements are not stored in any specific order. Iteration over a map will yield elements in an arbitrary order.

(however some map implementations(TreeMap in Java) maintain order based on keys)

(3) Dynamic Size: maps can grow & shrink dynamically as you add / remove elements. Flexibility allows them to adapt to changing data requirements

(4) Efficient Lookup: provide efficient lookup operations based on keys. Quickly find the value associated with a specific key using methods(get(), []) with an average time complexity of O(1) 

(5) Duplicate Key Handling: attempting to insert a key that already exists will typically overwrite the existing value associated with that key.(however, some map implementations, like multimap in C++, allow storing multiple values for the same key)

(6) Space Complexity: Hash-based maps typically have a space complexity(O(n)) / tree-based maps have a space complexity(O(nlogn))

(7) Time Complexity: Hash-based maps typically have an average time of O(1) / tree-based maps have an average time of O(logn)) + worst case time complexity for tree-based maps is still O(logn)

 

→ ordered vs. unordered

* ordered map: maintains the order in which key-value pairs are inserted(key and value are stored in the node)

: accessing element by key is efficient(typically O(log n)) / iteration over the map(typically O(n), preserves the insertion order)

: use cases(when the order of elements is important)

ex) binary search tree

 

* unordered map: the order in which elements are returned during iteratoin is not guaranteed and may vary across different implementations or executions

: implemented using a hash table / accessing elements by key is very efficient(typically O(1)) / making it faster than an ordered map in most cases / iterating over the map is less efficient than an ordered map(typically O(n))

: use cases(when the order is not important and fast access by key is crucial)

Feature	Ordered Map	Unordered Map
Order	Maintains an insertion order	No order
Implementation	Self-balacing tree, skip list, BST	Hash Table
Access by Key	O(logn)	O(1) average
Iteration	O(n)	O(n) (but less efficient than in an ordered map)
Use Cases	Order matters, LRU cache	Fast access, dictionaries

maps in C++

* C++ offers 2 primary map implementations

(1) std::map) standard ordered map. uses a red-black tree internally for efficient sorting and lookup operations

(2) std::unordered_map) uses a hash table for faster lookup operations.

Feature	Ordered Map	Unordered Map
Ordering	Ordereb based on keys	Unordered
Lookup Performance	Slower than std::unordered_map	Faster than std::map
Memory Overhead	Higher due to the red-black tree structure	Lower due to the hash table structure
Use Cases	when order of elements is important	when fast lookup performance is critical

 

 

 

 

maps in Python

techniques

① making a dictionary / change, delete, access

#1
tel = {'jack': 4098, 'sape': 4139}

#2
dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])

#3
dict(sape=4139, guido=4127, jack=4098)

#4
dict({1: 'Geeks', 2: 'For', 3: 'Geeks'})

#using tel dictionary
tel['guido'] = 4127 #add
tel['sape'] = 4111 #change
print(tel) #{'jack': 4098, 'sape': 4111, 'guido': 4127}
print(tel['jack']) #4098 - accessing

print('guido' in tel) # True - check key in a dictionary

del tel['sape'] 
print(tel) #{'jack': 4098, 'guido': 4127}

tel.pop('guido')
print(tel) #{'jack': 4098}

tel.popitem()
print(tel) #{} removes the last inserted key-value pair

 

② looping, sorted, 그 외 여러 dictionary 함수들

→ dictionary를 for loop으로 돌기 위해 dictionary_name.items()를 돌린다.

for k, v in tel.items():
    print(k,v)

'''
jack 4098
sape 4111
guido 4127
'''

 

→ keys()와 values()로 각각 key와 value list 출력

print(tel.keys()) #dict_keys(['jack', 'sape', 'guido'])
print(tel.values()) #dict_values([4098, 4111, 4127])

 

→ sort (dictionary sorting 꼭 기억하기!)

my_dict = {'banana': 3, 'apple': 1, 'orange': 2}

print(sorted(my_dict.items(), key=lambda item: item[1])) #Sorted based on values
#[('apple', 1), ('orange', 2), ('banana', 3)]

print(sorted(my_dict.items(), key=lambda item: item[0])) #Sorted based on keys
#[('apple', 1), ('banana', 3), ('orange', 2)]

print(sorted(my_dict.items(), key=lambda item: item[1], reverse = True)) #Sorted based on values in reverse order
#[('banana', 3), ('orange', 2), ('apple', 1)]

#or
print(sorted(my_dict.items(), key=lambda item: -item[1])) #only applied in numbers
#[('banana', 3), ('orange', 2), ('apple', 1)]

my_dict = {'banana': 1, 'apple': 1, 'orange': 2}
print(sorted(my_dict.items(), key=lambda item: (item[1], item[0]))) #sort based on values then keys
#[('apple', 1), ('banana', 1), ('orange', 2)]

time complexities

★ hash collision이 없다는 가정 하

+ 추가) checking a key in a dictionary(in operator) O(1) Time Complexity

---