해시 데이터 구조 - 해시, 해시 함수, 해시 테이블

해시와 해시 함수

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

해시 함수는 이 해시를 실행하려고 하나의 값을 다른 값으로 변환하는 함수다

해시 함수의 동작

해시 함수는 데이터를 입력하면 해시값을 출력한다

해시 함수의 특징은 입력되는 데이터가 문자든 문자열이든 기호든 출력되는 해시값의 길이가 항상 고정된다

해시 함수는 서로 다른 입력 2개가 같은 해시값을 생성할 가능성도 있다

이때 해시 충돌이 발생한다

해시 함수가 잘 정의되었으면 내부 연산이 빠르고 충돌 발생이 적다

해시 테이블

해시 테이블은 해싱(해시 테이블을 이용하는 탐색)할 때 사용한다

해시 테이블은 키와 값으로 구성된 검색 시스템이다

해시 테이블에는 모든 키에 대응하는 값이 있다

이러한 데이터 구성은 검색 수행 속도를 크게 증가시킨다

보통 문자열인 키를 해시 함수에 입력하면 저장을 위한 데이터 구조의 인덱스에 매핑된 해시값이 생성된다

생성된 해시값을 사용하면 테이블에서 검색이나 추가하려는 요소가 저장된 배열의 인덱스를 계산할 수 있다

3개의 문자열 STR0, STR1, STR2가 있고 해시 함수는 각 문자열을 입력 받아 배열의 인덱스에 매핑한다

각 문자열은 해시 함수에 입력하여 인덱스와 키-값을 생성해 완성된 해시 테이블은 다음과 같다

체이닝

위 방식은 해시값과 배열 크기 때문에 해시 충돌이 발생할 수 있다

해시 충돌의 발생을 방지하기 위해 체이닝 방식으로 해시 테이블을 구현한다

체이닝은 요소를 배열이 아닌 연결 리스트로 저장하는 방식이다

테이블의 각 인덱스에 할당된 것은 값이 아니라 키와 값을 가진 연결 리스트다

이 구조는 해시 충돌을 해결하는 데 도움이 된다

단 체이닝을 사용하면 연결 리스트가 길어졌을 때 해시 테이블 검색의 시간 복잡도가 증가할 가능성이 있다

순환 중복 검사

마이크로컨트롤러 시스템에서는 해싱을 사용하여 동작하는 순환 중복 검사(CRC) 모듈이 있다

CRC는 디지털 데이터의 오류를 감지하는 방식으로, 해시 함수의 원리를 사용하여 데이터의 유효성을 검증한다

해시 함수를 통해 고정된 비트 수의 체크섬을 찾아 발신할 데이터에 첨부하는 방식으로 동작한다

수신자는 전송된 데이터를 가지고 다항식 나눗셈의 나머지를 계산해 데이터의 오류를 확인한다

수신 데이터의 CRC가 발신 데이터의 CRC와 일치하지 않는다면 데이터가 손상되었을 가능성이 크다

해시의 용도

검색 엔진, 컴파일러, 데이터베이스 등 많은 양의 복잡한 검색 연산에는 많은 시간이 필요하며 소요 시간이 성능에 큰 영향을 준다

해시 테이블의 시간 복잡도는 O(1)이다

많은 양의 복잡한 검색 연산을 수행하는 응용프로그램에서 최대한 처리 시간이 빠르도록 설계하는 것이 적합하고 이는 해시를 적용하기 좋은 조건이다