해시함수

문자열 또는 숫자로 된 키를 배열에서 사용되는 유효한 인덱스, 작은 숫자로 바꿔주는데 사용된다.

좋은 해시 함수의 조건

1. 빠른 연산 속도: 해시 함수는 O(1) 시간 복잡도로 동작해야 한다.
2. 균등한 분배: 키를 해시 테이블의 모든 인덱스에 균일하게 분배해야 충돌을 줄일 수 있다.
3. 결정론적 특성: 같은 입력 값에 대해 항상 같은 해시 값을 반환해야 한다.

키

: 해시함수를 통해 고유한 해시값으로 변환

• 문자열 혹은 정수 형태
• 저장된 데이터를 빠르게 찾기 위해 사용되는 고유 식별자
• 해시함수에 전달되어 처리 → 특정 위치에 값을 저장하거나 검색할 수 있음

해시테이블

: 키(key)와 값(value) 형태의 데이터 구조

자바스크립트의 경우 Object나 Map을 사용해서 해시 테이블을 구현할 수 있다.

• 해시 테이블의 키는 순서를 갖지 않음
• 고유한 해시 값을 계산하여 해시 인덱스로 결정 → 해당 인덱스에 값을 저장

참고) 해시 충돌

해시 테이블에서는 서로 다른 키가 동일한 해시 값을 가지는 충돌(Collision) 문제가 발생할 수 있다.

개별 체이닝

• 배열, 연결 리스트등을 사용하여 이중 데이터 구조를 쓰는 방법이다.
• 즉 공동 저장 방식이다.
• 충돌이 발생해도 동일한 인덱스에 추가 데이터를 저장할 수 있다.

선형 탐색법

• 각 위치에 하나의 데이터만 저장한다는 규칙을 지키는 방식이다.
• 충돌이 발생하면 다음 빈칸을 찾아 저장한다.
• 해시 테이블이 꽉 차면 성능이 저하될 수 있다.