해시와 해시 충돌

 

해시 (Hash) 

• key, value 쌍으로 이루어진 데이터 구조 
• 키를 이용해 값을 O(1) 시간 복잡도로 찾을 수 있다.

 

해시 충돌 (Hash Collision)

• 다른 key를 사용해도 같은 결과가 나오는 경우를 해시 충돌이라고 한다.
• 해시 충돌을 완화하기 위한 접근 방법
  • 개방 주소법
  • 분리 연결법

 

개방 주소법 (Open Addressing)

• 특정 값이 들어가야하는 자리(버킷)가 이미 사용되고 있는 경우, 다른 빈 공간을 탐색하여 버킷에 데이터를 삽입한다.
• 대표적인 3가지 방식이 있다.
  • 선형 탐사 (Liner Probing)
    • 고정된 크기만큼 한 칸씩 옮기면서 빈 버킷을 찾는 방법
    • 해시 자료 구조 전체에서 해시 충돌이 균등하게 발생하는 경우 유리한 탐색법이다.
    • 구현이 간단하고 캐시 적중률이 높으나 특정 버킷 주변이 모두 채워져 있는 경우, 성능이 저하될 수 있다. (클러스터링=군집화 문제) 
    • 충돌 시 index+1, index+2 ... 순차적으로 탐색
    • 충돌: h(k), 다음 h(k)+1, h(k)+2 ...
  • 제곱 탐색 (Quadratic Probing) 
    • 한 칸씩 찾는 것이 아닌, 제곱만큼 늘리면서 빈 버킷을 찾는다.
    • 점점 늘어나기 때문에 선형 탐색처럼 특정 영역에 값이 밀집되어 저장되어도 해당 영역을 빠르게 벗어날 수 있다.
    • 선형탐사에 비해 군집화가 감소되나 여러 값이 해시 함수로 같은 값을 갖게될 경우, 모두 같은 순서로 탐사하기 때문에 충돌이 많으면 공간이 낭비된다. 
    • index+1^2, index+2^2, index+3^2 ...
      • 덜 밀집되게 분포되도록
  • 이중 해시 (Double Hashing)
    • 보조 해시 함수를 사용하는 방법
    • 충돌 분산, 충돌 가능성이 가장 낮지만 추가 보조 해시 함수를 사용하여 연산이 발생하고 구현이 복잡하다.
    • h(k, i) = (h1(k) + i * h2(k)) % tableSize
      • 더 넓은 범위로 분산 가능

 

분리 연결법 (Seprate Chaining)

• 버킷 내에 연결 리스트(Linked List)를 할당하여, 버킷에 데이터를 삽입하다가 해시 충돌이 발생하면 연결 리스트로 데이터들을 연결하는 방식
  • 충돌 시 동일한 인덱스에 연결리스트로 저장
• 버킷을 연결 리스트나 트리 형태로 관리하여 버킷에 들어갈 값의 수에 제한을 두지 않도록 하여 충돌을 완화한다.

 

개방 주소법의 장점

• 포인터가 필요 없고, 저장한 메모리 외의 추가 공간이 필요하지 않다.
• 삽입/삭제 시 오버헤드가 적다
• 저장할 데이터가 적은 경우에 유리

 

분리 연결법의 장점

• 연결 리스트만 사용하면 된다 = 개방주소법에 비해 복잡한 계산식을 사용할 필요가 적다.

 

 

아래는 선형 탐사 예제 🙂

package hashCollision;

public class OpenAddressingHashTable {

    // 선형 탐사 예제

    private Integer[] table;
    private int size;

    public OpenAddressingHashTable(int size) {
        this.size = size;
        this.table = new Integer[size];
    }

    private int hash(int key) {
        return key % size;
    }

    public void insert(int key) {
        int index = hash(key);
        int startIndex = index;

        while (table[index] != null) {
            index = (index + 1) % size;
            if(index == startIndex) throw new RuntimeException("Table is full");
        }

        table[index] = key;
    }

    public boolean search(int key) {
        int index = hash(key);
        int startIndex = index;

        while (table[index] != null) {
            if(table[index].equals(key)) return true;
            index = (index + 1) % size;
            if(index == startIndex) break;
        }

        return false;
    }

    public void showTable() {
        for(int i=0; i<size; i++) {
            System.out.println(i + ": " + table[i]);
        }
    }

    public static void main(String[] args) {
        OpenAddressingHashTable hashTable = new OpenAddressingHashTable(7);

        hashTable.insert(10);
        hashTable.insert(24);
        hashTable.insert(17);

        hashTable.showTable();
    }
}