해시
- 임의의 크기를 갖는 데이터(key)를 고정된 크기의 데이터(value)로 변화시켜 저장하는 것
- 키에 대한 해시값을 구하는 과정을 해싱(hashing)이라고 하며 이때 사용하는 함수를 해시 함수라고 한다.
- 해시 값 자체를 index로 사용하기 때문에 평균 시간 복잡도가 O(1)로 매우 빠르다
해시 함수
- 임의의 길이의 데이터를 입력받아 일정한 길이의 배열로 데이터를 매핑시키는 함수
- 계산이 복잡하지 않고 키값에 대해 중복없이 해시값을 고르게 만들어주는 함수가 좋은 함수이다.
해시 테이블
- 배열을 이용해 데이터를 key와 value로 저장하는 자료구조
충돌
- 서로 다른 키(key)가 같은 해시코드를 갖는 경우 충돌(collision)이라고 한다. 이 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
- 이를 해결하기 위해 LinkedList, Tree등을 사용할 수 있다.
- 충돌이 일어날 때 추가적인 메모리 공간을 사용하지 않기 위해 open addressing을 사용할 수 있다.(인덱스가 중복되어 충돌이 발생할 때 비어있는 해시값의 공간에 데이터를 할당한다)
과정
- 키값을 입력받아 해시 알고리즘을 통해 해시코드를 만든다.
- 해시코드를 해시 테이블의 크기로 나누어 공간을 할당한다.
키(key) -> 해시 함수(hash function) -> 해시값(hash value)
<이름> -> <해싱 과정> -> <index(hash value):data>
장점
- 데이터 액세스(삽입, 삭제, 탐색)시 시간 복잡도가 O(1)을 지향한다.(연산이 빠르다)
- 해시 함수는 언제나 동일한 해시값을 반환하고, 해당 index만 알면 해시 테이블의 크기에 상관없이 데이터에 빠르게 접근할 수 있다
- index를 해시값으로 사용하므로 모든 데이터를 탐색하지 않고 원하는 값을 삽입, 삭제, 탐색할 수 있다.
- 해시 충돌이라는 발생 가능성이 있지만, 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
- 하드디스크, 클라우드에 존재하는 매우 많은 데이터들을 유한한 개수의 해시값으로 매핑하면서 작은 크기의 메모리로 프로세스를 관리할 수 있다.
단점
- 충돌이 많이 일어난다면 공간 복잡도가 증가하고 시간 복잡도도 O(n)에 가까워진다.
.