이게 뭐냐 하면 hashtag(#) 모양으로 생긴 table일 것이다.라고 유추했는데 맞는지 확인해봐야겠다.
전혀 아니었다. 해시테이블이라는 자료구조를 알아보기전에 해시(hash)라는 것에 대해 먼저 알아보는 시간을 가지자.
해시넷이라는 사이트에서는 이렇게 정의를 내리고 있다.
해시(hash)란
다양한 길이를 가진 데이터
를고정된 길이를 가진 데이터로 매핑(mapping)
한 값이다.
그래서 이게 뭔 쌉소린가 싶기는 한데(솔직히 해시계가 먼저 생각났다.), 쉽게 말하고자 하면 이렇다. 어떤 값(key)를 받아서 이걸 hashingfunction(해시함수)에 집어넣어서 어떤 알고리즘에 의해서 뚝딱하고 같은 길이의 데이터
로 변환된다는 말이다. 결국엔 이렇게 만들어진 값이 해시코드(hash code), 혹은 해시값(hash value)이라고 부르는 것이다. 단방향 암호화 기법의 일종인데, 이게 또 단방향 암호화라는 말을 꺼내니까 새삼 파고들기 무서워진다. 일단 이해한 이야기를 그림으로 나타내보자.
자 그럼 이제 해시함수가 뭔지 알았다. 실제로 내가 구현할 수는 없겠지만, 어떤 값을 가지고 최종적으로 통일된 포맷의 어떠한 결과물을 내는 것. 그리고 그 결과물을 가지고 원래 넣었던 input
을 가지고 뚝딱뚝딱해서 동일한 길이의무슨 값(해시코드)
을 만들어내는 것이다.
- 입력 값이 일부만 변경되어도 전혀 다른 해시값을 출력한다. = 이걸 눈사태 효과라고 부른단다.
- 입력값 상관없이 고정된 길이의 해시값을 출력한다.
- 복호화 불가능하다. [단방향 암호화 기법 - 암호화는 되는데, 복호화는 안됨]
- 복잡하지 않은 알고리즘으로 구현되기 때문에 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모한다.
- 같은 입력값에 대해서는 같은 출력값을 항상 보장한다.
위 그림에 나와있는 것과 동일한 내용이다. 암호화 기법이므로, 동일 input에 대해선 같은 해시값을 내야하고 다른 input에 대해서는 해시값이 완전 달라야 한다. 복호화가 불가능하고, 알고리즘 자체는 가볍게 짜여지는 모양이다.
MD-5 (Message-Digest algorithm 5)
- 임의의 길이를 입력받아 128bit 길이의 해시값을 출력한다.
- 단방향 알고리즘
- 현재는 심각한 보안문제로 인하여 MD5를 보안 관련 용도로 사용하지 않는다.
- 2008년에는 MD5의 결함을 이용해 SSL 인증서를 변조하는 것이 발견되었다.
해시함수의 가장 큰 특징은 입력값이 일부만 변경되도 완전 다른 값이 나오는 함수다. 이러한 특징으로 인해, 해시함수를 사용하는 목적은 메시지의 오류나 변조를 탐지할 수 있는 무결성이다. 이 기술을 사용하는 대표적인 예는 블록체인이라고 한다. 그 외에 비밀번호, 전자서명, 전자투표, 전자상거래 등에서 사용된다.
위에서 본 것처럼 해시함수는 암호화하는 과정에도 쓰인다는 것을 알았는데, 해시함수가 포함된 해시테이블이라는 것은 다른 것을 떠나서 일단은 해시값을 이용한 자료구조
라는 것이다.
이거보다가 갑자기 희소배열 공부하고싶어서 떠남
지옥의 해시테이블