파이썬 알고리즘 인터뷰 해시 테이블 간단 정리

해시 테이블

• 해시 테이블 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형을 구현하는 자료구조 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)
  • 해시 함수 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수 키 값으로 레코드가 저장되어 있는 주소(혹은 색인)을 산출하는 함수
    • 성능 좋은 해시 함수 해시 함수 값 충돌의 최소화 쉽고 빠른 연산 해시 테이블 전체에 해시 값이 균일하게 분포 사용할 키의 모든 정보를 이용하여 해싱 해시 테이블 사용 효율이 높음
  • 해싱 해시 테이블을 인덱싱 하기 위해 해시 함수를 사용하는 것 최적의 검색이 필요한 분야에 사용됨
  • 충돌 데이터를 key 로 간소화하는 과정에서 다른 내용의 데이터가 같은 키를 갖는 경우
    • 비둘기집 원리 n 개의 아이템을 m 개 컨테이너에 넣을 때, n>m 이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리
    • 개별 체이닝 충돌 발생 시 연결 리스트로 연결하는 방식 키의 해시 값을 계산한 후 해시 값을 이용해 배열의 인덱스를 구한 뒤 같은 인덱스가 있다면 연결 리스트로 연결함
    • 오픈 어드레싱 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식 전체 슬롯의 개수 이상은 저장할 수 없음 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장되는다는 보장 없음 해시 테이블에 저장되는 데이터들이 고르게 분포하지 않고 뭉치는 경향 있음
      • 클러스터링 해시 테이블 여기저기에 연속도딘 데이터 그룹이 생기는 현상 탐사 시간을 오래 걸리게 하며, 전체적으로 해싱 효율을 떨어뜨리는 원인이 됨
      • 리해싱 로드 팩터 비율을 넘게 되면 그로스 팩터의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 작업
  • 로드 팩터 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것 비율에 따라 해시 함수를 재작성할지, 해시 테이블의 크기를 조정해야 할 지 결정
  • Python 에서의 해시 테이블 딕셔너리가 해시 테이블로 구현되어 있음 충돌 시 체이닝은 malloc 으로 메모리 할당하는 오버헤드가 높아 오픈 어드레싱 사용 슬롯의 80% 이상이 차게 되면 급격한 성능 저하가 일어나기 때문에 로드 팩터를 적게 잡아 성능 문제 해결
• zip 함수 2 개 이상의 시퀸스를 짧은 길이를 기준으로 일대일 대응하는 새로운 튜플 시퀸스를 만드는 역할 실제값 추출이나 값을 변경하기 위해서는 list 로 묶어서 해결
• 아스테리스크(*) 시퀸스를 풀어 해치는 시퀸스 언패킹 연산자 함수의 파라미터가 되었을 때 반대로 패킹도 가능 변수의 할당 시 나머지 모든 값을 취하게 됨 두개 사용 시 키/값 페어를 언패킹하는 데 사용됨