Javascript 자료구조 03 : Hash Table

Hash Table(해쉬 테이블)

Key + Data 구조

Hashing Function을 통해 Key를 Hash Code로 변환한 후에 테이블에 저장.
Hashing: 임의의 값을 고정 길이로 변환하는 것. 즉, 암호화

장점
- 빠른 데이터 검색 속도(index를 돌지 않고 Hash Code를 찾아가기 때문)
- 중복을 찾아내기 용이

단점
- 배열에 비해 저장 공간을 더 많이 차지

주의
- key값이 다르더라도 hashing한 결과가 같은 경우 충돌이 발생할 수 있음
- 따라서 충돌을 해결한 또 다른 자료구조를 필요로 함.

시간 복잡도
- 충돌이 없는 일반적인 경우, $O(1)$ (데이터 삽입, 검색, 삭제)
- 모두 충돌하는 최악의 경우, $O(n)$

"공간을 희생해서 시간을 줄이는 방법"

간단한 Hash Table 구현

// Hash Table 생성
const hashTable = new Array(10).fill(0);
// Hashing Function
function hashingDiv(n) {
  return n % 10;
}
// Hashing
function hashing(data, value) {
  const key = data.charCodeAt(0); // 전처리
  const address = hashingDiv(key); // Hashing Function
  hashTable[address] = value; // add data
}
// 테스트 코드
hashing("first", "chair");
hashing("second", "desk");
hashing("third", "coffee");
console.log(hashTable);
//
// Get Data
function getData(data) {
  const key = data.charCodeAt(0); // 전처리
  const address = hashingDiv(key); // Hashing Function
  return hashTable[address];
}
// 테스트코드
console.log(getData("second")); // "desk"
//
// 충돌 테스트 코드
hashing("fourth", "mac"); // 입력한 key "first"와 "fourth"의 hashing 결과값이 같아 충돌
console.log(hashTable); // 나중에 입력한 값으로 덮어씌워짐.

다음 글에서 Hash Table 충돌 방지를 다룹니다.

2020.04.08 최초 작성

댓글 환영 by.protect-me