해시 - hash

Contents

<!> 제대로 살펴봐야 겠다는 생각이 마구 들고 있다. Hash 함수는 임의의 길이를 가지는 데이터를 고정된 길이의 데이터로 맵핑하는 알고리즘이다. 해쉬 함수는 Hash(k) = V 로 표현할 수 있다. 함수 hash()에 K를 입력하면, 값 V가 출력된다. 이때 K가 같으면 항상 같은 V가 출력된다.

아래 그림은 해싱의 기본 개념을 묘사하고 있다.

해쉬 함수는 매우 큰 범위의 입력 데이터를 hash 함수를 이용해서, 고정된 크기의 디지털 데이터에 맵핑하기 위한 목적으로 사용한다. 어떤 해싱함수를 사용하느냐에 따라서 다양한 응용이 가능하다.

많은 양의 데이터에서 데이터의 위치를 빠르게 찾기 위해서 사용한다. Hash 함수에 key를 넣으면, 값 v를 리턴하는데, 이 v를 인덱스(index)로 해서 key에 대한 값이 저장된 위치를 찾는식이다.

크기가 4인 해시 테이블이 있다. 이 해시 테이블을 관리하는 해시함수 Hash(k)에 key를 입력하면, 해시 테이블에 있는 값들 중 하나를 반환한다. 이 반환 값은 실제 k가 저장된 위치에 대한 색인이다.

하드디스크와 같은 느린 미디어에 저장된 대량의 데이터에서 원하는 데이터를 빠르게 읽기 위해서 일반적으로 Cache를 사용한다.

ARP(Address Resolution Protocol)이 캐시를 이용해서 성능을 올리는 대표적인 예다. ARP는 로컬네트워크 상에서 IP에 대한 MAC 주소를 찾기 위해서 사용하는 프로토콜이다. 로컬 네트워크에서 데이터 통신을 하기 위해서는 IP에 대한 MAC 주소가 일치해야 하기 때문에, 운영체제는 ARP를 이용해서 상대편 컴퓨터의 MAC과 IP 주소를 먼저 수집한다. arp 명령을 이용하면, 이러한 방법으로 수집한 ARP 테이블을 확인할 수 있다.(ARP 주소는 수정했다.) 이 정보를 통신을 할 때마다 수집하는 것은 매우 비효율 적이다. 네트워킹을 위해 사용하는 매체는 매우 느리기 때문이다. 해서 운영체제는 수집한 ARP 정보를 상대적으로 빠른 로컬 메모리에 저장해서 사용한다. 그리고 수정되는 정보만 갱신한다.

Cache는 웹 서비스의 성능을 올리기 위해서도 널리 사용한다. 어떤 데이터(예를 들어 웹 문서)가 디스크에 저장돼 있다면, 자주 읽는 문서를 메모리에 캐시해서 속도를 높이는 식이다. 이 경우 모든 (비용 등 여러 가지 문제로)데이터를 메모리에 올릴 수 없기 때문에, 자주 접근하는 데이터를 Cache에 올리기 마련이다. 그렇다면 유저가 어떤 데이터를 요청했을 때, 그 데이터가 캐시에 있는지를 빠르게 찾아야 하는데, 이때 해시를 이용할 수 있다.

보안이 필요한 정보에 대한 유일한 확인을 위해서 해시 값을 사용할 수 있다. 해시 함수는 같은 입력에 대해서는 항상 같은 출력이 나온다. 만약 데이터가 변조 됐다면, 다른 해쉬 값이 나올테고, 원래 해쉬값과 비교하는 것으로 데이터 변조 여부를 확인할 수 있다.

문제는 서로 다른 데이터들에 대해서 같은 해쉬 값이 나올(해쉬 값 충돌 - collision) 확률이 존재한다는 거다. 이 문제는 근본적으로 해결 할 수 없고, 해쉬 값을 크게 해서 확률을 낮추는 방향으로 해결하고 있다. 암호화에 널리 사용하는 SHA-1도 해쉬 함수로 구현한다.

중복(거의 동일한)데이터를 찾는데 사용할 수 있다. 예컨데, 대량의 오디오 파일에서 비슷한 소리를 찾는다거나, 대량의 문서파일에서 비슷한 문서를 찾는 애플리케이션의 개발이 가능하다.

consistent hash 참고