해시
💡 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑
- 해시 함수: 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다.
- 해시 테이블: 키와 값을 매핑해둔 데이터 구조이다. 해시 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장하여 효율적인 검색을 위해 사용된다.
1-1. 해시 순서
해당 원소의 해시 함수를 이용하여 해시값을 얻는다.
해시값을 주소로 하는 위치에 원소를 저장한다.
저장 후 검색 시에도 원소의 해시값으로 계산하여 해당 위치로 이동한다.
1-2. 사용 용도
- 무결성 검사: 파일 다운로드 시 문제가 없는지 확인하는 용도로 다운로드하는 파일이 일부라도 변경된 경우 Checksum 값이 크게 달라진다.
예시 : WebStrom 다운로드 파일 체크섬 확인하여 일치하는지 볼 수 있다. WebStrom에서 제공하는 해시 값과 일치하면 정상적으로 다운된 것을 알 수 있다. - DB 비밀번호 저장
- 해시 테이블 사용
Direct Addressing Table
먼저 가장 간단한 형태의 해시테이블로 이름 뜻대로 키 값을 주소로 사용하는 테이블을 말한다. 크기가 U인 테이블 T를 생성하고 key k를 slot key에 저장하는 방식이다. 해당 테이블은 중복되는 키가 없다고 가정한다. 이는 삽입, 삭제, 검색 모두 O(1)이지만, 모든 키를 넣어야 하기 때문에 공간 낭비가 심하다. 예를 들어 모든 학생들에게 한 자리씩 할당해 준 것이다.
이러한 형태의 테이블은 키 값들이 골고루 분포되어있지 않다면 메모리 낭비가 심할 수밖에 없다. 또한 최대 키값이 작을 때 실용적으로 사용된다. 이러한 공간 낭비 문제로 Hash Table를 사용하게된다.
Hash Table
key k를 저장할 때 slot k를 저장하는 것이 아니라 slot h(k)에 저장한다. key k가 slot h(k)로 해시되었다고 하며, h(k)를 key k의 해시값이라고 부른다. 이때 h( )는 해시 함수라고 부른다.
Hash Table은 Direct Addressing Table와 다르게 U 만큼의 테이블을 생성하지 않아도 되어 공간 낭비는 줄인다. 그러나 충돌 문제가 있다. 아래 그림에서는 h(k2) = h(k5) 부분이 충돌이 났다.
시간 복잡도는 삽입, 삭제, 검색 모두 O(1)이다.
충돌
두 개의 다른 key가 동일한 hash 값을 갖는 경우 "충돌이 발생했다"라고 한다. 충돌을 피하는 방법은 충돌이 적은 좋은 해시 함수를 사용하는 것이다. 아래에서 충돌을 해결하기 위한 Chaining과 Open Addressing 두 가지 방법을 알아보자.
해시 충돌 해결 방법
1. Chaining
💡 충돌 시 연결 리스트에 추가하는 방식이다.
중복된 해시 값이 있는 경우, 해당 슬롯을 연결 리스트로 저장한다. 이 방법은 연결 리스트로 인해 최악의 경우 수행 시간이 O(n)이 된다. 해시를 사용하는 이유는 O(1)이라는 장점으로 사용하는 것인데 O(n)이 된다면 문제가 된다. 이런 문제로 트리로 구성하여 더 시간 복잡도를 줄일 수도 있다.
2. Open Addressing
💡 충돌 발생 시 해시함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장한다.
오픈 어드레싱은 충돌을 피하기 위한 다른 방법으로 key를 해시 테이블에 직접 저장한다. 오픈 어드레싱의 장점은 포인터를 사용하지 않아도 되어 구현이 간편하며, 검색도 미세하게 빨라진다.
