해시

해시법

💬  해시법은 데이터를 저장할 위치를 간단한 연산으로 구하는 것으로, 검색뿐만 아니라 추가, 삭제도 효율적으로 수행할 수 있다.

💬  정렬된 배열에 새로운 값을 추가하기 위해서는 아래의 과정이 필요하다.

정렬된 배열에 데이터 추가

💬  배열의 키 값을 배열의 요솟수 13으로 나눈 나머지로 다시 나눈 나머지로 정리하면 아래와 같다.

키 값과 해시 값의 대응

💬  이렇게 표에 정리한 값을 해시 값이라고 하며, 해시 값은 데이터에 접근할 때 사용한다.

💬  해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열이 아래의 해시 테이블이다.

해시에 새로운 값(35)을 추가

💬  이제 배열에 새로운 값 35를 추가할 때, 다른 배열 요소들을 뒤로 옮기지 않아도 된다.

💬  이와 같이 키 값(35)를 가지고 해시 값(9)를 만드는 과정을 해시 함수라고 하며, 해시 테이블의 각 요소를 버킷이라고 한다.

 

충돌

💬  새로운 값 18을 추가하는 경우를 생각해보자.

💬  18을 13으로 나눈 나머지가 5이므로 저장할 버킷의 인덱스는 5이다.

💬  하지만, 아래 그림과 같이 키 값과 해시 값의 대응 관계가 반드시 1:1은 아닐수도 있기 때문에 저장할 버킷이 중복되는 충돌 현상이 발생한다.

해시이 추가할 때의 충돌

💬  충돌을 피하기 위하기 위한 아래의 두 가지 방법을 알아보자.

    ◽  체인법 : 같은 해시 값을 갖는 요소를 연결 리스트로 관리한다.

    ◽  오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.

 

체인법

💬  체인법은 같은 해시 값을 갖는 데이터를 쇠사슬 모양으로 연결 리스트에서 연결하는 방법으로, 오픈 해시법이라고도 불린다.

같은 해시 값을 갖는 데이터 저장하기

💬  배열의 각 버킷에 저장하는 값은 같은 해시 값을 갖는 노드를 연결한 리스트의 첫 번째 노드에 대한 참조이다.

 

버킷용 클래스 Node<K, V>

public class ChainHash<K, V> {
  // 해시를 구성하는 노드
  class Node<K, V> {
    private K key;            // 키 값
    private V data;           // 데이터
    private Node<K, V> next;  // 체인의 다음 노드에 대한 참조
    
    // 생성자
    Node(K key, V data, Node<K, V> next) {
      this.key = key;
      this.data = data;
      this.next = next;
    }
    
    // 키 값을 반환
    K getKey() {
      return key;
    }
    
    // 데이터를 반환
    V getValue() {
      return data;
    }
    
    // 키의 해시 값을 반환
    public int hashCode() {
      return key.hashCode();
    }
  }
  
  ...

💬  제네릭 클래스 Node<K, V>가 전달받는 매개변수의 자료형은 키 값의 자료형 K와 데이터의 자료형 V이다.

💬  필드 next에 대입되는 값은 체인에 있는 다음 노드에 대한 참조이다.

 

생성자 ChainHash

private int size;            // 해시 테이블의 크기
private Node<K, V>[] table;  // 해시 테이블

// 생성자
public ChainHash(int capacity) {
  try {
    table = new Node[capacity];
    this.size = capacity;
  } catch (OutOfMemoryError e) {
    this.size = 0;
  }
}

// 해시 값을 구함
public int hashValue(Object key) {
  return key.hashCode() % size;
}

💬  클래스 ChainHash<K, V> 생성자는 해시 테이블 용량(capacity)만큼 비어 있는 해시 테이블을 생성한다.

💬  생성자가 호출된 직후 배열 table의 모든 요소는 null을 참조한다.

💬  메모리 확보에 실패하면(OutOfMemoryError) size에 0을 넣는다.

 

키 값으로 요소를 검색하는 search 메서드

// 키 값 key를 갖는 요소의 검색 (데이터를 반환)
public V search(K key) {
  int hash = hashValue(key);   // 검색할 데이터의 해시 값
  Node<K, V> p = table[hash];  // 선택 노드
  
  while (p != null) {
    if (p.getKey().equals(key))
      return p.getValue();     // 검색 성공
    p = p.next;                // 다음 노드에 주목
  }
  return null;                 // 검색 실패
}

💬  알고리즘

    ◻  해시 함수가 키 값을 해시 값으로 변환한다.

    ◻  해시 값을 인덱스로 하는 버킷을 선택한다.

    ◻  선택한 버킷의 연결 리스트를 처음부터 순서대로 검색한다.

    ◻  키 값과 같은 값을 찾으면 검색 성공이며, 끝까지 스캔하여 찾지 못하면 검색 실패이다.

 

요소를 추가하는 Add 메서드

// 키 값 key, 데이터 data를 갖는 요소의 추가
public int add(K key, V data) {
  int hash = hashValue(key);     // 추가할 데이터의 해시 값
  Node<K, V> p = table[hash];    // 선택 노드
  
  while (p != null) {
    if (p.getKey().equals(key))  // 이 키 값은 이미 등록됨
      return 1;
    p = p.next;                  // 다음 노드에 주목
  }
  Node<K, V> temp = new Node<K, V>(key, data, table[hash]);
  table[hash] = temp;            // 노드를 삽입
  return 0;
}

💬  알고리즘

    ◻  해시 함수가 키 값을 해시 값으로 변환한다.

    ◻  해시 값을 인덱스로 하는 버킷을 선택한다.

    ◻  버킷이 가리키는 연결 리스트를 처음부터 순서대로 검색한다.

    ◻  키 값과 같은 값을 찾으면 키 값이 이미 등록된 상태이므로 추가에 실패한다.

    ◻  끝까지 스캔하여 찾지 못하면 리스트의 맨 앞 위치에 노드를 삽입한다.

💬  다음은 키 값 13과 46을 갖는 노드를 해시 테이블에 추가하는 예시이다.

 

요소를 삭제하는 remove 메서드

// 키 값 key를 갖는 요소의 삭제
public int remove(K key) {
  int hash = hashValue(key);       // 삭제할 데이터의 해시 값
  Node<K, V> p = table[hash];      // 선택 노드
  Node<K, V> pp = null;            // 바로 앞의 선택 노드
  
  while (p != null) {
    if (p.getKey().equals(key)) {  // 찾으면
      if (pp == null)
        table[hash] = p.next;
      else
        pp.next = p.next;
      return 0;
    }
    pp = p;
    p = p.next;                    // 다음 노드를 가리킨다.
  }
  return 1;                        // 그 키 값은 없다.
}

💬  알고리즘

    ◻  해시 함수가 키 값을 해시 값으로 변환한다.

    ◻  해시 값을 인덱스로 하는 버킷을 선택한다.

    ◻  버킷이 가리키는 연결 리스트를 처음부터 순서대로 검색한다.

    ◻  키 값과 같은 값을 찾으면 그 노드를 리스트에서 삭제한다. 그렇지 않으면 삭제에 실패한다.

 

해시 테이블의 모든 내용을 출력하는 dump 메서드

// 해시 테이블을 덤프
public void dump() {
  for (int i = 0; i < size; i++) {
    Node<K, V> p = table[i];
    System.out.printf("%02d  ", i);
    while (p != null) {
      System.out.printf("-> %s (%s)  ", p.getKey(), p.getValue());
      p = p.next;
    }
    System.out.println();
  }
}

💬  해시 테이블의 모든 요소에 대하여 다음에 오는 노드를 끌어당기면서 각 노드의 키 값과 데이터를 출력하는 작업을 반복한다.

 

오픈 주소법

💬  충돌이 발생했을 때 리해시를 수행하여 비어 있는 버킷을 찾아내는 방법으로, 닫힌 해시법이라고도 한다.

public class OpenHash<K, V> {
  // 버킷의 상태
  enum Status {OCCUPIED, EMPTY, DELETED};  // {데이터 저장, 비어 있음, 삭제 마침}
  
  // 버킷
  static class Bucket<K, V> {
    private K key;          // 키 값
    private V data;         // 데이터
    private Status stat;    // 상태
    
    // 생성자
    Bucket() {
      stat = Status.EMPTY;  // 버킷은 비어 있음
    }
    
    // 모든 필드에 값을 설정한다.
    void set(K key, V data, Status stat) {
      this.key = key;      // 키 값
      this.data = data;    // 데이터
      this.stat = stat;    // 상태
    }
    
    // 상태를 설정
    void setStat(Status stat) {
      this.stat = stat;
    }
    
    // 키 값을 반환
    K getKey() {
      return key;
    }
    
    // 데이터를 반환
    V getValue() {
      return data;
    }
    
    // 키의 해시 값을 반환
    public int hashCode() {
      return key.hashCode();
    }
  }
  
  private int size;                // 해시 테이블 크기
  private Bucket<K, V>[] table;    // 해시 테이블
  
  // 생성자
  public OpenHash(int size) {
    try {
      table = new Bucket[size];
      for (int i = 0; i < size; i++) {
        table[i] = new Bucket<K, V>();
      this.size = size;
    } catch (OutOfMemoryError e) {  // 테이블을 생성할 수 없음
      this.size = 0;
    }
  }
  
  // 해시 값을 구함
  public int hashValue(Object key) {
    return key.hashCode() % size;
  }
  
  // 재해시 값을 구함
  public int rehashValue(int hash) {
    return (hash + 1) % size;
  }
  
  // 키 값 key를 갖는 버킷의 검색
  private Bucket<K, V> searchNode(K key) {
    int hash = hashValue(key);     // 검색할 데이터의 해시 값
    Bucket<K, V> p = table[hash];  // 선택 버킷
    
    for (int i = 0; p.stat != Status.EMPTY && i < size; i++) {
      if (p.stat == Status.OCCUPIED && p.getKey().equals(key))
        return p;
      hash = rehashValue(hash);    // 재해시
      p = table[hash];
    }
    return null;
  }
  
  // 키 값 key를 갖는 요소의 검색 (데이터를 반환)
  public V search(K key) {
    Bucket<K, V> p = searchNode(key);
    if (p != null)
      return p.getValue();
    else
      return null;
  }
  
  // 키 값 key, 데이터 data를 갖는 요소의 추가
  public int add(K key, V data) {
    if (search(key) != null)
      return 1;                      // 이 키 값은 이미 등록됨
       
    int hash = hashValue(key);       // 추가할 데이터의 해시 값
    Bucket<K, V> p = table[hash];    // 선택 버킷
    for (int i = 0; i < size; i++) {
      if (p.stat == Status.EMPTY || p.stat == Status.DELETED) {
        p.set(key, data, Status.OCCUPIED);
        return 0;
      }
      hash = rehashValue(hash);      // 재해시
      p = table[hash];
    }
    return 2;                        // 해시 테이블이 가득 참
  }
  
  // 키 값 key를 갖는 요소의 삭제
  public int remove(K key) {
    Bucket<K, V> p = searchNode(key);    // 선택 버킷
    if (p == null)
      return 1;                          // 이 키 값은 등록되지 않음
    
    p.setStat(Status.DELETED);
    return 0;
  }
  
  // 해시 테이블을 덤프
  public void dump() {
    for (int i = 0; i < size; i++) {
      System.out.printf("%02d  ", i);
      switch (table[i].stat) {
        case OCCUPIED:
          System.out.printf("%s (%s)\n",
                         table[i].getKey(), table[i].getValue());
          break;
          
        case EMPTY:
          System.out.println("-- 미등록 --"); break;
        
        case DELETED:
          System.out.println("-- 삭제 마침 --"); break;
      }
    }
  }
}

요소 삽입

💬  다음은 새로운 값 18을 삽입하고자 할 때 충돌이 발생한 경우이며, 이때 리해시를 진행한다.

💬  리해시할 때의 해시 메서드는 자유롭게 설정할 수 있으며, 해당 예제에서는 키 값에 1을 더한 값을 13으로 나눈 나머지로 하자.

💬  위와 같이 빈 버킷을 만날 때까지 재해시를 여러 번 반복하므로 선형 탐사법이라고도 한다.

 

요소 삭제

💬  인덱스가 5인 값을 삭제하는 과정을 살펴보도록 하자.

💬  오픈 주소법에서는 아래와 같은 속성을 부여하여 상태 값을 지정하도록 한다.

    ◻  데이터 저장 속성값

    ◻  비어 있음 속성값(-)

    ◻  삭제 마침 속성값(★)

💬  따라서 5를 삭제하기 위해서는 5가 위치하는 곳에 삭제를 마쳤다는 상태 값을 저장한다.

 

요소 검색

💬  17을 검색하면 해시 값이 4인 버킷이 비어 있음이므로 검색 실패이다.

💬  18을 검색하면 해시 값이 5인 버킷이 삭제 마침이므로 리해시를 수행하며, 6인 버킷에는 6이 저장되어 있으므로 리해시를 수행하고, 7인 버킷에서 원하는 값 18을 찾을 수 있다.