자료구조 기초 - 해시 데이터 구조

해시

 어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것. 컴퓨터 보안 영역에서 주로 사용된다.

 

해시 함수

 해시를 실행하려고 하나의 값을 다른 값으로 변환하는 함수. 해시 함수는 데이터를 입력하면 해시값을 출력한다.

 해시 함수는 입력되는 데이터가 무엇이든 출력되는 해시값의 길이가 항상 고정되어 있다.

 

해시 충돌

 서로 다른 입력 2개가 같은 해시값을 생성할 가능성도 조금 있다. 이때 해시 충돌이 발생한다.

 해시 함수는 입력 데이터의 비트 하나만 달라져도 출력되는 해시값이 매우 많이 달라지므로 해시 충돌은 흔치 않다.

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

 

해시 테이블

 해싱(해시 테이블을 이용하는 탐색)할 때 사용하며, 키와 값으로 구성된 검색 시스템이다. 해시 테이블에는 모든 키에

 대응하는 값이 있다. 이러한 데이터 구성은 검색 수행 속도를 크게 증가시킨다.

 해시 테이블에서 요소를 검색할 때의 시간 복잡도는 O(1)이다.  각 키는 값 하나와 연결되어 있으므로 키를 알면 연결된 

 값을 즉시 찾을 수 있다..

 

 해시 테이블은 해시 함수를 사용해 검색을 수행한다. 보통 문자열인 키를 해시 함수에 입력하면 저장을 위한 데이터 구조

 (기본적으로 배열)의 인덱스에 매핑된 해시값이 생성된다. 즉, 생성된 해시값을 사용하면 테이블에서 검색이나

 추가하려는 요소가 저장된 배열의 인덱스를 계산할 수 있다.

 이 방식은 해시값과 배열 크기 대문에 해시 충돌이 발생할 수 있어 방지를 위해 체이닝(Chaining)이라는 방식으로

 해시 테이블을 구현한다.

 

체이닝

 체이닝은 요소를 단순한 배열이 아닌 연결 리스트인 배열에 저장하는 방식이다.

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

 즉, 해시 함수가 여러 요소에 대해 똑같은 인덱스를 반환하면, 해시값과 해당 요소들을 함께 연결하여 해시 테이블의 같은

 인덱스에 저장한다.

 

 이 구조는 어떤 인덱스의 검색을 요청했을 때 에러를 발생시키지 않고 연결 리스트를 검색해서 원하는 데이터를 찾을 수

 있어 해시 충돌을 해결하는데 도움이 된다. 단, 체이닝을 사용하면 연결 리스트가 길어졌을 때 해시 테이블 검색의 시간

 복잡도가 증가할 가능성이 있다.

 

해싱과 암호화

 암호화는 정보를 암호화하고 암호화된 정보를 복구하는 것(복호화) 모두를 포함한다. 반면 해싱은 데이터를 입력받아 고정 길이의 출력을 생성하며, 이후에는 원래의 데이터가 필요하지 않다. 양방향 과정인 암호화와 달리 해싱은 단방향 과정이다.

보안을 위한 디지털 서명은 RSA(Rivest-Shamir-Adleman)와 DSA(Digital Signature Algorithm)이다. 두 방식 모두 보안을 보장하기 위해 해시를 사용한다. RSA 방식의 디지털 서명 과정에서는 암호화하기 전의 데이터에 해시 함수를 사용하고, DSA 방식의 디지털 서명 과정에서는 SHA(Secure Hash Algorithm)기반의 암호화 해시 함수를 사용한다.

해시는 단방향의 1대1 함수이므로 비밀번호를 사용하는 보안에 적합하다.

이 외에 컴퓨터 보안 분야에서 해시는 난수 생성, 메세지 인증코드(MAC), 단방향 함수 등에 사용된다.

 

순환 중복 검사(Cyclic Redundanch Check, CRC)

 마이크로컨트롤러를 내장한 임베디드 시스템에는 해싱을 사용하여 동작하는 순환 중복 검사 모듈(CRC)이 있다.

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

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

 데이터를 가지고 다항식 나눗셈의 나머지를 계산해 데이터으 오류를 확인한다. 수신 데이터의 CRC와 발신 데이터의 

 CRC가 일치하지 않는다면 데이터가 손상되었을 가능성이 크다. CRC 모듈은 이더넷과 와이파이를 통해 디지털 데이터를

 전송하는 임베디드 시스템에서 널리 사용되고 있다.

 

 검색엔진, 컴파일러, 데이터베이스 등 많은 양의 복잡한 검색 연산을 수행해야한다. 검색 연산에는 많은 시간이 필요하며 

 소요 시간이 성능에 큰 영향을 주기 때문에 연결 리스트와 같은 일반적인 데이터 구조로는 검색 연산을 보조할 수 없다.

 일정한 시간 내에 수행될 연산이 필요할 때 해시 테이블의 시간 복잡도는 O(1)이기 때문에 많은 양의 복잡한 검색 연산을

 수행하는 응용 프로그램에는 최대한 처리 시간이 빠르도록 설계할 수 있는 해시가 유용하다.