[파이썬 알고리즘 인터뷰] 해시 테이블

• 해시 테이블(해시 맵): 키를 값(해시)에 매핑할 수 있는 구조인, 연관 배열 ADT를 구현하는 자료구조
  • 대부분의 연산이 분할 상환 분석에 따라 시간 복잡도가 O(1)
• 해시 함수: 임의 크기 데이터를 고정 크기 값(해시)으로 매핑하는 데 사용할 수 있는 함수
  • 해시 함수가 값을 매핑할 때 충돌을 최소화하는 것이 무엇보다 중요함
• 로드 팩터: 해시 테이블에 저장된 데이터 개수를 버킷의 개수로 나눈 것
• 해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것
• 개별 체이닝: 충돌 발생 시 연결리스트로 연결
• 오픈 어드레싱: 충돌 방생 시 탐사를 통해 빈 공간을 찾는 방식
  • 전체 슬롯 개수 이상 저장 불가, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음
  • 데이터들이 고르지 않고 뭉치는 경향이 있다
  • 일정 이상 데이터가 채워지면 더 큰 버킷을 생성하고 리해싱
• 파이썬에서 해시 테이블로 구현된 딕셔너리는 오픈 어드레싱으로 성능을 높이고, 로드 팩터를 작게 잡음

 

706. design hashmap

- defaultdict로 초기화하고 연결리스트에 데이터 저장

- 개별 체이닝으로 충돌 처리

 

771. jewels and stones

- 해시 테이블

- defaultdict

- Counter

- 리스트 컴프리헨션(true = 1)

* 리스트 컴프리헨션에서 [] 없애면 제네레이터

 

3. longest substring without repeating characters

- 슬라이딩윈도우, 투포인터

- 딕셔너리

 

347. top K frequent elements

- 힙

- Counter

* zip()

* 아스테리스크(*): 튜플 또는 리스트 등의 시퀀스 언패킹, **: 키/갑 페어 언패킹 (함수의 인자일 때는 패킹) (변수 할당)