[자료구조] 해시

[자료구조] 해시

 

1. 해시

• 데이터를 빠르게 추가하거나 제거하도록 하는 데이터 구조
• 키(key)와 값(value)를 가지고 있음 → 키가 주어지면 평균 O(1)의 속도로 값을 찾을 수 있음

2. 해시함수

• 속도가 빠름
• 데이터의 속성
• 두개가 같으면 같은 값을 반환해야 함
• 동일한 상황일 때 항상 같은 값을 반환해야 함
• 새로 실행하면 객체가 같아도 다른 값이 나올 수 있음 → 객체들은 실행할 때마다 다른 주소에 저장되기 때문
• 충돌(collison)이 발생하지 않도록 만들어야 함
  • 충돌: 서로 다른 값을 가진 키가 일치하는 경우
    • 해시의 크기를 홀수로 설정(% 연산으로 다양한 값이 나오게 함)
    • 해시의 크기를 소수로 설정
• 해시 함수의 반환 값을 hashcode라고 함 → 해시 테이블의 인덱스를 결정
  • 해시코드는 최대한 키 전체를 참조하여 만들어야 함.

 

2.1 문자열을 hashCode로 바꾸는 예

• ex) 간단한 버전
  • 상수 g를 정의해서 문자의 위치만큼 제곱한 뒤 각 문자의 유니코드 숫자에 곱하여 나타낸다.

public int hashCode(String s) {
    int g = 31;
    int hash = 0;
    // 문자열을 숫자로 나타내기
    // 상수 g를 문자의 위치만큼 제곱한 뒤 곱합니다.
    for (int i = s.length() - 1; i >= 0; i--) {
            hash = g * hash + s.charAt(i);
  }
    return hash;
}

• 실제로 해시 코드 연산을 하면 음수가 반환될 수도 있는데 음수는 배열의 인덱스가 될 수 없으므로 양수로 변환시켜야 한다.

  • int hashValue = data.hashCode(str);
    hashValue = hashValue & 0x7FFFFFFF;
    int tableIndex = hashValue % hashTableSize;

  •  

 

2.2 충돌을 막는 방법

• 개방 주소법(Open Address)
  • 선형 조사법(linear probing)
    • 채우려는 공간이 차있으면 비어있는 칸을 찾을때까지 옆으로 하나씩 밀어서 데이터를 입력하는 방법
    • 만약, 인덱스 배열 크기를 벗어나면 % 연산을 통해 인덱스의 값을 줄여야 한다.
    • 위치가 바뀌었다는 사실을 알아야 함
  • 2차식 조사법(quadratice probing)
    • 채우려는 공간이 차있으면 1부터 순서대로 제곱한 옆으로 움직여 빈칸을 찾아 데이터를 입력하는 방법
    • 만약, 인덱스 배열 크기를 벗어나면 % 연산을 통해 인덱스의 값을 줄여야 한다.
    • 위치가 바뀌었다는 사실을 알아야 함
  • 이중 해시
    • 두 개의 해시함수를 사용
      • 두번째 해시 함수는 첫번째 함수와 달라야 하며 0을 반환하면 안됨
    • 첫번째 해시 함수를 이용하여 나온 해시 코드의 값을 인덱스로 사용
      • 만약, 배열이 비어있지 않으면 두번째 해시함수를 사용하여 값을 구한뒤, 먼저 구한 인덱스에 더해서 새로운 인덱스를 만들어 빈 공간을 찾음
    • 데이터를 좀 더 골고루 저장이 가능
• 분리 연결법(Separate Chaining)
  • 연결리스트를 사용한 체이닝
  • Tree를 사용한 체이닝(Red-Black Tee)

3. 연결리스트를 사용한 체이닝

• 배열에 연결리스트를 추가한 구조
• 해시코드 값이 같으면(충돌 발생) 같은 인덱스안에 연결리스트로 보관한다.
• 
• 테이블의 크기를 조절을 자주 안해도 됨 → 적재율($\lambda$)이 1보e다 크게 될 수 있다.
  • 한 체인에 데이터가 계속 쌓이면(해시 함수가 효율적이지 않으면) 데이터를 찾거나 제거하는데 O(n)의 시간이 필요

 

3.1 재해싱

• 적재율이 올라가면 해시의 검색 효율이 떨어지기 때문에 해시 테이블의 크기를 늘리고, 해시 테이블을 옮겨야 한다.

1. 크기가 2배인 배열을 만든다.
2. 해시 테이블의 있는 데이터들을 가지고 다시 해시 연산을 수행하여 새로운 인덱스를 얻어서 데이터를 옮긴다.
   • 기존 해시 테이블의 인덱스를 그대로 사용하면 데이터를 찾가서 제거할 때 문제가 발생

 

3.2 구현

// 해시 클래스
public class Hash<K, V> implements HashI<K, V> {
    class HashElement<K, V> implements Comparable<HashElement<K, V>> {
        // 키와 값 정의
        K key;
        V value;

        public HashElement(K key, V value) {
            this.key = key;
            this.value = value;
        }

        // compareTo 함수
        public int compareTo(HashElement<K, V> o) {
            return (((Comparable<K>)this.key).compareTo(o.key)); //키가 같을때(다른거여도 가능)
    }
    }

    // 변수
    int numElements;
  int tableSize;
    double maxLoadFactor;
    LinkedList<HashElement<K, V>> [] hashArray;

  public Hash(int tableSize) {
    this tableSize = tableSize;
    hashArray = (LinkedList<HashElement<K, V>>[]) new LinkedList[tableSize];

    for (int i = 0; i < tableSize; i++) {
      hashArray[i] = new LinkedList<HashElement<K, V>>();
    }
    maxLoadFactor = 0.75;
    numElements = 0;
  }
}

//추가 메서드(순서 보장 안됨)
public boolean add(K key, V value) {

  if (loadFactor() > maxLoadFactor) {
    resize(tableSize * 2);
  }

  HashElement<K, V> hashElement = new HashElement(key, value);
  int hashValue = key.hashCode();
  hashValue = hashValue & 0x7FFFFFFF;
  hashValue %= tableSize;

  hashArray[hashValue].add(hashElement);
  numElements++;

  return true;
}

//삭제 메서드
public boolean remove(K key) {

  int hashValue = key.hashCode();
  hashValue &= 0x7FFFFFFF;
  hashValue %= tableSize;

  hashArray[hashValue].remove(/*구현이 필요할수도 있음*/);
  numElements--;

  return true;
}

//값을 찾는 메서드
public V getValue(K key) {
  int hashValue = key.hashCode() & 0x7FFFFFFF / tableSize;

  for (HashElement<K, V> hashelement : hashArray[hashValue]) {
    if (((Comparable<K>) key).compareTo(hashElement.key) == 0) {
      return hashelement.value;
    }
  }

  return null;
}

//테이블 크기 변경 메서드
public void resize(int newSize) {
  LinkedList<HashElement<K, V>[] newArray = (LinkedList<HashElement<K, V>>[]) LinkedList[newSize];

  for (int i = 0; i < newSize; i++) {
    newArray[i] = new LinkedList<HashElement<K, V>>();
  }

  for (K key : this) {
    V value = getValue(key);
    HashElement<K, V> hashElement = new HashElement<K, V>(key, value);
    int hashValue = key.hashCode() & 0x7FFFFFFF % newSize;
    newArray[hashValue].add(hashElement);
  }

  hashArray = newArray;
  tableSize = newSize;
}

---

※ 참조

• 자바로 구현하고 배우는 자료구조 - 네이버 부스트 코스
• Interview_Question_for_Beginner