해시 테이블

박한솔·2020년 12월 6일

비트코인.
예전에도 황금알의 상징이었고 지금도 다시 언급되고 있는 떡상의 상징.

비트코인이 가상화폐로 자리를 잡았던 이유는 2가지의 암호화 과정입니다.

하나는 거래자들과의 거래를 위한 ECC(Elliptic Curve Cryptography),
다른 하나가 검증을 위한 SHA-256, 즉 해시 알고리즘입니다.

(참고 : https://earlybirdhenry.tistory.com/448 - 비트코인의 암호와 알고리즘)

해시 테이블은 키 값을 해시 함수라는 특수한 알고리즘을 통과시켜서 새로운 인덱스로 만든 다음 그 인덱스에 VALUE를 넣는 자료구조입니다.

해시 테이블의 최대 장점은 키 값을 완전히 망가뜨리므로 새로운 인덱스 값에서 역으로 원래 키 값을 찾지 못한다는 것입니다.(암호화에 최적화)

그러므로 해시 테이블은 비트 코인이나 은행의 암호화, 중복된 정보 탐색 등에 유용하게 쓰입니다.

여기까지 보면 해시 함수가 해시 테이블에서 매우 중요한(사실 거의 모든 것) 요소임을 볼 수 있습니다.

만약 해시 함수를 이렇게 쓰게 된다면 어떻게 될까요?

let hashfunction = function(key){
  let index = key.length % 10
  return index
}

이 경우 key가 'hello'이면 index는 5가 됩니다.

하지만 key가 'world'도 index는 5입니다.

이 경우에은 같은 index에 다른 값이 들어가게 되어 conflict가 일어나게 됩니다.

conflict를 방지하기 위해서(또는 해결하기 위해서) 사용하는 방법은 2가지입니다.

하나는 index=5의 값에 hello와 world가 node로 이어진 linked list를 만드는 separate chaining,

다른 하나는 world는 index = 6으로 다른 방을 찾아가는 open addressing입니다.(만약 6에도 다른 값이 있다면 7로....이렇게 빈 방을 찾아갑니다)

그럼에도 해시 함수의 conflict는 처리하기 위해서는 많은 데이터가 필요합니다.
따라서 지금도 최적화된 해시 함수를 위해서 개발자들은 열일을 하고 계십니다.

MD5 : https://en.wikipedia.org/wiki/MD5
가장 먼저 개발된 해시 함수, 간단하고 사용하기 용이합니다.

SHA-2 : https://en.wikipedia.org/wiki/SHA-2
우리나라의 인터넷 뱅킹, 비트코인은 SHA-2 시리즈 중 하나인 SHA-256을 널리 사용하고 있습니다.

치열하게, 하지만 즐겁게