유저의 비밀번호, 전자서명, 전자투표와 같은 민감한 입력의 무결성을 검증하거나, 혹은 문서 복제 등을 체크하거나 블록체인에도 사용되는 해시 테이블 개념을 정리해본다.
🚘 Hash Table
Hash Table(Hash map)이란 해시함수를 사용해서 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조를 말한다.
다시말해 해시 테이블은 어떤 특정 값을 받아서 해시 함수에 입력하고, 함수의 출력값을 인덱스로 삼아 데이터를 저장한다.
파이썬의 dictionary, 루비의 hash, 자바의 map이 hash table의 대표적인 예이다.
해시 테이블의 특징은 아래와 같다.
- 기본 연산으로는 search, insert, delete가 있다.
- 순차적으로 데이터를 저장하지 않는다.
- key를 통해서 value를 얻을 수 있다. => 이진탐색트리나 배열에 비해서 속도가 획지적으로 빠름.
- 커다란 데이터를 해시해서 짧은 길이로 축약할 수 있기 때문에 데이터를 비교할 때 효율적이다.
- value는 중복 가능하지만 key는 유니크해야 한다.
- 수정가능하다.(=> mutable)
- 보통 배열로 미리 hash table 사이즈만큼 생성 후에 사용한다.
해시 테이블은 key-value가 1:1매핑되어 있기 떄문에 검색, 삽입, 삭제 과정에서 모두 평균적으로 O(1)의 시간복잡도를 갖는다.
공간 복잡도는 O(N)인데 여기서 N은 키의 개수다.
🚘 Hash table time complexity in Big O notation
Hash Table의 시간 복잡도
| Algorithm | Average | Worst case |
|---|---|---|
| space | O(n) | O(n) |
| search | O(n) | O(n) |
| insert | O(n) | O(n) |
| delete | O(n) | O(n) |
| 연산 | Big-O |
|---|---|
| 삽입(Insertion) | 평균 O(1), 최악 O(N) |
| 검색(Search) | 평균 O(1), 최악 O(N) |
| 삭제(Deletion) | 평균 O(1), 최악 O(N) |
해시란 단방향 암호화 기법으로 해시 함수를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미한다.
이때 매핑 전 원래 데이터의 값을 key, 매핑 후 데이터의 값을 hash value, 매핑하는 과정을 hashing이라고 한다.
해시 함수를 이용해서 key를 hash value로 매핑하고, 이 hash value를 index로 삼아 데이터의 value를 buckets(혹은 slots)에 저장했다.
🚘 해시 함수
해시함수의 간단한 예로 나눗셈을 한번 보자.
어떠한 정수를 10으로 나눈 나머지를 return하는 함수가 있다.
무조건 0 ~ 9사이의 값이 리턴되기 때문에 이 또한 간단한 해시 함수이다.
즉, 해시 함수는 임의의 길이를 갖는 메시지를 입력받아서 고정된 길이의 해시값을 출력하는 함수다. 어떤 입력값에도 항상 고정된 길이(해시 함수에 따라 비슷한 길이까지 포함)의 해시값을 출력한다.
해시 함수를 통해 입력값은 완전히 새로운 모습의 데이터로 만들어지기 때문에 암호화 영역에서 아주 주요하게 사용되고 있다.
SHA(Secure Hash Algorithm)알고리즘이 그 대표적인 예시다.
또한, 입력 값의 일부가 변경되면 전혀 다른 값을 출력하는데 이것을 가리켜 '눈사태 효과'라고 한다.
이 눈사태 효과로 결과값은 입력값을 유추할 수가 없다. 역추적이 안된다는 말은 '단방향'으로만 되어 있다는 의미를 내포한다.
👳♀️ 대표적인 해시함수
해시함수는 키의 유무에 따라서 두 가지 종류로 분류한다. 키가 없는 MDC와 키가 있는 MAC로 분류한다.
MDC(Modification Detection Cryptography)는 무결성 검증으로 패스워드의 암호화 등에 사용하며 MDC의 대표적인 알고리즘으로는 MD5, SHA(SHA-1, SHA-256, SHA-512, SHA-3), LSH 등이 있다.
MAC(Message Authentication Cryptography)은 무결성 검증과 더불어 메시지의 출처 확인 용도로 사용하며 MAC의 대표적인 알고리즘으로는 H-MAC, CBC-MAC이 있다.
하지만 이 해시 함수에도 단점이 존재하는데, 해시 함수는 입력값의 길이가 어떻든 고정된 길이의 값을 출력하기 때문에 입력값이 다르더라도 같은 결과값이 나오는 경우가 있다.
이것을 '해시 충돌' Hash collision이라고 표현하며, 충돌이 적은 해시 함수가 좋은 해시함수다.
👳♀️ 해시 충돌
ARGOS와 MINIBEEF가 값은 해시 값을 가지며 충돌이 발생했다.
해시 충돌을 설명하기 위해서는 적재율(load factor)라는 개념이 필요하다.
적재율이란 해시 테이블의 크기에 대한 키의 개수의 비율을 뜻한다. 즉 키의 개수를 K, Hash Table의 size를 N이라고 했을때 적재율은 K/N이다.
만약 충돌이 발생하지 않을 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 실행되지만, 충돌이 발생할 경우에는 탐색과 삭제 연산이 O(K)만큼 걸리게 된다.
해시 충돌이 완전하게 없는 해시 함수를 만드는 것은 불가능하다. 따라서 해시 충돌에 대해 안전하다는 해시함수는 '충돌을 찾는 게 거의 희박하다'라는 뜻이다.
이 해시 충돌이 발생하는 근본적인 원인은 비둘기집 원리로, 해시 함수에 입력할 수 있는 데이터의 가짓수가 무한하지만 출력으로 나올 수 있는 해시 값이 유한하기 때문이다.
☁️ [해시 충돌 원인]
- 해시 함수는 다양한 입력값을 고정된 크기의 해시 값으로 매핑하기 때문에 발생한다.
- 해시 테이블의 크기보다 키의 개수가 더 많아서 두 개의 키가 동일한 슬롯에 해싱되는 경우 발생한다.
☁️ [해시 충돌의 문제점]
- 클러스터링(연속된 레코드에 데이터가 몰리는 현상)이나 오버플로우(버킷에 할당된 슬롯 수보다 많이 할당이 되어 더 이상 넣지 못하는 경우)가 발생한다.
- 해시 테이블의 성능을 저하시키는 주요 원인 중 하나로, 해시 충돌이 발생하면, 해시 테이블의 탐색 시간이 길어진다.
☁️ [해시 함수의 충돌 저항성]
- 해시 함수의 충돌 저항성은 같은 해시 값을 가진 다른 두 원문을 유추할 수 없다는 것을 의미한다.
- 해시(X) = Hash(X')를 만족하는 임의의 두 입력값 X, X'를 찾는 것이 계산적으로 불가능해야 한다.
☁️ [해시 충돌 해결 방법]
- 자바에서는 linkedList를 이용한 'chaing'방식을 통해 해결할 수 있다.
- 충돌의 완화하는 방법으로 개방 주소법(open addressing)등이 있다.
- 해시 충돌이 발생하면 해시 테이블의 충돌을 완화해야 한다.
🚘 javascript HashMap
자바스크립트에서 해시테이블은 Map, Object, Set이 있다.
본래 자바스크립트에서 해시테이블 자료구조는 Object가 대표적이었으나, ES6에서 Map과 Set이 추가되었다고 한다.
대표적으로 해시맵이라고도 불리는 Map에 대해 정리해 보려 한다.
👳♀️ Map 객체
Map 객체는 key-value로 이루어진 해시테이블이다.
set(): key-value pair를 map에 삽입
get(): key값으로 value를 찾아 리턴
key에 들어갈 수 있는 자료형은 number, string, function, object, NaN 등이 가능하다.
☁️ Map 객체 생성
var map = new Map(); ☁️ Map에 key-value 쌍 데이터 삽입: set(key, value)
let number = 0;
let str = 'string';
let obj = { a: 1 };
let func = () => {
console.log('func');
};
map.set(number, 4); //key에 number 가능
map.set(str, 1); // key에 string 가능
map.set(obj, 2); //key에 object 가능
map.set(func, 3); // key에 함수 가능
map.set(number, 0); // 덮어쓰기 가능
console.log(map); // Map(4) {0 => 0, "string" => 1, {…} => 2, ƒunc => 3}☁️ key로 value값 반환: get(key)
map.get(str); // 1
map.get(obj); // 2
map.get('none'); // undefined
map.get({ a: 1 }); // undefined, obj !== { a: 1 }☁️ map에 해당 key의 value 존재 여부: has(key)
map.has(str); // true
map.has(obj); // true
map.has('none'); // false ☁️ map의 크기: map.size()
map.size // 4
map.length // undefined☁️ map 탐색
//key, value 쌍으로 출력
for (let [key, value] of map) {
console.log(key + ' = ' + value)
}
//key만 출력
for (let key of map.keys()) {
console.log(key)
}
//value만 출력
for (let value of map.values()) {
console.log(value)
}