[자료구조] 7주차 - 해시 (Hash)

Hash

해시란

• 자료의 크기에 상관없이 실시간에 탐색이 수행되어야 하는 경우
• O(1)의 탐색 시간을 추구하는 자료구조 및 알고리즘

정의 : 모든 키의 레코드를 산술 연산에 의해 한 번에 접근할 수 있는 기법

• 해시 함수(Hash function)
• 해시 인덱스(Hash index)
• 해시 테이블(Hash table)
• 충돌(Colision) & 충돌 해소(Collision resolution)

해시 함수

1. 자릿수 선택 (digit selection)
   • 키의 값 중에서 일부 자릿수만 골라내 인덱스를 생성하는 함수
   • h(8812152) = 8112
2. 자릿수 접기 (digit folding)
   • 키의 각각의 자릿수를 더해서 인덱스를 생성하는 함수
   • h(8812152) = 8+8+1+2+1+5+2 = 27
3. 모듈로 연산 (modulo function)
   • 키를 해시 테이블의 크기로 나눈 나머지를 인덱스로 생성하는 함수
   • h(KEY) = KEY mod TableSize
   • h(8812152) = 8812152%100 = 52

연산

해시 테이블 구조

• 단순한 경우 : 인덱스에 하나의 데이터만 저장
  • data_type hash_table[N]
• 복잡한 경우 : 인덱스에 k개의 데이터를 저장
  • data_type hash_table[N] [k]

검색

• 키 -> 해시 인덱스 -> 해시 테이블
• 단순한 경우

  • void search(data_type key){
      int index = hash_function(key);
      return hash_table[index];
    }

• 복잡한 경우 (?)

  • void search ( int index, data_type key ) { 
      int index = hash_function( key );
      return search_hash_table(index, key);
    }
    void search_hash_table(int index, data_type key){
      for(int i = 0; i<k; i++){
          if(hash_table[index] [i].key = key)
              return hash_table[index] [i];
      }
      return NULL;
    }

삽입

• 키 -> 해시 인덱스 -> 해시 테이블
• 단순한 경우

  • void insert(data_type data){
      int index = hash_function(data.key);
      hash_table[index] = data;
    }

• 복잡한 경우

  • void insert (data_type data){
      int index = hash_function(dta.key);
      insert_hash_table(index, data);
    }
    void insert_hash_table(int index, data_type data){
      for(int i = 0; i<k; i++){
          if(hash_table[index][i] == NULL){
              hash_table[index][i] = data;
              return;
          }
      }
    }

• 문제 발생 : 충돌 해소 필요
  • 인덱스에 이미 데이터가 존재하는 경우
  • 인덱스가 가득 찬 경우

  • if(collision(index))
          index = collision_resolution(index);

삭제

• 키 -> 해시 인덱스 -> 해시 테이블
• 단순한 경우

  • void remove(data_type key){
      int index = hash_function(key);
      hash_table[index] = NULL;
    }

• 복잡한 경우
  • 인덱스에 k개의 데이터를 저장하는 경우

  • void remove(data_type key){
      int index = hash_function(key);
      remove_hash_table(index, key);
    }
    void remove_hash_table(int index, data_type key){
      for(int i =0; i<k; i++){
          if(hash_table[index][i].key == key){
              hash_table[index][i] = NULL;
          }
      }
    }

연산의 시간 복잡도

• 검색 : O(k) -> O(1)
• 삽입 : O(k) -> O(1)
• 삭제 : O(k) -> O(1)

충돌 해소

충돌 : 서로 다른 키를 가진 레코드가 해시 함수에 의해 동일한 인덱스로 대응되는 현상

충돌 해소

• 충돌이 발생한 레코드를 다른 주소에 저장하는 기법
• 열린 어드레싱(open addressing)
  • 충돌이 발생한 레코드를 저장할 다른 주소를 찾는 방법
  • 레코드의 주소가 변경될 수 있기 때문에 열린 어드레싱이라 함
    • 선형 탐사 (linear probing)
    • 제곱 탐사(quadratic probing)
    • 이중 해시(double hash)
• 닫힌 어드레싱(closed addressing)
  • 충돌이 발생한 레코드를 동일한 주소에 저장하는 방법
    • 버켓(bucket)
    • 별도 체인(separate chain)

열린 어드레싱

• 선형 탐사(linear probing)
  • 충돌이 일어나면 그 다음 빈 곳에 원소를 저장 : h(key+1), h(key+2)
  • 배열의 끝을 만나면 다시 처음으로 되돌아와서 거기서부터 빈자리를 찾음
  • 태그(tag) : 선형 탐사에서 다음 원소를 가리키는 포인터
    • h(key)+1에 이미 다른 원소가 존재할 때
    • 중간의 원소를 삭제할 때
  • 단점 : 클러스터링(clustering) - 레코드가 분산되지 않고 군집되는 현상
    • tag를 계속 따라가면 O(n)이 될 수도 있음
• 제곱 탐사(quadratic probing)
  • 충돌이 일어날 때 조금 간격을 두고 저장 : h(key+1) h(key+2^2)
  • 궁극적으 클러스터링을 피할 수는 없음 - 2차 클러스터링
• 이중 해시(double hash)
  • 2차 클러스터링을 방지
  • 두 개의 해시 함수 h1, h2를 사용
    • h1 : 주어진 키로부터 인덱스를 계산하는 해시 함수
    • h2 : 충돌 시 탐색할 인덱스의 간격(Step Size)
  • h1 = key%13, h2 = 1 + key%11

열린 어드레싱은 모두 최악의 경우 O(n) 탐사를 할 수도 있는 건 마찬가지임

닫힌 어드레싱

• 버켓(bucket)
  • 해시 테이블의 각 원소들이 다시 여러 개의 원소로 이루어짐
  • 2차원 배열
  • 충돌되는 레코드를 하나의 인덱스에 둠
  • 단점 : 사용되지 않는 배열 공간이 낭비 됨
• 별도 체인(separate chain)
  • 해시 테이브르이 각 원소들이 연결리스트를 가리키는 헤드
  • 충돌이 일어날 때마다 해당 레코드를 연결리스트의 첫 위치에 삽입
  • 동적 구조(Dynamic Structure)