(TIL Day03-05)자료구조- 해시 테이블

해시 테이블(Hash Table)

• 키와 값을 받아 키를 해싱(Hashing)하여 나온 index 값을 저장하는 선형 자료구조.
• 삽입은 O(1)이며, 키를 알고 있다면 삭제와 탐색도 O(1)로 수행한다.
• 해시 함수를 통해 키를 특정 범위 내 숫자로 변경한다.
• 키로 "name"이 주어진다면, 컴퓨터에서는 해시 함수를 통해 1239593로 바꿔 데이터를 저장한다.
• 즉, 사람의 입장에서는 name이지만 컴퓨터의 입장에서는 1239539가 된다.
• value가 저장되는 공간을 bucket이라 한다.
• JavaScript에서 객체(Object)가 해시 테이블에 해당한다.

해시 테이블

 

해시 함수

 

해시 충돌(Hash Collision)

• 만약 해시 함수의 결과가 기존에 있던 값과 같게 된다면 충돌이 발생한다.
• 이를 해결하기 위해서 "분리 연결법"과 "개방 주소법"으로 해결한다.

https://mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?

 

 

코드

const hash = [];
hash["name"] = "Kim";
hash["age"] = 22;
hash["gender"] = "man";

console.log(hash);

 

 

Map()과 Set()을 이용할 수도 있다.

Set은 Key와 Value가 동일하게 저장된다.

// Map()
const hash = new Map();
hash.set("name", "Kim");
hash.set("age", 23);
hash.set("gender", "woman");

console.log(hash);

Ma()

 

 

// Set()
const hash = new Set();
hash.add("name");
hash.add("age");
hash.add("gender");

console.log(hash);

Set()