오늘은 룩업(빠른 읽기)에 최적화된 자료구조인 해시 테이블에 대해서 알아보자.
Hash table 에 대해 알아보기 전에,
우리는 cafe_menu 메뉴를 아래와 같이 배열로 표현할 수 있다.
cafe_menu = [["americano", 4200], ["cappucino", 4400], ["apple-juice", 5500]]
# 치즈 빵 메뉴 추가
cafe_menu.append(["cheese-bread", 3900])
print(cafe_menu)
데이터의 입력만 생각하면 직관적인 방법이라고 생각한다.
하지만 우리가 데이터를 '저장'하는 이유는 '활용'하기 위함이다.
정렬되지 않은 배열은, 데이터가 증가할수록 절망감을 가져다 주기 때문이다.
카페의 메뉴가 100개가 됐다고 하자.
- "cake의 가격을 알고싶다면?"
- "strawberry cake를 메뉴에서 삭제하고 싶다면?"
for item in cafe_menu:
if item == "strawberry cake":
pass위와 같이 데이터 N에 대한 선형검색을 해야 함을 의미한다.
데이터가 100개 밖에 없는 상황이라 문제가 없다고 말하는 사람도 있을 수 있다.
그렇다면,
데이터가 만 개, 수십 만 개 혹은 그 이상인 경우엔
프로그램의 속도에 영향을 미치게 된다.
메뉴가 정렬된 배열의 경우,
'이진검색(binary search)'라는 좋은 해결책이 있다.
검색에 대한 시간복잡도가 log(N)으로써,
'O(N)인 선형검색'보단 훨씬 좋은 알고리즘이기 때문이다.
하지만, 카페 메뉴를 생각해볼때
아메리카노는 0번이고, 카푸치노는 1번, 그리고 케이크는 1003번으로 지정하는 것 자체가 넌센스가 아닌가 싶다.
왜냐하면,
1) '아메리카노'를 달라고 요청하면
2) 그것이 배열 인덱스 0과 동일하다는 '약속'을 맺어야하고(사용자 정의)
3) 그제서야 검색을 진행하는데,
4) cafe_menu[0] = '아메리카노',
cafe_menu[1001] = '케이크' 등과 같이
1001개에 대한 '정의'를 매번 코드로 추가/수정 작업을 해야하는
한숨이 나오는 상황이 생긴다.
알고리즘 뿐만 아니라,
어떤 자료구조를 채택할지 생각해봐야 하는 순간인 것이다.
1. 해쉬 테이블이란?
Python에선,
'딕셔너리'라고 하는 이 자료구조는
'key'와 'value' 한 쌍이 하나의 값으로 구성된다.
# 딕셔너리 정의 및 선언
cafe_menu = {}
# 카페 메뉴에 "americano"라는 'key'와 4200 이라는 value 입력
cafe_menu["americano"] = 4200룩업에 대한 시간복잡도는 O(1)로써, 그 효율성은 어마무시하다.
- 물론, 배열의 인덱스로 룩업을 하는 것도 O(1)이다.
하지만,
서두에 언급했듯이, 배열의 인덱스54가 어떤 메뉴인지는
우리는 알지 못한다.
(하나하나 지정해주는 수고를 하지 않는 이상 말이다.)
2. 해쉬 테이블 예시
바로 예시를 보며 접근해보자.
('누구나 자료구조와 알고리즘'(저자 : 제이 웬그로우)
p.149에 나온 예제를 참조했다.)
전자 투표 프로그램의 코드를 생각해보자.
vote_list = []
vote_list.append("a")
vote_list.append("b")
vote_list.append("c")
vote_list.append("d")
vote_list.append("a")
vote_list.append("a")
print(vote_list)리스트의 append()메소드를 통한 데이터 입력은
중복을 포함하는 데이터 추가 방식이므로
입력시 중복검사를 할 필요가 없다.
따라서, 입력에 대한 시간복잡도는 O(1)이다.
하지만 투표가 끝나고 집계를 할 때, 문제가 된다.
def get_elected(vote_list):
for candidate in vote_list:
# 해쉬테이블 사용(지역변수)
result = dict()
#'result'라는 딕셔너리에 후보자 이름이 있으면,
if candidate in result.keys():
result[candidate] +=1
#'result'라는 딕셔너리에 후보자 없다면,
else:
result[candidate] = 1
return result
vote_list = []
vote_list.append("a")
vote_list.append("b")
vote_list.append("c")
vote_list.append("d")
vote_list.append("a")
vote_list.append("a")
result = get_elected(vote_list)
print(result)
딕셔너리(해시 테이블)을 사용해서, 투표자의 표를 취합했다.
하지만 투표가 끝난 이후에 투표수 만큼(N)의
for 문을 돌려 집계를 해야하는 비효율적인 문제가 발생한다.
- 시간복잡도 : O(N)
"집계도 입력 직후 같이 진행되면 좋겠다."
# 전역변수 선언
result = dict()
# 집계를 진행할 함수 정의
def add_votes(candidate):
if candidate in result.keys():
result[candidate] += 1
else:
result[candidate] = 1
vote_list = []
# 후보 'a'가 vote_list에 입력됨
vote_list.append("a")
# 후보 'a'를 바로 pop 시키고, 그걸 add_votes 함수에 입력(전달인자)
add_votes(vote_list.pop())
# 이하 동일
# (= 입력된 데이터를 pop 메소드로 추출 및 삭제하고, 그걸 바로 집계)
vote_list.append("b")
add_votes(vote_list.pop())
vote_list.append("c")
add_votes(vote_list.pop())
vote_list.append("d")
add_votes(vote_list.pop())
vote_list.append("a")
add_votes(vote_list.pop())
vote_list.append("a")
add_votes(vote_list.pop())
print(result)결과
말장난인 것 같아 보이지만,
데이터 입력후,
바로 집계하는 방식은 모두 시간복잡도가 O(1)이다.
- 입력 : O(1)
- 읽기 : O(1)
이러한 점에서,
해쉬 테이블 자료구조는 읽기와 삽입이라는 면에서 강력한 도구다.
- One step at a time - 