코합되 / Chapter 09 해시 / 자바스크립트는 객체 깡패다.

해시

• 키와 값을 1:1 저장해서 빠른 데이터 탐색을 제공
• 단방향으로 동작(값으로 키를 왜 찾아) 
• O(1) -> 탐색 과정이 필요 없음

 

활용분야

• 특정 데이터를 탐색하는 횟수가 많을 경우 사용
• 비밀번호 관리
• 데이터베이스 인덱싱
• 블록 체인

 

해시함수

• 자스에선 오브젝트라는 자료형으로 구현 가능

 

고려사항

1. 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 됨. 
2. 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 함(동일한 결과값이 적게 나오게)

 

자주 사용하는 해시 함수

1. 나눗셈 법 : 키를 소수로 모듈러 연한 함. 
2. 곱셈법 
3. 문자열 해싱

 

충돌 처리

1. 체이닝
2. 개방 주소법