Hash Function이란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
해시 함수의 특징
어떤 값을 입력해도 고정 길이의 해시를 출력한다.
입력데이터의 크기가 방대할지라도 해시결과물은 고정된 길이를 갖기 때문에, 고정 길이의 해시 길이만큼만 비교과정을 거쳐서 데이터의 변화가 발생했는지 확인할 수 있다.
눈사태 효과 : 입력값의 아주 일부를 변경했을때, 전혀 다른 결과를 출력한다.
이를 반대로 말하면, 같은 입력값에는 항상 같은 해시값을 얻을 수 있어야한다. 만약 동일 값에 대하여 다른 해시 결과값을 얻게된다면 데이터의 무결성을 검증할 수 없게된다.
눈사태효과의 특징으로, 해시를 통하여 입력값을 유추할 수 없다.
Hash Function Example
SHA-256 : SHA(Secure Hash Algorithm) 알고리즘의 한 종류로서 256비트의 해시 값을 생성하는 해시 함수이다. SHA-256은 미국의 국립표준기술연구소(NIST; National Institute of Standards and Technology)에 의해 공표된 표준 해시 알고리즘인 SHA-2 계열 중 하나이며 블록체인에서 가장 많이 채택하여 사용하고 있다.
MD5(Message-Digest algorithm 5) : 128비트의 해시 값을 생성하는 해시 함수이다. 주로 프로그램이나 파일이 원본 그대로인지를 확인하는 무결성 검사 등에 사용된다. 이전에 쓰이던 MD4를 대체하기 위해 만들어졌다. 문제점이 발견되어 추천되지않는다
Hash Collision
Hash Collision이란 서로 다른 두개의 입력값에 대하여 동일한 출력값을 내는 상황을 의미한다.
일반적인 해결론이 제시되어있다.
separate chaining : jdk 에서 사용하는 방식으로 각 bucket이 linked list 구조를 갖고 data를 이어서 저장해나간다.
Open Addressing : chaining 방법과 달리, 기존의 해쉬 공간 내에서 index에 충돌이 발생했을 때 탐색을 통해 빈 index bucket에 데이터를 저장하는 방식이다. 해쉬 테이블 내의 빈 주소를 찾아가는 방법이며, 방법에 따라 linear Probing, Quadratic Probing등 여러 방법이있다.
최초 index에 저장된 데이터가 삭제되었을 경우 충돌에 의해서 다른 곳에 저장된 데이터의 검색이 어렵다는 한계점이 있으며, 추가적인 데이터 공간을 사용하기 때문에 태생적인 한계점을 갖는다. 따라서, resizing 작업이 필요하다.
linear Probing의 경우 군집화 현상이 발생하기 때문에 해쉬의 성능을 방해할 확률이 높다.
Map? HashMap?
key : value 형태로 저장된 자료구조를 Map이라고 부른다.
key ⇒ value 를 찾는 방법에 따라서 hashMap,treeMap등의 이름이 붙는다
즉, HashMap은 key를 통해 value를 찾아가는 과정에 hash function이 적용된 Map 형태의 자료구조이다.
HashMap 의 특징
key ⇒ value 를 찾는 과정에 hash function이 사용된다.
value 값을 찾을 때 Hash Function을 한 번씩만 수행하면 되기 때무에 데이터 조회 및 저장 삭제가 빠르다는 장점이 있다.
