[자료구조] 해시테이블

이전 블로그 포스팅 다시 공부하면서 옮기는 중..

---

github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/hash-table

trekhleb/javascript-algorithms

www.youtube.com/watch?v=Vi0hauJemxA&t=1s

🎈해시테이블

키와 값의 구조를 가지는 자료구조
해시함수를 통해 원하는 값을 찾는다

해시함수(키) -> 해시코드 -> 인덱스 -> 값

검색하고자하는 키 값(입력값)을 해시함수를 통해 해시코드로 만들어서 그 해시코드를 배열의 인덱스로 환산을 해 데이터에 접근&저장하는 자료구조이다.

입력 데이터가 완전 같지않는 이상 해시함수를 통해 나온 해시코드가 같을 수 없다.

검색 속도가 매우 빠르다

미리 배열을 만들어 놓고 데이터가 들어오길 기다린다.

 

충돌이 발생할 수 있다

: 한 배열의 방에 너무 많은 데이터들이 들어갈 경우

: 배열의 방이 한정되어있기때문에 어떤 키들은 중복되는 키or 중복되는 인덱스를 가질 수도 있다.

 

해시 함수

임이의 길이의 데이터를 고정된 길이의 데이터로 매핑해주는 함수를 해시함수라고 합니다.

• 해시 함수에 의해 얻어지는 값을 해시라고 합니다.
• 해시 함수는 항상 같은 출력값을 가집니다.

충돌 처리 방법

1. 체이닝
   찾는 데이터는 리스트를 돌면서 찾아온다
   충돌을 방지하기 위해서, 배열방 안에 바로 데이터를 저장하는것이 아니라 연결리스트를 사용해서 데이터를 추가해준다

1. 오픈 어드레싱 ( 개방 주소법 )
   충돌이 발생하면 다음으로 비어있는 주소를 찾아 저장

🎄 Map을 이용한 코드

developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map

Map - JavaScript | MDN

 

Map이란?

키-값 쌍을 저장하며 각 쌍의 삽입 순서도 기억하는 콜렉션

map을 사용할 땐 map전용 메서드 set, get 등을 사용해야만 한다.

키값으로 다양한 자료형을 사용할 수 있다

 

해시함수

const hash = (key, size) => {
	let hashedKey = 0;
	for (let i = 0; i < key.length; i++) {
		hashedKey = key.charCodeAt(i);
	}
	return hashedKey % size;
};

해시테이블

class HashTable {
	constructor() {
		this.size = 10;
		this.buckets = Array(this.size);

		for (let i = 0; i < this.buckets.length; i++) {
			this.buckets[i] = new Map();
		}
	}
	insert(key, value) {
		let idx = hash(key, this.size);
		this.buckets[idx].set(key, value);
	}

	remove(key) {
		let idx = hash(key, this.size);
		let deleted = this.buckets[idx].get(key);
		this.buckets[idx].delete(key);
		return deleted;
	}
	search(key) {
		let idx = hash(key, this.size);
		return this.buckets[idx].get(key);
	}
}