Data Structure - Hash Table

Jung Hyun Kim·2022년 7월 27일

Data Structure(자료구조)

목록 보기

4/5

Hash

데이터 관리 유지 구조
리소스 < 속도

HashTable?

데이터를 해시함수 를 거쳐서 인덱스와 값으로 나누게 하는 자료구조이다.
해시테이블의 첫번째는 인덱스, 키 (버킷), 두번째는 해시 값, 벨류(엔트리) 라고 한다.

Hash table 과 array의 차이점
```
메뉴로 구분을 해보자면  arrray는 아래와 같고, 
```

	menu = [{name : "coffee", price: 1},{name : "juice", price: 2},{name : "milk", price: 3}]

	hash table은 이런 형태일 것이다.

	 menu = { "coffee": 1,"juice": 2,"milk": 3}

time complexity를 비교하면 array 는 길이가 길어질수록 오래걸리는 O(n), 해시테이블은 항상 O(1)걸리기 때문에 아이템을 추가하거나 빼더라도 O(1)기때문에 시간을 매우 절약 가능하다.
결국 javaScript에서는 object라는 이름으로 우리가 어떻게 활용하나의 차이라고 볼수 있음.

hash table의 가장 큰 단점 => 해시충돌(collision)

기존에 만든 해시함수를 통해 key를 만들어 그 key값을 인덱스로 저장하는데, 중복된 key가 전달될경우 해시 충돌이 일어난다.

해결방법?

Chaining
- 리스트 공간에 다른 배열을 value에 저장해서 선형 검색으로 찾는 것(linear search)
- 이렇게 되면 시간복잡도는 0(1)이 아니라 더 복잡해 질 수 도 있다.

JavaScript에서의 hash table

Object나 Map은 key-value pair을 저장함으로서 hash table structure를 가진다

const collection = new Map();

collection.set("Nathan", "555-0182");
collection.set("Jane", "555-0182");

console.log(collection.get("Nathan")); // 555-0182
console.log(collection.size); // 2

Map은 object 와는 다르게 set() get()을 통해 데이터를 업데이트하고 가져올수있다.
object 처럼 추가도 불가능하다

collection["size"] = false;

console.log(collection.get("size")); // undefined

실제 JavaScript에서 어떻게 hash table class 를 사용할 수 있을까?

먼저 hash table class를 만들고 입력될 데이터의 크기를 정해준다

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }
}

해시함수를 추가해 각각의 key가 indexing되도록 한다
- 간단하게 character의 ASCII code로 key를 정해주어 겹치는 걸 막고 이름은 _로 정해 private하다는걸 명시한다.
- 127까지 table크기를 정했으므로 hash함수는 0 ~ 127의 숫자(index)를 return 한다.

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash;
}

*127 을 넘지 않기 위해서는 아래와 같은 모듈러 operator 추가해준다.

_hash(key) {
 let hash = 0;
 for (let i = 0; i < key.length; i++) {
   hash += key.charCodeAt(i);
 }
 return hash % this.table.length;
}

set() get() remove() 메서드를 통해 key/value pairs 를 추가하거나 삭제하거나 가져오게한다


  set(key, value) {
    const index = this._hash(key);
    this.table[index] = [key, value];
    this.size++;
  }

  get(key) {
    const target = this._hash(key);
    return this.table[target];
  }

  remove(key) {
    const index = this._hash(key);

    if (this.table[index] && this.table[index].length) {
      this.table[index] = [];
      this.size--;
      return true;
    } else {
      return false;
    }
  }
}