해시 테이블 (hashTable)
해시 함수를 사용해서 key를 고유 index로 변환해서 해시 테이블에 값을 저장한다. index를 만들기 위해서 해시 함수를 사용한다. 해시 테이블에는 문제점이 있는데, 해시 함수를 사용해서 생성된 인덱스가 중복될 수 있다는 문제가 있다. 따라서 해시 함수에는 선형 탐사법, 제곱 탐사법, 이중 해싱 등의 알고리즘을 사용해서 문제점을 해결해야 한다.
해시 테이블은 해시 함수를 거쳐서 만들어진 인덱스와 값을 갖고 해시 테이블에 저장한다. 따라서 추가, 삭제하려는 요소의 key를 알고 있다면 (해시 함수에 의해서 index로 변환됨) 상수 시간 복잡도를 갖는다.
그렇다면 왜 이 불안정한 "해시 함수"를 왜 쓰는 것인가? 그냥 배열처럼 바로 저장하면 문제가 없어보이고, 해시 함수가 만들어내는 인덱스로 인해 발생하는 충돌에 대한 걱정을 할 필요도 없는데?
검색을 통해 찾아본 결과 해시 함수를 사용하지 않고 배열에 직접 저장한다면 최대 키 값에 대해서 알고 있어야 한다. 또한 키 값이 매우 많아진다면, 전체 탐색을 해야 할 수도 있기 때문에 실용성이 떨어진다. 그리고 일정하게 키 값이 정해진게 아니라면 (ex. 오름 차순 0, 1, 2,..) 키 값들이 배열에 넓게 분포되어 배열의 크기가 커지고 그에 따른 메모리 낭비도 발생할 수 있다. 따라서 해시 함수를 사용해서 데이터를 추가하는 사용자와 데이터를 추출해서 사용하는 사용자 모두 인덱스를 고려할 필요 없게 만든다면, 단순히 키 값만을 갖고 원하는 요소를 추가하거나 삭제할 수 있다는 장점이 있다.
여기서는 해시 함수를 구현하는 것이 아닌 해시 테이블을 자바스크립트에서 구현해 본다. 해시 테이블을 구현하는 방법은 자바스크립트의 배열을 사용하는 방법과 객체를 사용하는 방법 그리고 Map과 Set을 사용하는 방법이 있다.
배열을 사용해서 해시 테이블 만들기
const hashTableByArray = [];
hashTableByArray["key"] = 100;
hashTableByArray["key2"] = "Hello";
hashTableByArray[1234] = 1234;
console.log(hashTableByArray["key"])
console.log(hashTableByArray["key2"])
console.log(hashTableByArray[1234])
delete hashTableByArray["key"];
console.log(hashTableByArray["key"]);
console.log(hashTableByArray); 비어 있는 배열을 생성하고 (자바스크립트에서 배열을 생성할 때 크기를 고려하지 않는다는 점은 언제봐도 편하다.) key 값에 따른 value를 저장한다. 여기서 key값으로 문자열이 아닌 숫자 1234를 사용해서 value 1234를 저장했다.
출력할 때 key값으로 1234를 입력했지만 정상적으로 출력되었다. 이는 1234가 문자열로 자동으로 변환되기 때문이다. 마찬가지로 배열의 요소를 delete 하면 해당 요소의 값이 빈값이 될뿐 배열의 크기가 변하지 않는다.
객체를 사용해서 해시 테이블 만들기
const hashTableByObject = {};
hashTableByObject["key"] = 100;
hashTableByObject["key2"] = "hello";
hashTableByObject[1234] = 1234;
const obj = { B: 32};
hashTableByObject[obj] = 22;
console.log(hashTableByObject[obj]);
console.log(hashTableByObject["key"]);
console.log(hashTableByObject["key"]);
console.log(hashTableByObject[1234]);
delete hashTableByObject["key"];
console.log(hashTableByObject); 배열과 비슷하게 key와 value를 추가한다. 차이점은 delete를 사용했을 때 객체에 남지 않는다는 점이다. 배열과 객체 모두 삭제한 값을 출력하면 undefined가 출력되지만 배열은 empty value 로 남아 있고 객체는 존재하지 않는다. 또한 key값으로 객체를 사용할 수 없다.
Map을 사용해서 해시 테이블 만들기
const map = new Map();
map.set("key", 100);
map.set("key2", "Hello");
map.set(1234, 1234);
console.log("map[]", map["key"]); //undefined
console.log("map[]", map["key2"]); //undefined
console.log("map[]", map[1234]); //undefined
console.log("map.get()", map.get("key"));
console.log("map.get()", map.get("key2"));
console.log("map.get()", map.get(1234));
const obj = { a: 1 };
map.set(obj, "A1");
console.log("map[]", map[obj]); // undefined
console.log("map.get()", map.get(obj)); // object를 key로 사용
console.log(map.keys());
console.log(map.values());
map.delete("key");
map.clear();
console.log(map);Map을 사용하면 set, get, delete, clear 함수를 사용할 수 있다. 배열처럼 [{key}]를 사용해서 value를 확인할 수 없고 반드시 get을 사용해야 한다. 요소를 추가 할때도 set을 사용해야 한다. 또한 객체나 배열과 달리 object를 키로 사용해도 된다. clear를 사용하면 Map 객체를 비울 수 있다.
Set을 사용해서 해시 테이블 만들기
const set = new Set();
set.add("key");
set.add("key2");
set.add("key3");
console.log(set.has("key"));
console.log(set.has("key3"));
set.delete("key2");
console.log(set.has("key2"));
console.log(set.size);
console.log(set);
set.clear();
console.log(set); Set을 사용하면 key값과 동일한 value를 테이블에 저장한다. add 함수를 사용해서 추가하고 delete를 사용해서 삭제할 수 있다. 테이블에 요소가 존재하는지 확인하기 위해서는 has함수를 사용하면 된다. has함수는 true/false를 리턴한다. Map과 가장 큰 차이점이라면 Key-Value가 동일한 값으로 저장된다는 점이다.
해시 테이블을 구현하는데 있어서 가장 중요한 부분은 해시 함수를 구현하는 것이라 생각한다. 충돌이 발생하지 않는 해시 함수가 있어야 안정적인 해시 테이블을 완성할 수 있다. 해시 함수를 구현하는 방법은 추후에 더 공부해야겠다...
