해시테이블이란?
- 프로그래밍 언어에 따라서 조금씩 다른 이름을 가지고 있음
해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary) - 해시 함수로 테이블의 인덱스를 새로 만들기 때문에 해시테이블이라는 이름이 붙음.
해시테이블의 장단점

장점
- 빠른 검색 속도: 평균적으로 O(1)의 시간 복잡도로 데이터를 검색할 수 있 음.
- 빠른 삽입 및 삭제: 평균적으로 O(1)의 시간 복잡도로 데이터를 삽입하거나 삭제할 수 있 음.
- 유연성: 다양한 종류의 데이터를 효율적으로 저장하고 검색할 수 있음.
단점
- 충돌 문제: 두 개 이상의 키가 동일한 해시값을 가질 때 충돌이 발생. 이를 해결하기 위해 추가적인 메모리와 시간이 필요.
- 메모리 사용량: 해시테이블은 효율적인 성능을 위해 종종 실제 데이터보다 큰 메모리 공간을 요구.
- 해시 함수의 선택: 좋은 해시 함수를 선택하지 않으면 성능이 저하될 수 있음.
요약
- 좋은 해시 함수가 필요함
- 검색속도, 삽입, 삭제는 빠름
- 두 개 이상의 키가 동일한 해시값을 가질때 충돌 발생.
해시 테이블의 주요 연산
- 데이터 삽입
- 데이터 읽기
- 데이터 제거
자바스크립트에서는 객체(Object)와 Map을 사용하여 해시테이블을 구현할 수 있다.
자바스크립트 예시
class HashTable {
constructor(size = 53) {
this.keyMap = new Array(size);
}
// 해시 함수
_hash(key) {
let total = 0;
let WEIRD_PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * WEIRD_PRIME + value) % this.keyMap.length;
}
return total;
}
// 키-값 쌍을 추가합니다.
set(key, value) {
let index = this._hash(key);
if (!this.keyMap[index]) {
this.keyMap[index] = [];
}
this.keyMap[index].push([key, value]);
}
// 키를 이용해 값을 가져옵니다.
get(key) {
let index = this._hash(key);
if (this.keyMap[index]) {
for (let i = 0; i < this.keyMap[index].length; i++) {
if (this.keyMap[index][i][0] === key) {
return this.keyMap[index][i][1];
}
}
}
return undefined;
}
// 모든 키를 가져옵니다.
keys() {
let keysArr = [];
for (let i = 0; i < this.keyMap.length; i++) {
if (this.keyMap[i]) {
for (let j = 0; j < this.keyMap[i].length; j++) {
if (!keysArr.includes(this.keyMap[i][j][0])) {
keysArr.push(this.keyMap[i][j][0]);
}
}
}
}
return keysArr;
}
// 모든 값을 가져옵니다.
values() {
let valuesArr = [];
for (let i = 0; i < this.keyMap.length; i++) {
if (this.keyMap[i]) {
for (let j = 0; j < this.keyMap[i].length; j++) {
if (!valuesArr.includes(this.keyMap[i][j][1])) {
valuesArr.push(this.keyMap[i][j][1]);
}
}
}
}
return valuesArr;
}
}
// 해시테이블 사용 예시
let ht = new HashTable();
ht.set("hello", "world");
// 객체 활용하기
class HashTable {
constructor() {
this.table = {};
}
// 키-값 쌍을 추가합니다.
set(key, value) {
this.table[key] = value;
}
// 키를 이용해 값을 가져옵니다.
get(key) {
return this.table.hasOwnProperty(key) ? this.table[key] : undefined;
}
// 키를 이용해 값을 제거합니다.
remove(key) {
if (this.table.hasOwnProperty(key)) {
delete this.table[key];
return true;
}
return false;
}
// 모든 키를 가져옵니다.
keys() {
return Object.keys(this.table);
}
// 모든 값을 가져옵니다.
values() {
return Object.values(this.table);
}
// 해시 테이블이 비어있는지 확인합니다.
isEmpty() {
return Object.keys(this.table).length === 0;
}
// 해시 테이블의 크기를 반환합니다.
size() {
return Object.keys(this.table).length;
}
// 해시 테이블을 비웁니다.
clear() {
this.table = {};
}
}
// Map 활용
class HashTable {
constructor() {
this.table = new Map();
}
// 키-값 쌍을 추가합니다.
set(key, value) {
this.table.set(key, value);
}
// 키를 이용해 값을 가져옵니다.
get(key) {
return this.table.get(key);
}
// 키를 이용해 값을 제거합니다.
remove(key) {
return this.table.delete(key);
}
// 모든 키를 가져옵니다.
keys() {
return Array.from(this.table.keys());
}
// 모든 값을 가져옵니다.
values() {
return Array.from(this.table.values());
}
// 해시 테이블이 비어있는지 확인합니다.
isEmpty() {
return this.table.size === 0;
}
// 해시 테이블의 크기를 반환합니다.
size() {
return this.table.size;
}
// 해시 테이블을 비웁니다.
clear() {
this.table.clear();
}
}'CS > Data Structure' 카테고리의 다른 글
| 셋 (Set) (0) | 2024.07.02 |
|---|---|
| 덱 (Deque) (0) | 2024.06.30 |
| 큐 (Queue) (0) | 2024.06.25 |
| 스택 (Stack) (0) | 2024.06.24 |
| 연결 리스트 (Linked List) (0) | 2024.06.23 |