[Data Structure] Hash Table

슬지로운 개발생활·2020년 12월 8일

data structure

Data Structure

목록 보기

1/3

Hash Table

해시 테이블(해시 맵)은 키, 값 쌍으로 저장하고 있는 자료구조다.
키를 저장할 때 키를 '해시 함수'를 통해 특정 숫자값의 인덱스로 변환한다
→ 메모리 공간을 덜 사용한다
해시 테이블은 필요할 때만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

Hashing(해싱)

주어진 key를 다른 값(value)로 변환하는 과정
- 원래 데이터의 값을 키(Key), 매핑 후 데이터의 값을 해시 값(hash value), 매핑하는 과정 자체를 해싱(hashing)이라고 한다.
→ 매핑(Mapping) : 해당 값이 다른 값을 가리키도록 하는 것.
참조 :

Hash Function(해시 함수)

해시 함수(Hash Function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
Deterministic
```
x = y => h(x) = h(y)
```

해시함수의 3가지 특징

암호화 해시 함수(Cryptographic Hash Function)
해시 함수의 일종으로 해시 값으로부터 원래의 입력값과의 관계를 찾기 어려운 성질을 가지는 경우를 의미

역상 저항성(preimage resistance)
해시 값이 주어졌을 때, 그 해시 값을 생성하는 입력값을 알아내기가 불가능하다는 특성
→ 입력값 A에 의해 B가 출력되었다면, 출력된 B만 주어졌을 때 입력값인 A값을 찾는 것이 계산적으로 불가능하다
제 2 역상 저항성(second preimage resistance)
어떤 입력 값과 동일한 해시 값(결과 값)을 가지는 다른 입력 값을 찾을 수 없어야 한다는 특성
→ 입력값 A와 출력값 B가 모두 주어졌을 때, 똑같은 B를 반환하는 A2를 찾아내거나 만들어내는 것이 계산적으로 불가능함을 의미
충돌 저항성(collision resistance)
해시 값(결과 값)이 같은 입력 값 두개를 찾을 수 없다는 특성,
충돌저항성은 제 2 역상 저항성의 외부효과(부수효과, Side effect)이자 부분집합이다.
→ 똑같은 B라는 출력값이 나오는 X가 단일하지 않고, 중복이 되는 또다른 Xn을 발견하는 것이 계산적으로 어려운 성질을 의미
참조 :

Hash Collision(해시 충돌)

해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미
해시 함수가 무한한 가짓수의 입력 값을 받아 유한한 가짓수의 출력 값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.
→ 두 개 이상의 key가 동일한 hash값을 갖는 경우 : '충돌이 발생했다'라고 한다.
같은 해시를 갖는 데이터가 생긴다는 것은 특정 키의 버킷(bucket)에 데이터가 집중된다는 뜻이다.
→ 그래서 너무 많은 해시 충돌은 해시 테이블의 성능을 떨어뜨린다.

해시 충돌 해결 방안

Chaining(체이닝)
- Closed Addressing
- 해시 충돌이 발생하면 키에 해당하는 데이터들을 연결하는 방식
1. 연결리스트(Linked List)를 사용하는 방식
  - 각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision이 발생하면 해당 버킷에 리스트를 추가하는 방식
  - 삭제 또는 삽입이 간단하다.
  - 작은 데이터들을 지정할 때 연결 리스트 자체의 오버헤드가 부담이 된다.
2. Tree (Red-Black Tree)를 사용하는 방식
  - 트리를 사용하는 방식은 메모리 사용량이 많다.
Open Addressing(개방 주소법)
- 해시 충돌이 일어나면 다른 버킷에 데이터를 저장하는 방식
1. 선형 탐색 : 해시 충돌시 다음 버킷에 저장하는 방법
2. 제곱 탐색 : 해시 충돌시 제곱만큼 건너 뛴 버킷에 데이터를 저장하는 방법
3. 이중 해시 : 해시 충돌시 다른 해시 함수를 한번 더 적용한 결과를 저장
- 장점 :
  - 체이닝처럼 포인터가 필요없고, 지정한 메모리 외에 추가적인 공간이 필요 없다.
  - 삽입 삭제시 오버헤드가 적다
- 단점 :
  - 최악의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다.
  - 특정 위치에만 데이터가 몰리는 현상이 나타날 수 있다.
Resizing(리사이징)
- 해시 테이블 안의 데이터(tuple)의 비율이 storage의 길이(크기)의 25% 에서 75% 정도 존재할 때 효과적으로 운영된다.
- 테이블에 할당된 공간을 다 사용해서, 더 이상 사용할 수 있는 공간이 없을 때 행하는 방법
- 테이블의 크기를 늘려준 다음에 기존의 데이터를 다시 해시 함수로 보내서 다시 재정렬한다.

해시 테이블 용어

이미지	설명
	Storage : 데이터를 저장하는 공간 배열 형태
	Bucket : 데이터가 들어갈 공간 버켓은 storage[index]에 담겨있다.
	Tuple : 데이터를 담고 있는 곳(key, value를 같이 가지고 있다)

Property

_size : 저장된 key-value 쌍의 갯수
_bucketNum : 해시 테이블의 스토리지 배열의 길이 지정
_storage : LimitedArray(_bucketNum)을 사용해 배열 생성

Method

insert(key, value) : key, value 저장, key값이 있다면 덮어씌운다.
retrieve(key) : 주어진 키에 해당하는 값을 반환, 없다면 undefined반환
remove(key) : 주어진 키에 해당하는 값을 삭제하고 값을 반환, 없다면 undefined 반환
_resize(newBucketNum) : 해시 테이블의 스토리지 배열을 newBucketNum으로 리사이징하는 함수
- 해시 테이블에 저장된 key-value 쌍이 bucketNum의 75%를 넘는 경우 bucketNum을 2배로 늘린다
- 25%보다 작아지는 경우 bucketNum을 절반으로 줄인다.
- 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 한다.

Pseudocode

// LimitedArray에 포함된 get, set 메소드(?)를 쓰지 않고 배열을 사용한 방식이다.

// 외부 폴더에서 준비되어 있는 해시 함수 (hashFunction) 가져온다.
// 외부 폴더에서 배열의 크기를 제한시키 위한 함수(LimitedArray)을 가져온다.
// ↑ 자바스크립트의 배열은 크기가 제한되어 있지않은 동적 배열이다.

class HashTable {
  constructor() {
    this._size = 0;
    this._bucketNum = 8;
    this._storage = LimitedArray(this._bucketNum);
  }

  insert(key, value) {
    const index = hashFunction(key, this._bucketNum);
    // 해시값을 만드는 해시 함수

    // 만약 this._storage[index]값이 없다면
      // this._storage[index] 에 [[key, value]]를 할당해준다
      // this._size++;
    // 그 외에는
      // false를 할당한 isKey변수(키가 인덱스에 있는지 확인 후 value 재할당 용도) 선언
      // 포문으로 this._storage[index]의 tuple확인
        // 만약 this._storage[index][i][0] 가 키랑 같으면
          // this._storage[index][i][1]에 value를 재할당
          // key가 있으니 isKey변수를 true로 재할당
      // 만약 isKey변수가 false면 (key, value는 새로 들어온 값이므로)
        // this._storage[index]에 [key, value]를 푸시한다.
        // this._size++
   
    // 만약 this._size가 this._bucketNum의 75% 보다 작으면
      // this._bucketNum를 2배로 늘려 this._resize함수의 인자값으로 넘겨 호출한다.
  }

  retrieve(key) {
    const index = hashFunction(key, this._bucketNum);
    // const arrIdx = this._storage[index].findIndex(el => el.includes(key));
    // ↑ this._storage[index]의 요소가 key를 포함하고 있다면 인덱스 값을, 없다면 -1을 저장하는 변수 선언
    // 만약 arrIdx가 -1보다 크면
      // return this._storage[index][arrIdx][1];
  }

  remove(key) {
  // 중요!! remove메소드를 실행하면 지운 값을 반환하게 만들었다. → 반환하지 않아도 된다면 더 간단하게 풀 수 있다...

    // this._size--;

    // 만약 this._size가 this._bucketNum의 25% 보다 크면
      // this._bucketNum를 절반으로 줄여 this._resize함수의 인자값으로 넘겨 호출한다.

    const index = hashFunction(key, this._bucketNum);
    // retrieve에서 선언했던 arrIdx 똑같이 만들어준다.(key가 포함된 tuple의 인덱스를 얻기 위해)

    // 만약 arrIdx가 -1보다 크면
      // return this._storage[index].splice(arrIdx, 1);
    // 그 외에는(arrIdx가 -1인 상태 = this._storage에 key가 없다)
      // this._size++;
      // 만약 this._size가 this._bucketNum의 75% 보다 작으면
        // this._bucketNum를 2배로 늘려 this._resize함수의 인자값으로 넘겨 호출한다.
      // return undefined;  
  }

  _resize(newBucketNum) {
    // 모든 키값이 저장된 this._storage에 새로운 값을 재할당하기전에 새로운 변수에 할당해준다.
    // ↑ (원래 값을 this._storage의 크기를 변경 후 해싱하기 위해)

    // 초기화 해주는 작업을 한다.
    // this._size는 0으로 재할당
    // this._bucketNum은 인자로 받아온 newBucketNum 재할당
    // this._storage = LimitedArray(this._bucketNum);

    // 포 인으로 originStorage(객체형태)에서 index를 가져온다.
      // 만약 originStorage[index]가 배열이라면 → limitedArray에 get, set, each메소드가 있기 때문에
        // 포 오브로 originStorage[index]에서 arrIdx(tuple이라고 생각하면된다)
          // this.insert(...arrIdx);
  }
}

슬지로운 개발생활

다음 포스트

[Data Structure] Hash Table

Data Structure

Hash Table

Hashing(해싱)

Hash Function(해시 함수)

해시함수의 3가지 특징

Hash Collision(해시 충돌)

해시 충돌 해결 방안

해시 테이블 용어

Property

Method

Pseudocode

[Data Structure] Linked List

0개의 댓글