해시
데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하고, 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.
해시함수란?
해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 한다.
해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다.
해시 테이블이란?
해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블(hash table)이라고 한다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 하며, 해시테이블의 기본 연산은 삽입, 삭제, 탐색(search)이다.
해시 테이블 장점
해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는
- 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 된다.
- 색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있다.
- 해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적이다. 다시 말해 해시는 데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 𝑂(1)을 지향한다.
충돌 문제 해결
- 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)
- Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)
- 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피
- 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함
출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Hash.md
