해시의 개념
큰 데이터 베이스에서 특정 데이터를 찾는다고 했을 때, 가장 확실하고 쉽게 떠올릴 수있는 방법은 처음부터 끝까지 순차 탐색하는 방법입니다. 이 방법을 사용하면 가장 확실하게 원하는 데이터를 찾을 수 있습니다. 하지만 최악의 경우에 모든 데이터를 비교해야되기 때문에 효율이 떨어지는 방법입니다. 이 방법을 개선하기 위해 어떠한 값이 저장되는 위치를 규정할 수 있다면 순차탐색 없이 바로 데이터를 찾아낼 수 있을 것입니다.
해시
해시는 해시 함수를 사용해 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조입니다. 해시는 key를 활용해 빠른 데이터 탐색을 가능하게 합니다.
값 value : 얻고자 하는 정보
키 key : 검색을 위해 활용하는 정보
해시함수 : 키를 이용해 해시값 또는 인덱스로 변환하는 함수
해시 테이블 : 키와 대응한 겂이 저장되어 있는 공간
버킷 : 해시 테이블의 각 데이터
키 자체가 해시 함수에 의해 값이 있는 인덱스가 됨으로 탐색 과정이 필요 없습니다.
해시는 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색 가능
해시의 특성을 활용한 분야
비밀관리 관리 : 사용자의 비밀번호를 노출해 저장하는 것은 보안의 문제가 있으므로, 해싱한 비밀번호를 저장, 비밀번호 확인도 마찬가지 입니다.
데이터베이스 인뎅싱 : 데이터베이스에 저장된 데이터를 효율적으로 검색
블록체인 : 각 블록은 이전 블록의 해시값을 포함 -> 데이터 무결성을 확인
자바스크립트에서의 구현
자바스크립트에는 오브젝트라는 자료형을 제공하는데, 오브젝트는 해시와 거의 동일하게 동작
해시 함수가 반환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안됨
충돌: 서로다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 경우
해시 함수 구현법
나눗셈법(모듈러 연산) : 키를 소수로 나눈 나머지를 활용 ( 7 % 2 = 1 )
곱셈법 : 나눗셈법의 단점인 큰 소수를 사용해야 하는 경우를 보완하기 위해 사용, h(x)=(((xA) mod m ) A는 황금비(무한소수)
문자열 해싱 : 키의 자료형이 문자열 일때, 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱
충돌 처리
서로 다른 키에 대해서 해시 함수의 결괏값이 같으면 충돌이 발생
체이닝으로 처리 : 충돌이 발생하면 해당 버킷에 연결 리스트로 같은 해시값을 가지는 데이터를 연결
장점 : 단순한 방법
단점 : 해시테이블 공간 활용성이 떨어짐 , 검색 성능이 떨어짐
개방 주소법으로 처리 : 충돌이 발생하면 빈 버킷을 찾아 충돌값을 삽입
선형탐사방식 : 다른 빈 버킷을 찾을 때까지 일정간격으로 이동 (주로 1)
이중 해싱 : 해시 함수를 2이상 사용,
