[자료구조/알고리즘] 해시 테이블

📌 해시테이블이란?

키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형(ADT)을 구현하는 자료구조로 시간 복잡도가 O(1)로 빠른 성능을 지니고 있다.

 

• 해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것

 

• 로드팩터
  • 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것, 키들을 잘 분산해 주는지 효율성 측정에도 사용
  • 로드 팩터 비율에 따라 해시 함수를 재작성해야 될지 해시 테이블의 크기를 조정해야 할지 결정한다.
  • 자바 0.75 파이썬 0.66 루비 0.5

        → 일반적으로 로드 팩터가 증가할수록 성능 감소, 로드 팩터를 넘어설 경우 동적 배열처럼 해시 테이블 공간 재할당

 

---

 

충돌 해결 방법

 

1. 개별 체이닝

 

• 충돌 발생 시 연결 리스트로 연결
• 보통 O(1)이지만 해시 충돌이 모두 발생하면 시간복잡도는 O(n)이 됨

 

 

 

 

2. 오픈 어드레싱

 

• 충돌 발생 시 빈 공간을 찾음
• 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음

 

 

 

 

 

 

---

 

 

파이썬의 경우 해시 테이블 형태의 자료형인 딕셔너리는 

체이닝은 메모리를 할당하는 오버헤드가 높아서 오픈 어드레싱 방식으로 구현되어 있다. (자바는 개별 체이닝 방식)

오픈 어드레싱이 성능이 더 좋지만 로드팩터가 0.8 이상일 때 급격히 성능저하가 일어나기 때문에 로드 팩터를 작게 잡아 성능 저하 문제를 해결한다.

 

 

 

 

 

참고 및 출처: 파이썬 알고리즘 인터뷰