해시 ∙ 해시맵

DEV · 11 Dec 2021

1. 해시(Hash)

1-1. 직접 주소 테이블(Direct Address Table)

해시 테이블은 ‘직접 주소 테이블’이라는 자료구조에서 시작된다.
key와 value를 가지며 하나의 key에 하나의 value가 매칭된다.
Array에서는 key값에 숫자만 가능함(index). 그러나 Hash Table은 key값에 문자열도 가능하다.
찾고자 하는 value와 테이블의 index가 일치하므로, 저장된 데이터를 바로 꺼내올 수 있다.
시간복잡도 O(1)으로 표현된다.
이진트리검색, linked list와 같은 구조를 쓰게 될 시 특정값의 삭제가 다른 값의 탐색에 영향을 미칠 수가 있는데, map은 그러한 것에서 자유롭다.
그러나, 단점으로 꼽히는 것이 ‘공간의 효율성’이다.

[ <3 empty items>, 3, <6 empty items>, 10, <79 empty items>, 90 ]

‘적재율‘로 이러한 공간의 활용도를 표현할 수도 있는데, 위와 같은 경우는 총 95개의 공간 중 3개가 사용되어 3.15%의 적재율이라 볼 수 있다.

1-2. 해시 테이블과 해시 함수

해시 함수 : 임의의 길이를 가지는 데이터를 고정된 길이의 데이터로 매핑해주는 함수

직접 주소 테이블의 단점을 보완하기 위해 사용할 수 있는 방법이 해시 테이블을 사용하는 것이다.
해시 테이블의 사용을 위해서 ‘해시 함수’를 만들어주게 된다.

해시 함수의 특징
해시 함수를 거쳐 나온 값을 통해 value를 추측할 수 없다.
value를 바로 적용하지 않기 때문에, 예를 들면 ‘100’이라는 숫자에 대해서 100개의 공간을 만든 뒤 값을 배치할 필요가 없어지게 된다.
```
function hashFunction(key) {
  return key % 10;
}
```
위 함수에서 가장 중요한 것은 ‘10’이라는 크기 내로 한정되어진다는 것이다.
Hash Table의 key와 연결된 value를 삽입, 삭제, 탐색하는 알고리즘 함수이다.(대표적으로 MDS)
key가 들어오면 랜덤한 주소값을 생성한 뒤, 그 주소값으로 설정된 테이블에 key, value를 저장한다.
해시함수 과정에서 해시충돌(Collision)이 발생할 수 있다.

2. 해시 충돌(Collision)

해시 충돌 : 서로 다른 value를 입력했을 때, 테이블 내 같은 index로 값이 들어가(같은 값이 나오게 되어) 겹치는 상황

해시 테이블은 데이터의 개수보다 테이블의 크기를 줄이고자 하는 생각에서 나왔기 때문에, 이에 대한 해결책이 존재한다.
근본적으로, 해시 함수를 짤 때 가능한 겹치는 값이 나오지 않도록 하는 것이 중요하지만, 결국 겹치는 구간이 존재할 수 밖에 없다.

2-1. 개방 주소법(open address)

충돌이 발생할 시, 테이블 내 새로운 주소를 탐사한 후, 비어있는 곳에 데이터를 입력하는 방식.
해시 함수의 결과값 외에 다른 인덱스를 허용한다는 의미로 ‘개방 주소’라고 표현한다.

A. 선형 탐사법(Linear Probing)

선형으로 순차적으로 탐사하는 방법.
충돌이 일어났을 경우, 충돌이 발생한 곳의 바로 옆자리로 배치가 이루어진다.

const hashingIndex = function (number) {
  const result = number % 3;
  return result;
};
class hashTable {
  constructor() {
    this.table = [];
  }

  setValue(value = -1) {
    const index = hashingIndex(value);
    if (this.table[index]) {
      this.table[index + 1] = value;
    } else {
      this.table[index] = value;
    }
  }
  getTable() {
    return this.table;
  }
}

const myTable = new hashTable();
myTable.setValue(4);
myTable.setValue(7);

console.log(myTable.getTable());
// [ <1 empty item>, 4, 7 ]

위 코드에서 입력된 4, 7은 모두 3으로 나눌 때의 나머지 값이 1이므로, index 1에 값이 들어가야 한다.
→ 4가 이미 배치되어 있어 7은 그 옆 칸으로 이동하여 배치된다.
문제점 : 값의 주변이 모두 채워지는 일차 군집화(Primay Clustering)가 발생하기 쉽다.
→ 이로 인해, 옆 칸에 저장되는 데이터가 늘어나고, 그 근처에 새로 저장되려는 값들도 끊임없이 옆으로 새로 이동해 저장되는 문제가 발생한다.

B. 제곱 탐사법(Quadratic Probing)

선형 탐사법과 유사한 방식이지만, 탐사의 폭이 제곱으로 늘어난다.
충돌의 발생 수의 제곱만큼 이동하게 되므로 ‘한 번 충돌 시 1, 두 번 충돌 시 4’ 이런식으로 늘어나게 된다.

3. JavaScript의 해시테이블(Hash Table) : Map

JavaScript에서의 key-value 자료구조는 Object가 대표적이었는데, Map, Set이 추가되어 현재 JavaScript의 해시테이블은 “Object, Map, Set”가 있다.

3-1. Map

key-value로 이루어진 해시 테이블로, Object와 주로 비교된다.
탐색은 get(), 삽입은 set()으로 한다.
key 값은 고유한 값으로, 하나만 존재할 수 있으며, number, string, function, object, NaN이 자료형으로 사용된다.
set()을 이용해 value를 설정한다.

let map = new Map();

let testNumber = 1;
let testString = "string";
let testObject = { A: "a" };
let testFucntion = (B) => {
  B = "b";
};

map.set(testNumber, 1);
map.set(testString, 2);
map.set(testObject, 3);
map.set(testFucntion, 4);

console.log(map);
/*
Map(4) {
  1 => 1,
  'string' => 2,
  { A: 'a' } => 3,
  [Function (anonymous)] => 4
}
*/
// map의 형태

get()을 통한 value 가져오기

map.get(testNumber); // 1
map.get(testString); // 2
map.get(testObject); // 3
map.get(testFucntion); // 4

has()를 통한 value 찾기

map.has(testFucntion); // true
map.has(testNumber); // true

delete()를 통한 value 삭제

map.delete(testFucntion); // true
map.get(testFucntion); // undefined
map.get("none"); // undefined

size를 통한 value의 유무 확인

map.size; // 3
map.length; // undefined

for-of를 통한 hash 탐색

for (let [key, value] of map) {
  console.log(key, "=", value);
}
// 1 = 1
// string = 2
// { A: 'a' } = 3
// [Function: testFucntion] = 4
for (let key of map.keys()) {
  console.log(key);
}
// 1
// string
// { A: 'a' }
// [Function: testFucntion]
for (let value of map.values()) {
  console.log(value);
}
// 1
// 2
// 3
// 4
console.log(map.values());
// [Map Iterator] { 1, 2, 3, 4 }
console.log(map.keys());
// [Map Iterator] { 1, 'string', { A: 'a' }, [Function: testFucntion] }

4. 충돌(Collision)

받아온 key값에 대해 hash function으로 index를 지정하고 넣어주게 되는데, 이미 해당 index에 값이 존재하는 경우가 발생할 수 있으며 이를 collision이라고 한다.
해결을 위해서 대표적인 두 가지 방법이 존재한다.

Open Addressing
겹치는 해당 index의 옆 자리에 넣게 되는 방법이다.
이후에 해당 자리를 찾기 위해서 hash 값 index 이후부터 찾는 key값이 나올 때까지 찾는다.
Separate Chainining
Linked List를 이용해 다음 링크에 끼워넣는 방법이다.
이후 찾을 때에는 해당 링크를 타고 들어가면 된다.

참고 링크

JavaScript Map, Hashmap
전체적인 설명 : https://velog.io/@jun094/Hash와-Map
설명 동영상 : https://www.youtube.com/watch?v=HraOg7W3VAM
Hashmap 충돌 해결법
https://overcome-the-limits.tistory.com/entry/자료구조-해시테이블-with-JavaScript

Linux

Linux의 특징

유닉스 기반의 무료 오픈 소스 운영체제이며, 윈도우와 맥과 가장 구별되는 점으로 ‘오픈 소스’를 꼽을 수 있다.
커스터마이즈된 OS를 만들 수 있는 커널로, Linux 커널을 기반으로 하며, 커널은 운영 체제의 핵심이라고 할 수 있다. 즉, 이 커널로 자신의 운영 체제를 개발할 수 있다.
Linux 아키텍처는 커널, 시스템 라이브러리, 시스템 도구와 같은 구성 요소로 이루어진다.