해시 테이블(Hash Table)

해시 테이블(Hash Table)

키, 값을 대응시켜 저장하는 데이터 구조로 키를 통해 해당 데이터에 빠르게 접근 가능

해싱

키를 특정 계산식에 넣어 나온 결고를 사용하여 값에 접근하는 과정

해시 테이블 구조

키 : 해시 테이블 접근을 위한 입력 값

해시 함수 : 키를 해시 값으로 매핑하는 연산

해시 값 : 해시 테이블의 인덱스

해시 충돌

해시 함수를 통한 해시 값이 동일한 경우 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우

해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있다.

해시 충돌 해결 방법

개방 주소법(Open Address)

• 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장
• hash와 value가 1:1 관계 유지 (해시 키는 하나의 데이터만 가지고 있다.)
• 비어 있는 공간 탐색 방법에 따라 분류된다.
  • 선형 탐사법, 제곱 탐사법, 이중 해싱

선형 탐사법(Linear Probing)

• 빈 공간을 순차적으로 탐사하는 방법
  • 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사
• 일차 군집화 문제 발생 - 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생

public void setValue(int key, int data) {
  int idx = this.getHash(key);
​
  if (this.elemCnt == this.table.length) {
    System.out.println("Hash table is full");
  } else if (this.table[idx] == null) {
    this.table[idx] = data;
    this.elemCnt++;
  } else {
    int newIdx = idx;
    // 키 값이 중복이라면
    // "(기존 키 값에 + 1) % 테이블 길이"의 값으로 증가하면서 비어있는 공간 탐색
    do {
      newIdx = (newIdx + 1) % this.table.length;
    } while (this.table[newIdx] != null);
    this.table[newIdx] = data;
    this.elemCnt++;
  }
}

제곱 탐사법(Quadratic Probing)

• 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법
• 일차 군집화 문제 일부 보완
• 이차 군집화 문제 발생 가능성

public void setValue(int key, int data) {
  int idx = this.getHash(key);
​
  if (this.elemCnt == this.table.length) {
    System.out.println("Hash table is full");
    return;
  } else if (this.table[idx] == null) {
    this.table[idx] = data;
    this.elemCnt++;
  } else {
    int newIdx = idx;
    int count = 0;
    // 키 값이 중복이라면
    // "(기존 키 값에 + 2^count) % 테이블 길이"의 값으로 증가하면서 비어있는 공간 탐색
    while (true) {
      newIdx = (newIdx + (int)Math.pow(2, count)) % this.table.length;
      if (this.table[newIdx] == null) {
        break;
      }
      count++;
    }
    this.table[newIdx] = data;
    this.elemCnt++;
  }
}

이중 해싱(Double Haching)

• 해싱 함수를 이중으로 사용
  • 최초 해시를 구할 때
  • 충돌 발생 시, 탐사 이동 간격을 구할 때
• 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포

public void setValue(int key, int data) {
  int idx = this.getHash(key);
​
  if (this.elemCnt == this.table.length) {
    System.out.println("Hash table is full");
    return;
  } else if (this.table[idx] == null) {
    this.table[idx] = data;
    this.elemCnt++;
  } else {
    int newIdx = idx;
    int count = 0;
    // 키 값이 중복이라면
    // "(기존 키 값에 + hash) % 테이블 길이"의 값으로 증가하면서 비어있는 공간 탐색
    while (true) {
      newIdx = (newIdx + this.getHash2(newIdx) * count) % this.table.length;
      if (this.table[newIdx] == null) {
        break;
      }
      count++;
    }
    this.table[newIdx] = data;
    this.elemCnt++;
  }
}
​
//2번째 해쉬 값에 사용되는 c값은 해쉬 테이블의 사이즈에 가장 가까운 소수가 효율적이다.
public int getHash2(int key) {
  int hash = 1 + key % this.c;
  return hash;
}
​
// 테이블의 사이즈에 가장 가까운 소수 구하기
//this.c == getHashC(int size)
public int getHashC(int size) {
  int c = 0;
​
  if (size <= 2) {
    return size;
  }
​
  for (int i = size - 1; i > 2; i--) {
    boolean isPrime = true;
    for (int j = 2; j < i; j++) {
      if (i % j == 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      c = i;
      break;
    }
  }
  return c;
}

분리 연결법(Separate Chaining)

• 해시 테이블을 연결 리스트로 구성
• 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결 -> 1:n 관계 (충돌된 해시 키값에 여러 데이터를 가지게 된다.)

== hash table ==
0 : List is empty
1 : 10 11 12 13 
2 : 20 21 22 23 
3 : 30 
4 : List is empty