[Coding Test][Python] Hash Table(Dictionary) 개념 및 예제

※ Hash Table 이란?

효율적인 탐색을 위한 자료구조로써 key-value 쌍의 데이터를 입력받는다.        
Hash Function $h$의 key값을 입력으로 얻은 해시값 $h(k)$를 위치로 지정하여 저장한다.      
저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다.

 

Direct Access Address

Direct Access Address는 특정 Key 값을 주소로 직접 사용하여 데이터를 저장하는 방식이다.

위 2가지 단점이 존재하기 때문에 Key 값에 Hash Function을 적용하여 사용한다.

• 불필요한 메모리 공간 낭비
  • ex) Key 값이 1, 1000 => 2개의 데이터를 위해 1000개의 공간이 필요
• Key 값으로 문자열이 올 수 없다

Collision

서로 다른 Key의 Hash Function의 값이 같을 때 Collision이 발생했다고 한다.

중복되는 Key 값은 없지만 Hash 값은 중복될 수 있다.

따라서 Collision이 최대한 적게 발생하도록 Hash Funtion을 설계해야하고, Collision이 발생했을 때 Seperatre Chaining 또는 Open Addressing 등의 방법을 사용하여 해결해야한다.

 

Python에서 Hash Table은 Dictionary로 구현되어 있다.

1. Python Method 사용 방법

딕셔너리 생성

딕셔너리는 중괄호에 Key:Value 쌍을 주거나 list Index에 접근하는 것과 동일하게 생성 가능하다.

dic = {1:"철수", 2:"영희", 3:"민수", 4:"은지"}

print(dic)

dic = dict()
dic[1] = "철수"
dic[2] = "영희"
dic[3] = "민수"
dic[4] = "은지"

print(dic)

 

{1: '철수', 2: '영희', 3: '민수', 4: '은지'}
{1: '철수', 2: '영희', 3: '민수', 4: '은지'}

 

fromkeys(iterable=, value=)

Key List(Iterable)을 사용하여 모든 Key 값에 대해 동일한 값을 가지는 Dictionary를 생성한다.

dic = dict().fromkeys([1,2,3,4], 0)
dic

{1: 0, 2: 0, 3: 0, 4: 0}

 

keys(), values(), items()

Dictionary의 key값, value값, key-value 쌍을 return 한다.

dic = {1:"철수", 2:"영희", 3:"민수", 4:"은지"}
print(dic.keys())
print(dic.values())
print(dic.items())

 

dict_keys([1, 2, 3, 4])
dict_values(['철수', '영희', '민수', '은지'])
dict_items([(1, '철수'), (2, '영희'), (3, '민수'), (4, '은지')])

 

get(key=)

Key값에 해당하는 Value 값을 return한다.

값이 존재하지 않는다면 None return ( Index로 접근하는 방법은 Error)

dic = {1:"철수", 2:"영희", 3:"민수", 4:"은지"}
print(dic.get(2))
print(dic.get(5))
print(dic[2])
print(dic[5])

 

영희
None
영희
---------------------------------------------------------------------------
KeyError                       Traceback (most recent call last)
Cell In[30], line 5
        3 print(dic.get(5))
        4 print(dic[2])
----> 5 print(dic[5])

KeyError: 5

 

pop(key=), popitem()

Dictionary에 있는 Key-Value 쌍을 제거한다

popitem()은 가장 최근에 추가된 Key - value를 제거한다(Python 3.7이상부터 삽입 순서를 보장)

popitem()은 (key, value), pop()은 value를 return 하는 것에 주의

dic = {1:"철수", 2:"영희", 3:"민수", 4:"은지"}
# 가장 최근에 추가된 Key - value 제거
# Python 3.7이상에소는 딕셔너리가 삽입 순서를 보장한다.
print(dic.popitem())
print(dic)

dic = {1:"철수", 2:"영희", 3:"민수", 4:"은지"}
print(dic.pop(1))
print(dic)

 

(4, '은지')
{1: '철수', 2: '영희', 3: '민수'}
철수
{2: '영희', 3: '민수', 4: '은지'}

 

update()

Dictionary의 값을 update한다.

Index로도 가능하다.

dic = {1:"철수", 2:"영희", 3:"민수", 4:"은지"}

dic.update({1:"준수"})
print(dic)

dic[1] = "철수"
dic

 

{1: '준수', 2: '영희', 3: '민수', 4: '은지'}
{1: '철수', 2: '영희', 3: '민수', 4: '은지'}

 

setdefault(key=,default=)

특정 Key 값을 가져오거나, Key가 없으면 기본값을 설정하여 추가한다

dic = {1:"철수", 2:"영희", 3:"민수", 4:"은지"}

print(dic.setdefault(1, 0))
print(dic)

print(dic.setdefault(5, 0))
print(dic)

철수
{1: '철수', 2: '영희', 3: '민수', 4: '은지'}
0
{1: '철수', 2: '영희', 3: '민수', 4: '은지', 5: 0}

 

그외에도 dict().clear(), dict().copy()가 있습니다.

 

※ in 연산자

in 연산자를 사용하면 Dictionary에 특정 Key 값이 있는지 확인할 수 있다.

List에서 in 연산자를 통해 특정 원소가 들어있는지 확인할 수 있는데 List에서는 O(N)의 시간복잡도를 가진다.

하지만 Dictionary에서는 O(1)의 시간복잡도를 가지기 때문에 Dictionary와 in 연산자를 함께 사용하면 큰 힘을 발휘할 수 있다.

dic = {1:"철수", 2:"영희", 3:"민수", 4:"은지"}

for i in range(1, 6):
    if i in dic:
        print(dic[i])
    else:
        print(f"Key {i}가 존재하지 않습니다.")

 

철수
영희
민수
은지
Key 5가 존재하지 않습니다.

 

2. Dictionary를 사용한 예제

Longest Consecutive Sequence(LCS)

정렬되어있지 않은 정수형 배열 nums가 주어졌다       

nums 원소를 가지고 만들 수 있는 가장 긴 연속된 수의 갯수는 몇개인가?        

 

제약조건       
0 <= nums.length <= 10^5 ==> O(n^2)은 안되고 input이 없는 경우도 생각해야 한다              
-10^9 <= nums[i] <= 10^9        

input : [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]      
output : 9      
==> 중복되는 숫자는 포함 x

 

def longest_consecutive_sequence(nums:list)->int:
    answer = 0
    nums = dict.fromkeys(nums, False)

    for key in nums.keys():
        prev = key - 1
        # 이전 수가 존재하지 않을 때
        if prev not in nums:
            count = 1
            # 1 씩 증가시키며 consecutive sequence를 만들 수 있는지 확인
            while key + count in nums:
                count += 1

        answer = max(answer, count)
 

    return answer