파이썬 알고리즘 인터뷰: 11장 해시 테이블
2258 단어 datastructurealgorithmalgorithm
해시 테이블
해시 함수
임의 크기 데이터를 고정 크기 값으로 매핑 하는 데 사용할 수 있는 함수
ABC -> A1
1324BC -> CB
AF32B -> D5
- 위 입력값의 길이가 각각 3,6,5로 다르지만, 화살표에 해당하는 해시 함수를 통과하면 2바이트의 고정 크기 값으로 매핑됨.
해시 함수 활용 분야
- 심볼 테이블, 체크섬, 손실 압축, 무작위화 함수, 암호 등
성능 좋은 해시 함수들 특징
- 해시 함수 값 충돌의 초소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시 테이블 사용 효율이 높음
생일 문제
- 생일이 같은 2명이 존재할 확률은 23명만 모여도 50%를 넘고, 57명이 모이면 그때부터는 99퍼를 넘음 ↔ 비둘기집 원리
로드 팩터
해시 테이블에 저장된 데이터 개수 n을 버킷 k로 나눈 것
- 자바 10은 0.75, 파이썬은 0.5
클러스터링
선형 탐사시 해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 현상
- 탐사 시간이 이 걸리는 것이 아닌가?
해시 테이블 충돌 해결
개별 체이닝
- 충돌 발생 시 연결 리스트로 연결
- 데이터의 개수가 많아지면 레드-블랙 트리에 저장하는 형태로 병행해 사용하기도 함
오픈 어드레싱
- 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식
- 전체 슬롯의 개수 이상은 저장할 수 없음
- 충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아 해결
- 기준이 되는 로드 팩터 비율을 넘어서게 되면, 그로스 팩터의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업 일어남
- 동적 배열에서 공간이 가득 찰 경우, 더블링으로 새롭게 복사해서 옮겨가는 과정과 유사
파이썬의 해시 테이블 충돌 해결
임의 크기 데이터를 고정 크기 값으로 매핑 하는 데 사용할 수 있는 함수
ABC -> A1
1324BC -> CB
AF32B -> D5
해시 테이블에 저장된 데이터 개수 n을 버킷 k로 나눈 것
선형 탐사시 해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 현상
- 동적 배열에서 공간이 가득 찰 경우, 더블링으로 새롭게 복사해서 옮겨가는 과정과 유사
→ 오픈 어드레싱 방식
- 체이닝 시 malloc으로 메모리를 할당하는 오버헤드가 높아 오픈 어드레싱을 택했다
- 연결 리스트를 만들기 위해서는 추가 메모리 할당이 추가하고, 추가 메모리 할당은 상대적으로 느린 작업이기 때문에 택하지 않음
- 선형 탐사는 로드 팩터 비율이 높아질수록 조회당 평균 캐시 실패가 높아지는 문제가 있어 파이썬은 로드팩터를 자바(0.75)에 비해 작게 잡음(0.66)
Author And Source
이 문제에 관하여(파이썬 알고리즘 인터뷰: 11장 해시 테이블), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@taekkim/파이썬-알고리즘-인터뷰-11장-해시-테이블저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)