TIL 웹개발 - 해시테이블
서경태
해시테이블(해시 맵)
•
키, 밸류 구조로 딕셔너리형태의 자료형
•
자료를 저장하고 검색하는데 사용하는 중요한 기법
•
좋은 해시 함수의 조건
◦
해시 함수 값 충돌의 최소화
◦
쉽고 빠른 연산
◦
해시 테이블 전체에 해시 값이 균일하게 분포
◦
사용할 키의 모든 정보를 이용하여 해싱
◦
해시 테이블 사용 효율이 높아야함
로드 팩터
해시테이블에 저장된 데이터 개수 n을 버킷의 개수 k 로 나눈 것
로드 팩터 비율에 따라 해시 함수를 재작성 할지, 크기를 조정할 지 결정한다.
로드팩터가 증가할 수록 해시 테이블 성능은 점점 감소하기에 해시테이블의 공간을 재할당한다.
해시 함수
해시 함수를 통해 키가 해시 값으로 변경되는 과정을 도식화 한 것이다.
윤아와 서현의 값은 해시 함수를 통해 동일한 2를 가지며 충동한 것을 알 수 있다.
해결 방식
개별 체이닝
윤아와 서현의 해싱 함수 값이 충돌날 경우 그 뒤에 연결리스트로 붙이는 해결 방법
개별 체이닝의 원리
1.
키의 해시 값을 계산한다.
2.
해시 값을 이용해 배열의 인덱스를 구한다.
3.
같은 인덱스가 있다면 연결 리스트로 연결한다.
오픈어드레싱
충돌 발생 시 탐사를 통해 빈 공간을 찾아 나서는 방식 = 리니어 프로븍 (선형 탐사)
클러스터링 - 선형 탐사의 경우 데이터들이 뭉치는 경향이 생기는데 이것을 클리스터링이라고 한다.
일정 이상 크기가 채워지면 리해싱한다.
개별 체이닝과 리니어 프로빙의 차이
파이썬의 해시 테이블 구현방식
해시 테이블로 구현된 파이썬의 자료형은 딕셔너리 형태이고 오픈 어드레싱 방식으로 구현되어있다.
Subscribe to 'kyugntae-ai'
Subscribe to my site to be the first to receive notifications and emails about the latest updates, including new posts.
Join Slashpage and subscribe to 'kyugntae-ai'!
Join Slashpage and subscribe to 'kyugntae-ai'!
Subscribe
