해시 테이블

= 파이썬의 딕셔너리!!!

-> 딕셔너리는 충돌 시, Open Addressing 방식으로 구현되어 있다!

• 해시테이블 대부분 연산은 시간복잡도가 O(1)임

  • 따라서 데이터 수에 상관없이 빠른 성능 기대
    
    (이미지출처)

• 해시 함수란, 가장 큰 특징은 어떤 데이터라도 똑같이 고정된 크기 값으로 매핑하는데 사용하는 함수

  • 예를들어
  • ABC -> A1
  • 1234BC -> DA
  • AF32B -> Q4

• 해시 특징

  • 해시 함수 결과값들의 충돌 최소화
  • 쉽고 빠른 연산(O(1))
  • 해시 테이블 전체에 해시값이 균일하게 분포
  • 사용할 키의 모든 정보를 이용해 해싱
  • 해시 테이블 사용 효율이 높음

• 해시테이블 간단 원리

  • 키의 해시값을 계산한다
  • 해시값을 이용해 배열의 인덱스를 구한다
  • 같은 인덱스(해시값)이 나오면 링크드 리스트로 엮어준다
    - 체이닝 방식
    - 충돌이 많이 발생할 수 있음
    - 충돌이 발생해도 무한정 저장 가능 (링크드리스트니까)
    
    (이미지출처)

• 해시테이블은 기본적으로 대부분의 연산이 O(1)이지만

  • 동일한 해시값을 갖는 애들이 발생할 경우
  • "충돌"이 일어나는 경우, 최악은 O(n)이 될 수도 있다.

• 충돌이 발생할 경우 해결법 1

  • 오픈 어드레싱 (open addressing)
  • 충돌 발생 시 빈 공간을 찾아나가는 방법
  • 문제점 : 정해진 개수를 초과하여 저장할 수 없음
    
    (이미지출처)

• 파이썬의 딕셔너리는 충돌 시 체이닝 vs 오픈 어드레싱

  • 답 : 오픈어드레싱
  • 이유
    • 체이닝을 사용할 경우 연결 리스트를 만들기 위한 추가 메모리 할당이 필요하고
    • 추가 메모리 할당은 상대적으로 느린 작업이기 때문
  • 부록 A에서 면접관이 잘못 알고있는 경우 대처 방안을 소개하니까 읽어볼것