[자료구조 공부] 자바스크립트 해시 테이블 #6

☘️ 해시 테이블

해시 테이블은 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조

각 테이블에 해당하는 index를 해시 테이블에서는 buckets 이라고 하며,

테이블의 각 요소는 키와 값이 저장되어 있다.

해시 테이블에서 요소를 삽입하는 것은 상수 시간 O(1) 이 소요되며,

키를 알고 있을 경우 요소를 삭제, 탐색하는 것도 상수 시간 O(1) 이 소요된다.

 

해시 함수

입력받은 값을 특정 범위 내 숫자로 변경하는 함수

키 값을 해시 함수를 통해 해싱하여 buckets에 저장하며,

해시 함수는 특정한 구현 방법이 없어 사용자 마음대로 구현하면 된다.

 

해시 테이블 문제점

해시 함수를 통해 키 값을 해싱하는데, 만약 해시 함수의 결과가 동일하여 겹칠 수 있다는 문제점이 있고

이를 해시 충돌 이라고 불린다.

 

☘️ 해시 충돌(Hash Collision) 해결 방법

해시 충돌이 발생했을 경우, 해결하는 방식 4가지가 있다.

선형 탐사법

단순히 옆 index 한 칸 이동하는 방법

단순하지만 특정 영역에 데이터가 몰릴 수 있다는 단점이 있고,

이동했을 경우 또 충돌이 일어난다면 최악의 경우 선형 시간 O(n) 이 소요될 수 있다.

 

제곱 탐사법

충돌이 발생한 횟수의 제곱만큼 옆으로 이동

선형 탐사법의 문제점인 특정 영역에 데이터가 몰리는 것을 방지하기 위해 제곱 탐사법을 사용할 수 있다.

 

이중 해싱

충돌이 발생하면 다른 해시 함수 사용

충돌이 발생할 경우 기존 해시 함수가 아닌 다른 해시 함수를 사용하여 새로운 index를 만든다.

 

분리 연결법

bucket의 값을 연결 리스트로 사용해, 충돌이 발생하면 리스트에 값을 추가

다른 방법과 다르게 충돌이 발생할 경우 다른 index로 이동하지 않고,

해시 테이블의 요소를 연결 리스트로 만들어 충돌이 발생한 요소를 그대로 해당 bucket에 넣는다.

 

최악의 경우 하나의 bucket에 요소가 무한대로 들어갈 수 있다는 단점이 있다.

 

☘️ 해시 테이블 사용 예시

해시 테이블을 사용하는 상황에는 학생 정보를 관리하는 출석부가 있다.

 

만약 출석부를 연결 리스트로 구현한다면, 학생 정보를 찾을 때엔 선형 시간 O(n) 이 소요되고,

배열로 구현한다면, 인덱스를 모를경우 학생을 탐색할 경우 선형 시간 O(n) 이 소요된다.

 

그래서 이름을 key로 하여 해시 테이블을 만들 경우 학생을 찾고, 추가, 삭제할 경우 상수 시간 O(1) 이 소요된다.

최악의 경우 탐색이 선형 시간 O(n) 이 소요될 수 있지만 연결 리스트와 배열보다는 안정적이다.

 

☘️ 자바스크립트에서 해시 테이블 사용하기

자바스크립트에서 해시 테이블을 구현하는 방법에는 여러 가지가 있다.

• 배열 - 추천X
• 객체 - 제일 간단
• Map - key 값 다양한 타입 가능, 편리한 메서드 제공
• Set - key와 value 동일하게 저장

 

배열

배열을 사용해서 해시 테이블을 사용하는 방법은 다음과 같다

const table = [];

// 요소 넣기
table['key'] = 100;
table['key2'] = 'Hello';
console.log(table['key']);

// 요소 수정
table['key'] = 349;
console.log(table['key']);

// 요소 삭제
delete table['key'];
console.log(table['key']);

console.log(table);

출력 결과

 

객체

자바스크립트에서 배열은 근본적으로 객체 타입이라 객체는 위에 배열과 크게 다른 점이 없다.

const table = {};

// 요소 넣기
table['key'] = 100;
table['key2'] = 'Hello';
console.log(table['key']);

// 요소 수정
table['key'] = 349;
console.log(table['key']);

// 요소 삭제
delete table['key'];
console.log(table['key']);

console.log(table);

출력 결과

 

 

Map

Map은 key 값에 object와 같이 다양한 타입을 넣을 수 있으며,

실용적인 메서드( set(), get(), keys(), values(), clear() )를 제공해 준다.

const table = new Map();

// 요소 넣기
table.set('key', 100);
table.set('key2', 'Hello');

// 요소 값 가져오기
console.log(table['key']); // 사용 X, undefined 출력
console.log(table.get('key'));

// 요소 넣기 - Map은 object를 key로 쓸 수 있음
const object = { a: 1 };
table.set(object, 'A1');
console.log(table.get(object));
console.log(table);

// 요소 삭제
table.delete(object);
console.log(table.get(object));
console.log(table);

// 요소 key, value 가져오기
console.log(table.keys());
console.log(table.values());

// 요소 전체 삭제
table.clear();
console.log(table);

출력 결과

 

Set

Set은 key와 value 의 값이 동일하게 저장된다.

Set도 Map처럼 제공하는 메서드( add(), has(), delete(), clear() ) 를 사용한다.

const table = new Set();

// 요소 넣기
table.add('key');
table.add('key2');
console.log(table);

// 요소 값 유무
console.log(table.has('key'));
console.log(table.has('key3'));

// 요소 삭제
table.delete('key2');
console.log(table.has('key2'));

// 요소 전체 삭제
table.clear();
console.log(table.size);
console.log(table);

출력 결과

 

---

 

 

해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다. (유료강의)

코딩테스트 광탈 방지 A to Z : JavaScript