Map and Hash

1. Map(Hash Table)

• A map models a searchable collection of (key, value) entries
• value 중복은 허용되지만 key의 중복은 허용되지 않는다.
• 예시로 python의 dictionary가 있다. 

 

2. Map ADT(abstract data type)

• M[k] : return the value of v associated with key k, or(if the key is not exist) raise a KeyError
• M[k] = v : add or replace 
• del M[k]
• len(M)
• iter(M)
• k in M : return Ture if the map contains an item with key k
• M.get(k, d=None) : return M[k] if key k exists, or return d(default value)
• M.setdefault(k, d) : return M[k] if key k exists, set M[k] = d and return the value d
• M.pop(k, d=None) : pop M[k] if key k exists, or return d(default value)
• M.poptiems() : return an arbitrary key-value pair 
• M.clear() : remove all the items
• M.keys() : return all keys
• M.values() : return all values
• M.items()
• M.uptate(M2) 
• M == M2
• M != M2

 

3. Hash Fuction

• A hash function is any function that can be used to map data of arbitrary size to fixed-size values.
• The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. 
• This seemingly "magical" process of turning any type to an integer of range 0 to N-1 is usually viewed as two steps:
  1. Hash code : maps a key k to an integer
  2. Compression function : maps a key k to an integer

 

4. Hash Table

• A data structure where a map is implemented using a hash function is called a hash table.
• A hash function h maps keys of a given type to integers in a fixed interval 0 to N-1.

5. 

Hash를 이용하면 여러 method들을 O(1)으로 줄이는 것이 가능하다.