본문으로 건너뛰기

Hash(해시)

· 약 4분
dldkffh
dldkffh

Hashing(해싱)​

  • 임의의 길이를 가진 값을 해시 함수를 사용해 고정된 크기의 값으로 변환하는 작업

해시 테이블​

  • 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
  • 삽입은 O(1)O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)O(1)로 수행

해시 함수​

  • 입력받은 값을 특정 범위 내 숫자로 변경하는 함수
  • 문제점 : 해시 함수의 결과가 동일한 경우가 생길 수 있음

탐색 방법​

  1. 선형 탐색법

    • 충돌이 발생하면 옆으로 한칸 이동

  2. 제곱 탐색법

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

  3. 이중 해싱

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

  4. 분리 연결법

    • 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가
    • 단점 : 하나의 버킷이 무한정 늘어날 수 있다.

1. Array를 Hash Table처럼 사용​

javascript
const table = [];
table["key"] = 100;
table["key2"] = "Hello";
console.log(table);
console.log(table["key"]);

table["key"] = 349;
console.log(table["key"]);

delete table["key"];
console.log(table["key"]);
powershell
[ key: 100, key2: 'Hello' ]
100
349
undefined

2. Object를 Hash Table처럼 사용​

javascript
const table = {};
table["key"] = 100;
table["key2"] = "Hello";
console.log(table);
console.log(table["key"]);

table["key"] = 349;
console.log(table["key"]);

delete table["key"];
console.log(table["key"]);
powershell
{ key: 100, key2: 'Hello' }
100
349
undefined

3. Map을 Hash Table처럼 사용​

Map()​

  • Map 객체는 키-값 쌍인 집합
  • 한 Map에서의 키는 오직 단 하나만 존재. 이는 Map 집합의 유일성
  • Map 객체는 키-값 쌍으로 반복. for...of 루프는 각 반복에 대해 [key, value]로 이루어진 멤버가 2개인 배열을 반환. 반복은 삽입한 순서대로 발생. 즉, set() 메서드로 맵에 처음 삽입한 각각의 키-값 쌍 순서와 대응 (set()이 호출되었을때 맵에서 해당 키가 없었을 경우)
javascript
const table = new Map();
table.set("key", 100);
table.set("key2", "Hello");
console.log(table);
console.log(table["key"]);
console.log(table.get("key"));

const object = { a: 1 };
table.set(object, "A1");
console.log(table);
console.log(table.get(object));

table.delete(object);
console.log(table.get(object));

console.log(table.keys());
console.log(table.values());

table.clear();
console.log(table);
console.log(table.keys());
console.log(table.values());

powershell
Map(2) { 'key' => 100, 'key2' => 'Hello' }
undefined
100
Map(3) { 'key' => 100, 'key2' => 'Hello', { a: 1 } => 'A1' }
A1
undefined
[Map Iterator] { 'key', 'key2' }
[Map Iterator] { 100, 'Hello' }
Map(0) {}
[Map Iterator] {  }
[Map Iterator] {  }

4. Set을 Hash Table처럼 사용​

Set()​

  • Set 객체는 값 콜렉션으로, 삽입 순서대로 요소를 순회할 수 있다.
  • 하나의 Set 내 값은 한 번만 나타날 수 있다.
  • 어떤 값은 그 Set 콜렉션 내에서 유일
javascript
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"));

const object = { a: 1, b: 2 };
table.add(object);
console.log(table.size);

table.clear();
console.log(table.size);
powershell
Set(2) { 'key', 'key2' }
true
false
false
2
0