# TIL 웹개발 - 해시테이블

해시테이블(해시 맵)

- 키, 밸류 구조로 딕셔너리형태의 자료형

- 자료를 저장하고 검색하는데 사용하는 중요한 기법

- 좋은 해시 함수의 조건

    - 해시 함수 값 충돌의 최소화

    - 쉽고 빠른 연산

    - 해시 테이블 전체에 해시 값이 균일하게 분포

    - 사용할 키의 모든 정보를 이용하여 해싱

    - 해시 테이블 사용 효율이 높아야함

로드 팩터

해시테이블에 저장된 데이터 개수 n을 버킷의  개수 k 로 나눈 것

로드 팩터 비율에 따라 해시 함수를 재작성 할지, 크기를 조정할 지  결정한다.

로드팩터가 증가할 수록 해시 테이블 성능은 점점 감소하기에 해시테이블의 공간을 재할당한다.

해시 함수

해시 함수를 통해 키가 해시 값으로 변경되는 과정을 도식화 한 것이다.

윤아와 서현의 값은 해시 함수를 통해 동일한 2를 가지며 충동한 것을 알 수 있다.

![Image](https://upload.cafenono.com/image/slashpagePost/20240715/131142_w2d7qWotINY8qaF4X5?q=75&s=1280x180&t=outside&f=webp)

해결 방식

개별 체이닝

윤아와 서현의 해싱 함수 값이 충돌날 경우 그 뒤에 연결리스트로 붙이는 해결 방법

![Image](https://upload.cafenono.com/image/slashpagePost/20240715/131317_f2LclZdjXcAim4Ehr5?q=75&s=1280x180&t=outside&f=webp)

개별 체이닝의 원리

1. 키의 해시 값을 계산한다.

2. 해시 값을 이용해 배열의 인덱스를 구한다.

3. 같은 인덱스가 있다면 연결 리스트로 연결한다.

오픈어드레싱

충돌 발생 시 탐사를 통해 빈 공간을 찾아 나서는 방식 = 리니어 프로븍 (선형 탐사)

![Image](https://upload.cafenono.com/image/slashpagePost/20240715/131534_3G3Gvdvr8MDkRBgutr?q=75&s=1280x180&t=outside&f=webp)

클러스터링 - 선형 탐사의 경우 데이터들이 뭉치는 경향이 생기는데 이것을 클리스터링이라고 한다.

일정 이상 크기가 채워지면 리해싱한다.

![개별 체이닝과 리니어 프로빙의 차이](https://upload.cafenono.com/image/slashpagePost/20240715/125150_HaTQGQ1CopXHzI28gy?q=75&s=1280x180&t=outside&f=webp)

파이썬의 해시 테이블 구현방식

해시 테이블로 구현된 파이썬의 자료형은 딕셔너리 형태이고 오픈 어드레싱 방식으로 구현되어있다.

For the site tree, see the [root Markdown](https://slashpage.com/kyugntae-ai.md).