파이썬 해시테이블
해시테이블 관련 leet 문제
(박상길님의 ‘파이썬 알고리즘 인터뷰’ 책 참고)
해시 테이블
키를 값에 매핑할 수 있는 구조
해시테이블은 1953년 IBM에 근무하던 한스 피터 룬이 사내 메모에서 해싱과 체이닝을 결합하여 처음 사용한 것으로 알려져 있으며, 지금까지도 현대 컴퓨터 프로그래밍 언어에서 유용하게 사용되는 매우 중요한 자료구조이다.
출처: 파이썬 알고리즘 인터퓨(박상길 저)
해싱
- 해시함수: 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수
- 해싱: 해시테이블을 인덱싱하기 위해 해시 함수를 사용하는 것. 정보를 가능한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나다.
- 성능 좋은 해시 함수들의 특징
→ 해시 함수 값 충돌의 최소화
→ 쉽고 빠른 연산
→ 해시 테이블 전체에 해시 값이 균일하게 분포
→ 사용할 키의 모든 정보를 이용하여 해싱
→ 해시 테이블 사용 효율이 높을 것 - 생각해볼 문제: 생일 문제, 비둘기집 원리, 로드 팩터(해시 테이블의 크기를 조정해야 할지를 결정하는 지표)
- 자바 JDK의 해시 함수에서는 31(메르센 소수)을 이용하여 해시함수를 구현한다.
충돌
아무리 좋은 해시함수라도 충돌은 발생하게 된다.
- 개별 체이닝
- 오픈 어드레싱 → 클러스터링 문제
해시 테이블로 구현된 파이썬의 자료형 = 딕셔너리
체이닝시 malloc으로 메모리를 할당하는 오버헤드가 높아 파이썬 딕셔너리를 오픈 어드레싱을 택했다. (CPython 구현)
→ 오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋다. 그러나 슬롯의 전체 개수 이상, 즉 로드 팩터 1 이상은 저장할 수 없다. 그리고 공간이 찰 수록 탐사에 점점 더 오랜 시간이 걸린다.
시간 복잡도
- 대부분의 탐색은 O(1), 최악의 경우 O(n) : 하나의 key에 값이 몰린 경우
HashTable은 프로그래머의 기본기
해시 테이블에 대한 재밌는 영상이 있어서, 영상 링크와 함께 영상 내용도 함께 적어보았다.
- 컴퓨터 동작에 대한 기본적인 이해가 자료구조, 알고리즘 구현 능력에서 나타난다.
컴퓨터에서 재현되는 모든 것은 결국에는 이진수, 숫자로 나타내게 된다.
Opcode와 같은 low level 부터 모든 데이터는 이진수 숫자에 대한 의미를 어떻게 지정하느냐에 따라 데이터의 해석이 다르다. - HashMap은 이런 디지털 데이터의 특성을 잘 나타낸 자료구조이다. O(1)으로 접근 가능한 JumpTable을 표현한 것으로, Key, Value를 어떻게 mapping할 것인지가 포인트다. 오브젝트를 다 비교하면 어려우니까, 시그니처에 대해 해시값만 비교하여 유니크한 정수값인 Key 값을 만드는 것이 해시 알고리즘의 핵심이다. 이 알고리즘이 해시 테이블의 성능을 좌우한다.
해시 테이블 구현 방법
