해시테이블 기초개념 요약 및 Python 프로그래밍 구현연습

ㅇ 학습 시 참고한 도서정보

• 제목 : Hello Coding 그림으로 개념을 이해하는 알고리즘
• 저자&출판사 : 아디트야 바르가바 지음, 김도형 옮김 / 한빛미디어

해시테이블

• 해시 테이블은 사전을 구현하는 가장 효율적인 자료구조이다.

• 이론적으로는 해시 테이블에서 원소를 찾는 것이 연결 리스트에서 원소를 찾는 것 (O(n)) 만큼 오래 걸릴 수 있지만, 실제 해싱은 성능이 탁월하다.

• 일반적으로 해시 테이블에서 원소를 찾는 데 걸리는 수행시간은 O(1)이다.

• 해시 테이블은 단순한 표현인 배열을 일반화 한 것이다.

• 일반적인 배열에 대한 직접 번지화 방법은 배열의 임의의 위치를 O(1)안에 접근하게 하는 효율적인 방법이다.

• 해시테이블의 핵심

헤시테이블은 속도가 빠르고 여러가지로 모형화가 가능한 강력한 자료구조이다.

1. 헤시테이블은 해시함수와 배열을 결합해서 만든다.

   • 해시함수 : string을 입력했을때 숫자를 반환하는 함수. 보통 파이썬에서는 딕셔너리를 활용한다.

2. 충돌은 나쁜현상이다. 충돌을 줄이는 해시함수가 있어야한다. 하지만 우리가 고민할 깊이는 아니다.

3. 헤시테이블은 정말 빠른 탐색,삽입,삭제 속도를 가진다.

4. 헤시 테이블은 어떤 항목과 다른 항목의 관계를 모형화 하는데 좋다.

5. 헤시테이블의 사용률이 0.7보다 커지면 헤시테이블을 리사이징할 때다.

6. 헤시테이블은 (웹서버 등에서) 데이터를 캐싱하는데도 사용된다.
   • 서버에게 작업을 시키지 않고 자료를 캐싱할 수 있다.
   • 모든 대형 웹 사이트는 캐싱을 사용한다. 그리고 그 자료는 헤시테이블에 저장된다.
7. 헤시테이블 중복을 잡아내는데도 뛰어나다.

• 예시) 투표소에서 투표하는 사람을 관리해보자

voted = {}

def check_voter(name):
    if voted.get(name):
        print("kick them out!")
    else:
        voted[name] = True
        print("let them vote!")

check_voter("tom")
print(voted)
check_voter("mike")
print(voted)
check_voter("mike")

let them vote!
{'tom': True}
let them vote!
{'tom': True, 'mike': True}
kick them out!