💡코드 없는 알고리즘과 데이터 구조을 바탕으로 작성된 글입니다.

해시 데이터 구조

해시와 해시 함수

해시

어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것.

해시 함수

해시를 실행하려고 하나의 값을 다른 값으로 변환하는 상자.

💡여기서 변환된 다른 값을 해시 값(hash value)라고 한다.

해시 함수는 데이터를 입력하면, 일련의 16진수를 출력한다.

• 입력되는 데이터가 어떤 값이든 출력되는 해시 값의 길이는 항상 고정되어 있다.

해시 충돌

해시 함수는 일반 함수와 다르다. 일반 함수는 입력 값에 대응하는 출력 값이 정확하게 하나에만 대응되지만, 해시 함수는 서로 다른 입력 값을 가진 2개가 같은 해시 값을 생성할 가능성도 있다. 이때를 해시 충돌이 발생했다고 한다.

☝️다만 해시 함수는 입력 데이터의 비트 하나만 달려져도 출력되는 해시 값이 완벽하게 달라지므로 해시 충돌은 흔하지 않은 일이다.
해시 함수를 잘 정의하면 내부 연산이 빠르고 충돌 발생도 적어진다.

해시 테이블

키와 값으로 구성된 데이터를 저장하는 자료구조로 배열과 연결 리스트를 기반으로 만들어졌다. 해시 함수를 사용해 검색을 수행한다.

💡 해시 테이블에는 모든 키에 대응하는 값이 있기 때문에 키를 알면 연결된 값을 즉시 찾을 수 있어 시간 복잡도 O(1)를 가진다.

해시 테이블은 데이터의 키를 해시 함수에 입력하여, 그 결과로 나오는 해시 값을 인덱스로 사용하여 데이터를 저장한다.

체이닝(chaining)

해시 값과 배열의 크기때문에 해시 충돌이 발생하는 경우가 있다. 이런 상황을 방지하기 위해 체이닝 방식으로 해시 테이블을 구현한다.

체이닝은 해시 테이블의 요소들을 단순한 배열이 아닌 연결 리스트인 배열에 저장하는 방식이다. 해시 함수가 여러 요소에 대해 똑같은 인덱스를 반환하면, 해시값과 해당 요소들을 함께 연결하여 해시 테이블의 같은 인덱스에 저장한다.

데이터를 검색할 때에는 먼저 해당 데이터의 인덱스를 구한 후, 인덱스에 해당하는 연결 리스트에서 해당 데이터와 일치하는 해시 값을 찾는다.