해시테이블(Hash Table)과 Dictionary

1. 해시테이블 종류

1. Array list based (Open addressing) => 파이썬에서 구현해 놓은 해시테이블
2. Array list + Linked list based (Seperate chaining)
3. Find key O(1)

괄호에 들어간 내용은 해시테이블에서 나는 충돌을 해결하는 방법 (기술면접에서는 중요함)

 

2. 해시테이블?

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

2-1. 예시

해시테이블은 어쨋든 list라서 인덱스가 있다. 해시테이블에서 인덱스를 저장하는 방법을 코드로 들어보자면

def hashFunction(key):
	return key % 9 # 이건 리스트가 9의 길이라고 가정

이런식의 그림이 된다 위의 해시값을 인자로 받아서 해당 리스트의 크기만큼 나눈것을 리턴하여 해시테이블의 인덱스로 지정해준다

3. 해시테이블의 문제점

해시테이블의 문제점이 있는데 바로 어떤 해시코드를 가공해서 index로 만들었을 때 그 인덱스에 어떤 정보가 이미 들어가 있을 수 있다.

그럴때 사용하는 두가지 방법이 위에서 언급한

1. Open addressing
2. Seperate chaining

이 두가지 방법인데 파이썬에서는 Open addressing으로 문제를 해결한다

3-1. Open addressin

만약 이미 들어가있는 요소가 있다면 바로 다음 인덱스에 저장하는 방식인데 여기서 중요한 점은 시간 복잡도이다.

해시값으로 해당 인덱스에 찾아가는건 O(1)으로 구현된다.

파이썬에서는 이 해시테이블이 Dictionary로 구현이 되어있다

4. Dictionary

우리가 시험 성적을 리스트에 저장한다고 생각해보자

score = [97, 49, 89]

이렇게 저장했을 경우에 어떤 과목의 점수인지 알수가 없다

이럴 경우에 Dictionary를 사용한다

4-1. 딕션어리 만드는법

score = {
  'math' : 97,
  'eng' : 49,
  'kor' : 89
}

자바스크립트의 객체 처럼 중괄호를 사용한다.

4-2. 딕션어리 다뤄보기

접근

score['math'] # 97

수정

score['math'] = 45
print(score['math']) # 45

추가

score['sci'] = 100

4-2. 만약 과목이 1억개라면?

print('music' in score) # False

if 'music' in score: # music이 있으면 점수를 보여주고
	print(score['music'])
else:
	score['music'] = 0 # 없으면 점수를 0점으로 해서 딕션어리에 추가

5. 결론

여기서 중요하게 봐야할 점은 in 이다.

어떤 데이터를 찾을 때 O(1)의 시간복잡도로 찾는 것은 시간 복잡도를 많이 줄여준다

딕션어리는 시간복잡도를 줄이기 위해 메모리를 사용하는 것이다.