🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
해시테이블(HashTable)
📍 해시테이블(HashTable)
👉🏻 해시, 맵,해시맵, 딕셔너리라고도 불림
👉🏻 해시 + 테이블 합쳐진 자료 구조
📍 해시테이블(HashTable) 예시
👉🏻 야구 선수의 등 번호
👉🏻 기존 테이블은 메모리 낭비하는 경우가 있어(ex: 야구 선수 등번호의 경우 빈 숫자가 있음) 특정한 계산(해시 함수, ex: 10으로 나눠서 넣음)을 거쳐 메모리 절약을 하고자 함
👉🏻 키(Key)를 알고 있을 경우 조회/삽입/삭제를 O(1)의 성능으로 접근할 수 있게 됨
👉🏻 단, 이때 등 번호가 11번, 21번이 있다면 해시 함수를 거친 값은 모두 1이 됨
👉🏻 중복된 값이 있다면 같은 인덱스에 연결 리스트로 연결함
👉🏻 21번을 찾고자 할 때 해시 함수를 거쳐 1번 인덱스에 접근하고, 해당 데이터를 만날 때까지 조사함 - O(n)의 성능
-----> 해시 함수의 선정이 매우 중요해짐!
📍 해시테이블(HashTable) 장점
👉🏻 빠른 데이터 읽기, 삽입, 삭제 가능
📍 해시테이블(HashTable) 단점
👉🏻 메모리를 많이 차지함
👉🏻 좋은 해시 함수를 구현하는 것이 필수적
📍 해시테이블(HashTable) 구현
[ HashTable.mjs ]
import { DoublyLinkedList } from './DoublyLinkedList.mjs';
class HashData {
constructor(key, value) {
this.key = key;
this.value = value;
}
}
class HashTable {
constructor() {
this.arr = [];
for(let i = 0; i < 10; i++) {
this.arr[i] = new DoublyLinkedList();
}
}
// 원소마다 빈 이중 연결 리스트 생성 완료!
hashFunction(number) {
return number % 10;
}
set(key, value) {
// 해시 함수를 거쳐 배열의 인덱스를 결정해 해당 인덱스의 연결 리스트에 삽입
this.arr[this.hashFunction(key)].insertAt(0, new HashData(key, value));
}
get(key) {
let currentNode = this.arr[this.hashFunction(key)].head;
while(currentNode != null) { // 해당 인덱스를 모두 돌아라
if(currentNode.data.key == key) {
return currentNode.data.value;
}
currentNode = currentNode.next;
}
return null;
}
remove(key) {
let list = this.arr[this.hashFunction(key)];
let currentNode = list.head;
let deletedIndex = 0;
while(currentNode != null) {
if(currentNode.data.key == key) {
return list.deleteAt(deletedIndex);
}
currentNode = currentNode.next;
deletedIndex++;
}
return null;
}
}
export { HashTable };
[ test_hashtable.mjs ]
import { HashTable } from "./HashTable.mjs";
let hashTable = new HashTable();
hashTable.set(0, "안권수");
hashTable.set(1, "황성빈");
hashTable.set(2, "김민석");
hashTable.set(3, "신윤후");
hashTable.set(4, "이호연");
hashTable.set(5, "김민수");
hashTable.set(6, "한태양");
hashTable.set(7, "이학주");
hashTable.set(8, "전준우");
hashTable.set(9, "정훈");
hashTable.set(10, "이대호");
hashTable.set(11, "최동원");
hashTable.set(12, "김재유");
hashTable.set(13, "안치홍");
hashTable.set(14, "김세민");
hashTable.set(15, "김진욱");
hashTable.set(16, "한현희");
hashTable.set(17, "렉스");
hashTable.set(18, "최준용");
hashTable.set(19, "김강현");
hashTable.set(20, "");
hashTable.set(21, "박세웅");
hashTable.set(22, "구승민");
hashTable.set(23, "김도규");
hashTable.set(24, "김상수");
hashTable.set(25, "한동희");
hashTable.set(26, "진승현");
hashTable.set(27, "유강남");
hashTable.set(28, "반즈");
hashTable.set(29, "");
hashTable.set(30, "이민석");
hashTable.set(31, "신정락");
hashTable.set(32, "강태율");
hashTable.set(33, "최이준");
hashTable.set(34, "김원중");
console.log(`1: ${hashTable.get(1)}`);
hashTable.remove(1);
console.log(`1: ${hashTable.get(1)}`);
console.log(`34: ${hashTable.get(34)}`);
👉🏻 set: 데이터 삽입
👉🏻 get: 데이터 읽기
👉🏻 remove: 데이터 제거
-----> 내가 데이터를 set 한 후에 등 번호 "34번 김원중"을 찾고자 할 때, 해시 테이블에서는 내부적으로 34를 10으로 나눈 4번 인덱스를 찾아 "4번 이호연, 14번 김세민, 24번 김상수"를 거쳐 34와 일치하는 김원중을 찾아낸 것!