해시(Hash)
해시는 key-value를 쌍으로 데이터를 저장하는 자료구조이다. Space-Time trade off(시간-공간)의 대표적인 알고리즘에 속한다.
Space-Time trade off(시간-공간)
기존의 배열과 다른 별도의 리스트 공간을 만들어 빠른 알고리즘을 구현하는 방법. 즉 시간을 빠르게 하기 위해서 많은 공간을 사용하는 알고리즘이다. 기수 정렬, 해시, B-tree 등이 이 방식을 사용한다.
key 값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어나게 된다.
특정 데이터가 저장되는 인덱스가 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 삽입과 삭제 시 데이터의 이동이 없도록 만들어진 구조이다.
해시의 사용 용도
해시는 주로 해시 테이블, 암호화, 데이터 축약 등에 사용된다.
해시 테이블
해시테이블은 데이터를 입력받아 해시함수를 사용하여 주소를 만들고 그 주소에 데이터를 담는 방식으로 작동한다.
해시 함수
해시 테이블을 만들 때 인덱스로 사용할 고유한 숫자값을 만드는 함수.
해시 함수를 구하는 방법
1. 나눗셈법(division method)
숫자로 된 키를 해시 테이블의 크기 m으로 나눈 나머지를 해시값으로 변환하는 방법
간단하면서 빠른 연산이 장점이다.
주소 = 입력값 % 테이블 크기
일반적으로 나눗셈법으로 해시 함수를 구현할 때 테이블의 크기를 소수(Prime Number)로 정하는 것이 좋다고 알려져 있다.
2. 자릿수 접기(digit folding)
나눗셈법은 충돌을 일으킬 가능성이 높기 때문에 충돌이 일어날 가능성을 줄인 자릿수 접기 방법을 사용하기도 한다.
자릿수 접기는 종이를 접듯이 숫자를 일정한 크기 이하의 수로 만드는 방법이다.
7891242 = 7+8+9+1+2+4+2
78+91+24+2 = 195
위와 같이 각 자릿수를 더해 해시 값을 만드는 방법을 말한다. 문자열의 경우 각 요소를 아스키코드로 바꾸고 이 값들을 각각 더해서 접으면 문자열을 해시 테이블 내의 주소로 바꿀 수 있다.
충돌
해시 함수가 서로 다른 입력값에 대해 동일한 해시 테이블 주소를 반환하는 것을 말한다. 충돌을 해결하는 방법에는 크게 두 가지가 있다.
해시 함수에서 충돌 처리 방법
1. 개별 체이닝
해당 인덱스에 값이 있으면 그 뒤에 중첩해서 연결시키는 방법이다. 개별 체이닝을 사용하면 테이블의 길이보다 더 많은 데이터를 저장할 수 있다.
체이닝의 경우 최악의 경우 한 버킷에 모든 데이터가 들어 있어 시간복잡도가 O(n)이 될 수 있다.
2. 선형 탐색
해시 함수가 반환한 주소에 이미 다른 데이터가 있을 때, 자리가 있으면 데이터를 다음 주소로 이동하며 비어 있는 주소에 입력하는 방식이다.
만약 모든 주소에 데이터가 있을 경우 해시 테이블을 늘리는 리사이징을 진행한 후에 다시 입력한다.
선형 탐색법은 최대 테이블의 길이만큼만 저장할 수 있다.
해시의 시간 복잡도
데이터를 검색할 때 key와 value가 한 쌍으로 존재하고, key 값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)이 된다.
자바스크립트에서 해시 테이블 구현하기
해시 함수 생성
function hashStringToInt(s, tableSize) {
let hash = 17;
for (let i = 0; i < s.length; i++) {
hash = (13 * hash * s.charCodeAt(i)) % tableSize;
}
return hash;
}- 키로 들어온 문자열(s)를 반복문을 돌면서 하나씩 charCode로 변환한다.
- hash에 17을 할당한 것은 효율적인 키 분산을 위해서이다.
charCodeAt() 메서드는 주어진 인덱스에 대한 UTF-16 코드를 나타내는 0부터 65535 사이의 정수를 반환합니다.
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
해시 테이블 생성
class HashTable {
table = new Array(71);
//key, value를 받아 테이블에 넣어주는 메서드
setItem = (key, value) => {
//해시 함수가 반환하는 해시 값이 인덱스가 된다.
const idx = hashStringToInt(key, this.table.length);
//해당 인덱스에 할당
this.table[idx] = value;
};
//key를 받아 해당하는 값을 불러오는 메서드
getItem = (key) => {
const idx = hashStringToInt(key, this.table.length);
return this.table[idx];
};
}const myTable = new HashTable();
myTable.setItem('firstName', 'k');
myTable.getItem('firstName');
console.log(myTable.getItem('firstName')); //k
해시 맵
Map 객체
키와 값의 쌍으로 이루어진 데이터 구조
객체와의 차이점
| 구분 | 객체 | Map 객체 |
|---|---|---|
| 키로 사용할 수 있는 값 | 문자열 또는 심벌 값 | 객체를 포함한 모든 값 |
| 이터러블 | X | O |
| 요소 개수 확인 | Object.keys(obj).length | map.size() |
- Map 객체는 이터러블이므로 for...of 문으로 순회가 가능하다.
Map을 사용하여 해시맵 구현
//생성
const hashMap = new Map();
//요소 취득
hashMap.set('1',700);
hashMap.set('2',[1,2,3]);
console.log(hashMap); //Map(2) {'1' => 700, '2' => Array(3)}
//값 얻기
hashMap.get('1');
//요소 존재 여부 확인
hashMap.has('1'); //boolean
//요소 탐색
for (let [key,value] of hashMap) {
console.log(key + ' = ' + value)
}
//요소 삭제
hashMap.delete('1'); //boolean
//요소 일괄 삭제
hashMap.clear(); //undefined 반환
참고
https://dbehdrhs.tistory.com/70
https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
https://www.geeksforgeeks.org/hashing-data-structure/
https://eunjinii.tistory.com/87
