해시테이블

• 해시테이블은 키를 활용해 값에 직접 접근이 가능한 구조
• 해싱의 목적: 검색(즉, 해시테이블은 검색알고리즘 역할도 한다)
• 해싱의 장점: 데이터 양에 영향을 덜 받으며 성능이 빠름
• 해시테이블은 검색 역할, 딕셔너리를 위한 자료구조 역할도 함
• 해시함수는 여러 키를 분할하기 위해 키를 해시값(정수값)으로 매칭시키는 역할
• 해싱은 쉽게 말해서 다 흩뜨려놓고 키와 매칭되는 값을 검색하는 과정

해시함수

• 입력값의 형태는 다양하고 출력값의 형태는 숫자
• 해시함수 조건
  • 해시함수는 입력값이 같다면 동일한 출력값을 받아야함
  • 해시함수는 특정 범위안에 있는 숫자를 반환해야함
• 하나의 해시함수가 입력 데이터별로 다른 숫자와 매핑된다면 그것은 완벽한 해시함수
• 해시함수가 입력데이터에 따라 다른 숫자를 반환하게 되면 해시충돌을 최소화
• 입력값: 문자열, 출력값: 정수형
• 정수형에서 문자열로 변환하기 위해서, 해시함수는 문자열에 해당하는 개별적인 단어를 활용

해시충돌

• 해시충돌은 키가 들어갈 자기가 없는 경우에 발생

체이닝, Chaining

• 해시 테이블에서 동일한 해시값에 대해 충돌이 일어나면, 그 위치에 있던 버킷에 키값을 뒤이어 연결
• 데이터 형태는 연결리스트의 형태
• 체이닝의 원리

1. 키의 해시값 계산
2. 해시값을 이용해 리스트의 인덱스를 구함
3. 같은 해시값이 있다면(충돌한다면) 리스트로 연결

• 충돌을 줄이기 위해 각 리스트에 대해 연결(리스트형태)하도록 한다
  (따라서, 충동 발생해도 체이닝을 통해 값을 찾을 수 있음)
• 체이닝으로 충돌상황을 재현하고 해결하는 모습을 구현할 수 있음
• 체이닝은 연결리스트의 원리를 사용해서 해시값이 같은 노드를 연결하는 모습을 가짐
• 해시값은 인덱스 역할도 함

오픈어드레싱, open addressing

• 다른 로직의 함수를 활용하기때문에 open address
• 비어있는 배열 슬롯이 발견될 때까지 array의 위치를 검색하여 해시 충돌을 해결
• 충돌이 일어나는 경우, 탐사를 진행하면서 빈공간을 찾아야 해결
  (체이닝과 달리 저장공간 정해짐)
• 해시테이블로 구현된 자료형은?=>딕셔너리
• 체이닝의 경우 연결리스트를 활용하고 오픈 어드레싱은 내부적으로 공간이 어느정도 정해진 배열을 활용하여 설계됨
• 파이썬의 경우 내부적으로 오픈 어드레싱 방식을 활용
• 오픈 어드레싱 활용할때 빈 공간이 없으면 시간이 오래 걸릴 수 있어서 로드팩터를 작게 설정하여 성능 저하 문제를 해결
• 로드 팩터 비율에 따라 해시함수 재작성여부, 해시테이블 크기조정여부가 결정됨

놓은 해시함수란

• 키, 값 계산과정이 쉬워야함
• 충돌을 피할 수 있어야함