[해시 테이블]

해시 테이블 또는 해시 맵은 키를 값에 매핑 할 수 있는 구조인, 연관 배열 추산 자료형을 구현하는 자료 구조이다.

[해시]

해시 함수랑 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용 할 수 있는 함수를 말한다.

해시 테이블의 핵심은 해시 함수다. 입력값은 ABC, 1324BC, AF32B로 각각 3글자, 6글자, 5글자 이지만 화살표로 표시한 특정 함수를 통과하면 2바이트의 고정 크기 값으로 매핑이 된다.

[성능 좋은 해시 합수들의 특징]

1)해시 함수 값 충돌의 최소화

2)쉽고 빠른 연산

3)해시 테이블 전체에 새시 값이 균일하게 분포

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

5)해시 테이블 사용 효율이 높을 것

[비둘기집 원리]

비둘기집 원리란, n개 아이템을 m개 컨테이너에 넣을 때, n>m이라면 적어도 하나의 컨터이네에는 반드시 2개 이상의 아이템이 들어 있다는 원리를 말한다.

[로드 팩터]

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

load factor=(n/k)