CS) 해시 테이블(Hash table) - 실사용과 최적화
해시 테이블로 데이터 조직
해시 테이블은 데이터를 쌍으로 저장하므로 데이터를 조직하는 많은 시나리오에 유용하다.
어떤 데이터는 본래 쌍 형태다. 식당의 메뉴나, 사전 같은 경우가 대표적이다.
메뉴에는 각 음식의 이름과 그 가격이 한 쌍으로, 사전에는 단어와 그 뜻이 한 쌍으로 되어있다.
실제로 파이썬에서는 해시 테이블을 dictionary라고 부르는데, 사전이야 말로 단어와 각각의 정의가 쌍으로 나열된 일반적인 데이터 형태이기 때문이다.
선거를 가정하고, 후보자와 각 득표수 같은 집계 데이터 역시 쌍으로 되어있다.
{"CandidateA" => 145024, "CandidateB" => 442034}각 품목의 재고를 기록하는 재고 관리 시스템 역시 쌍으로 되어있다.
{"Shirt" => 402, "Jeans" => 34}심지어 어떤 경우에는 해시 테이블로 조건부 로직을 간소화할 수도 있다.
일반적인 HTTP 상태 코드 번호의 의미를 반환하는 다음과 같은 함수가 있다.
function httpStatusCodeMeaning(num) {
switch(num){
case 200:
return 'Ok';
case 301:
return 'Moved Permanently';
case 401:
return 'Unauthorized';
case 404:
return 'Not Found';
case 500:
return 'Internal Server Error';
default:
return 'Unknown http status code';
}
}위 코드를 가만히 보면 조건부 로직에서 쌍으로 된 데이터, 즉 상태 코드 번호와 각각의 의미를 처리하고 있다.
위 코드는 해시 테이블로 완전히 대체가 가능하다.
STATUS_CODES = {
200: 'Ok',
301: 'Moved Permanently',
401: 'Unauthorized',
404: 'Not Found',
500: 'Internal Server Error'
};
function httpStatusCodeMeaning(num) {
return STATUS_CODES[num] || 'Unknown http status code';
}해시 테이블로 속도 올리기
해시 테이블은 쌍으로 된 데이터와 완벽하게 들어 맞지만 쌍이 아닌 데이터라도 코드를 빠르게 만들 때 쓰일 수 있다.
다음은 간단한 배열이다
const arr = [61,30,91,11,54,38,72];위 볘얼에서 어떤 수를 찾으려면 정렬되지 않은 배열이기에 선형 검색을 수행하므로 O(N)단계가 소요된다.
하지만 어떤 코드를 실행해 수 배열을 다음과 같은 해시 테아블로 변환하면 어떨까?
const hashTable = new Map({61 : 61, 30 : 30, 91 : 91, 11 : 11, 54 : 54, 38 : 38, 72 : 72})각 수로 키를 저장해서 연관된 값에 boolean값으로 true를 할당했다.
해시테이블은 키로 값을 찾을 때 O(1)의 단계가 소요된다.
만약 arr배열에서 54를 찾으려면 5번의 이동과 5번의 검색이 필요하다.
arr.indexOf(54)하지만 해시 테이블에서는 단 1단계만으로도 룩업할 수 있다.
hashTable[72]마법이 느껴지는가?
배열을 해시 테이블로 변환하면 O(N)의 검색이, O(1)의 검색으로 바뀐다.
해시 테이블을 이러한 용도로 사용할 경우, 한 가지 흥미로운 점이 있다.
해시 테이블은 주로 본래 쌍으로 된 데이터에 쓰이는데 여기서 데이터는 쌍이 아니다. 수 리스트를 처리할뿐이다.
책 뒤에 나오는 인덱스를 보면 어떤 주제를 찾으려고 모든 페이지를 뒤적일 필요 없이 그 주제가 책의 어디에 나오는지 알게 된다.
예제에서도 마찬가지로 해시 테이블이 인덱스 역할을 했다.
인덱스는 어떤 항목이 원래 배열에 있는지 알려 준다.
이 기법을 사용해 실제 많이 쓰이는 알고리즘의 속도를 올려 보자.
알고리즘 속도에 도움이 되는 해시테이블 예제
1. 배열 부분 집합
한 배열이 다른 배열의 부분 집합인지 알아내야 한다.
예를 들어 다음 두 배열을 보자
const arr1 = ["a","b","c","d","e","f"];
const arr2 = ["b","d","f"]두 번째 배열의 모든 값이 첫 번째 배열에 있으므로 두 번째 배열인 ["b","d","f"]는 첫 번째 배열의 부분 집합이다.
하지만 배열이
const arr3 = ["a","b","c","d","e","f"];
const arr4 = ["b","d","f","h"];두 번째 배열의 원소 h는 첫 번째 배열에 없으므로 두 번째 배열은 첫 번째 배열의 부분 집합이 아니다.
두 배열을 비교해 한 쪽이 다른 한쪽의 부분 집합인지 알려주는 함수는 어떻게 작성할까?
(두 배열 중 작은 길이의 배열이 큰 길이의 배열에 완전히 속하는 경우)
한 가지 방법은 중첩 루프다.
기본적으로 더 작은 배열의 원소를 모두 순회하며 더 작은 배열의 각 원소에 더해 큰 배열의 각 원소를 순회하는 두 번째 루프를 시작한다.
작을 배열의 원소가 큰 배열에 없으면 함수는 false를 반환한다.
루프를 끝까지 통과하면 작은 배열의 값이 모두 큰 배열에 있었다는 뜻이니 true를 반환한다.
function isSubset(arr1, arr2){
let largeArray;
let smallArray
if(arr1.length > arr2.length){
largeArray = arr1;
smallArray = arr2;
} else {
largeArray = arr2;
smallArray = arr1;
}
for(let i = 0; i < smallArray.length; i++) {
if(!largeArray.includes(smallArray[i])){
return false;
}
}
}위 알고리즘의 효율성을 분석해보면 길이가 서로 다른 배열 2개가 N으로 입력되어 첫번째 배열 항목수에 두 번쨰 배열 항목 수를 곱한 만큼 실행되므로 O(N * M)이다.
이제 해시테이블의 힘을 활용해 위 알고리즘의 효율성을 개선해보자.
원래 방식을 버리고 처음부터 다시 시작하자.
새 방식에서는 어느 배열이 더 작고 큰지 알아낸 후 큰 배열을 순회하는 루프 하나만 실행해 해시 테이블에 각 값을 저장한다.
let hashTable = {};
for(const value of largeArray) {
hashTable[value] = true;
}
// hashTable = { "a": true, "b": true, "c": true, "d": true, "e":true, "f": true }
for(const value of smalleArray) {
if(!hashTable[value) return false;
}
위 코드는 hashTable 변수에 빈 해시 테이블을 생성한다.
이어서 largeArray의 각 값을 순회하며 배열의 항목을 해시 테이블에 추가한다.
그 뒤 smallArray 내 각 항목이 hashTable의 키로 존재하는지 확인한다. 앞서 largeArray의 모든 항목을 hashTable에 키로 저장했다.
따라서 hashTable에서 모든 항목을 찾으면 largeArray에 있는 항목이라는 뜻이다.
위 알고리즘을 통해 전체 코드를 다시 작성해보자.
function isSubset(arr1, arr2){
let largeArray;
let smallArray
if(arr1.length > arr2.length){
largeArray = arr1;
smallArray = arr2;
} else {
largeArray = arr2;
smallArray = arr1;
}
let hashTable = {};
for(const value of largeArray) {
hashTable[value] = true;
}
for(const value of smalleArray) {
if(!hashTable[value) return false;
} 두 배열을 합친 총 항목 수를 N이라고 하면 각 항목을 한 번씩 순회했으므로 위 알고리즘은 O(N)이다.
O(N*M)에 비해 엄청난 개선이다.
해시 테이블을 인덱스로 사용하는 이 기법은 배열을 여러번 검색해야 하는 알고리즘에 자주 쓰인다.
알고리즘에서 배열의 값을 계속 검색해야 한다면, 매 검색에만 최대 N단계가 소요되기 때문이다.
키로 해시 테이블을 룩업해서 어떤 값이든 받으면 그 키가 해시테이블에 있다는 뜻이다.
아래의 문항들은 모두 실전 예제다.
직접 풀어보길 바란다.
2. 두 배열의 교집합
두 배열의 교집합을 반환하는 함수를 작성하라.
예를들어 [1,2,3,4,5]와 [0,2,4,6,8]의 교집합은 [2,4]이다.
(내장 기능을 사용하지 말고 직접 알고리즘을 개발해보자)
function intersectionSet(arr1, arr2) {
let largeArr
let smallArr
let intersection = [];
const largeArrHashTable = {};
if(arr1.length >= arr2.length) {
largeArr = arr1;
smallArr = arr2;
} else {
largeArr = arr2;
smallArr = arr1;
}
// 먼저 큰 배열을 헤시테이블로 이동
for(let i = 0; i < largeArr.length; i ++){
largeArrHashTable[largeArr[i]] = true;
}
// 작은 배열을 돌면서 lAHT[smallLargeValue]가 true인지 확인
// true면 intersection 배열에 푸시
for(let i = 0; i < smallArr.length; i++) {
if(largeArrHashTable[smallArr[i]]){
intersection.push(smallArr[i]);
}
}
return intersection
}
intersectionSet([1,2,3,4,5],[2,4,6,7,9,11,14]) // [2, 4]3. 문자열 배열의 첫 번째 중복 값 반환
문자열 배열을 받아 첫 번째 중복 값을 찾아 반환하는 함수를 작성해보자.
예를 들어 배열이 arr =["a","b","c"",d","e","c"]라면, 함수는 배열에서 중복인 c를 반환해야 한다.
(배열에는 반드시 하나 이상의 중복 쌍이 있다.)
(
단 함수의 효율성은 O(N)이어야 한다.
function duplicateString(arr) {
const obj = {};
const duplString = new Map();
for(let i = 0; i < arr.length; i++){
if(obj[arr[i]]){
duplString.set(arr[i],arr[i]);
}else{
obj[arr[i]] = arr[i];
}
}
return [...duplString.keys()]; // ['a','f','d']
}
}
duplicateString(['a','b','d','f','a','f','c','q','z','d'])4. 알파벳 26자 중 사용하지 않은 문자열 구하기
문자열을 받아 빠진 문자열을 반환하는 함수를 작성해보자.
예를 들어 문자열 the quick brown box jumps over a lazy dog는 f를 제외한 모든 문자를 포함한다.
함수의 시간 복잡도는 O(N)이어야 한다.
function findNotuseAlphabet(string){
let alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'];
let notUseAlphabet = [];
let hashString = {};
for(let i = 0; i < string.length; i++){
hashString[string[i]] = true;
}
for(let i = 0; i < alphabet.length; i++){
if(!hashString[alphabet[i]]) {
notUseAlphabet.push(alphabet[i])
}
}
return notUseAlphabet.join()
}
findNotuseAlphabet("i can't wait!!") // b,d,e,f,g,h,j,k,l,m,o,p,q,r,s,u,v,x,y,z5. 문자열에서 첫 번째 중복되지 않는 문자 찾기
문자열에서 첫 번째 중복되지 않는 문자를 반환하는 함수를 작성해보자.
예를 들어 문자열 "minimum"에는 한 번만 등장하는 문자가 "n"과 "u" 두개인데 먼저 나오는 문자인 "n"을 반환해야 한다.
함수의 효율성은 O(N)이다.
function nonDuplicateStringAtFirst(string) {
let hashStr = {};
let firstString = '';
let index = string.length;
for(let i = 0; i < string.length; i++) {
if(hashStr[string[i]]){
hashStr[string[i]] = string.length + 1;
}else{
hashStr[string[i]] = i;
}
}
for(const key in hashStr) {
if(index > hashStr[key]){
index = hashStr[key]
firstString = key
}
}
return firstString;
}
nonDuplicateStringAtFirst('hello world! hello hash table!'); // w해시 테이블은 효율적인 소프트웨어 개발에 필수다.
O(1)의 읽기와 삽입은 쉽게 따라잡을 수 없는 자료 구조다.
지금까지는 효율성과 속도를 중심으로 다양한 자료 구조를 분석했지만
속도 외에 장점을 제공하는 자료 구조도 존재한다.
이 다음에는 코드의 간결성과 유지보수성을 향상시킬 수 있는 두 자료구조를 알아본다.
