0. 주제 선정하게 된 배경 :
코딩테스트 중에서 해시 개념으로 풀어보려고 했으나, 키-값으로 된 자료구조라고만 생각하고 푸니 문제를 못 풀겠다.
1. 해시란?
: 자바스크립트에서 해시란 일반적으로 해시 테이블(Hash Table)또는 해시 맵(Hash Map)과 같은 자료구조에서 사용되는 용어라고 한다.
해시는 데이터를 저장하기 위한 효율적인 자료 구조 중 하나로, key-value 쌍으로 저장한다.
-
해시 테이블 또는 해시 맵
: 해시 함수를 사용해서 데이터를 저장하는 구조
키와 값을 연관시켜서 저장하고, 해시 함수를 사용해서 키를 해시 값으로 변환한 다음, 해당 해시 값을 배열의 인덱스로 사용해서 값을 저장하거나 검색 -
해시 함수 :
key를 받아서 해당 키에 대한 해시 값을 생성
해당 해시 값을 사용해서 데이터를 저장하거나 검색 가능
즉, 해시 함수는 데이터를 해시 값으로 변환해주는 함수이고,
해시 맵 또는 해시 테이블은 해시 함수를 이용해서 데이터를 저장하고 관리하는 자료구조
// 해시 테이블 생성
let hashTable = {};
// 해시 함수 정의
function sampleHash(str) {
let hash = 0;
for(let i = 0; i < str.length;i++) {
hash += str.charCodeAt(i);
}
return hash;
}
let key = 'apple';
let value = '사과';
// 해시 값 계산
let hash = sampleHash(key);
// 키-값 저장
hashTable[hash] = value;
// 특정 키에 대한 값 검색
let searchKey = 'apple';
let searchHash = hashTable(searchKey);
let result = hashTable[searchHash];
2. 해시 테이블
해시테이블에는 배열 구조가 있음
Q : 내부에 배열 같은 구조가 있으면서 어떻게 배열보다 더 빠르게 탐색이 가능한걸까?
A : 해시 함수 덕분임
2-1. 해시 함수
: 해시 함수는 키값을 숫자로 바꿔주고, 그 숫자는 인덱스가 되는 것임
2-2. 해시 충돌
: 각각 다른 키에 대해서 해시 함수가 동일한 숫자를 반환하면 해시 충돌이 일어남
[해결법]
충돌된 인데스의 값에 새로운 배열을 만들어서 충돌된 값을 넣어줌
나중에 검색할땐 선형 검색으로 찾음
3. 배열 vs 해시 테이블
3-1. 배열
: 배열에서 원하는 값을 찾기 위해서는 선형검색을 하면 됨
시간 복잡도 : O(N)
const menu = [
{name: 'coffee', price: 10},
{name: 'burger', price: 14},
{name: 'tea', price: 5},
{name: 'pizza', price: 10},
{name: 'juice', price: 5},
]3-2. 해시 테이블
: 원하는 정보의 값을 얻고 싶을땐,
원하는 정보를 키로 사용해서 값을 얻을 수 있음
시간 복잡도 : O(1)
단, 언제나 상수 시간인건 아니지만 (해시 충돌시 선형검색을 해야하기 때문) 평균적으로는 상수 시간임.
const menu = {
coffee: 10,
burger: 14,
tea: 5,
pizza: 10,
juice: 5
}4. 결론
객체를 사용하자
5. 참고
