[자료구조] 해시 ( Hash ) 테이블

 

      ●  해시 ( Hash )

        :   임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑한 값

        -  해시 함수를 통해 값을 얻을 수 있음

 

      ●  해시 함수

        -  키 값을 입력으로 받아 해시 테이블상의 주소 리턴

        -  입력 원소가 해시 테이블 전체에 고루 저장되어야 함

        -  계산이 간단해야 함

        1.  나누기 방법  =>  h(x) = x mod m  ( m은 해시 테이블 크기 )
        2.  곱하기 방법  =>  h(x) = ⌊ m( xA mod 1 ) ⌋ 
                                ( m은 아무렇게나 잡아도 상관 없음. 컴퓨터의 이진수 환경에 맞게
                                 2의 제곱수로 잡는 것이 자연스러움. 상수 A는 0.6180339887 이 적당 )

 

      ●  해시 테이블

        :  키와 값을 매핑(mapping)해 둔 자료 구조

        -  원소가 저장될 자리가 원소의 값에 의해 결정되는 구조
         ( 원소끼리 비교하여 자리를 찾는 것이 아니라 자신의 값이 자신의 자리를 바로 결정 )

        -  해시 테이블이 총 m개의 원소를 저장할 수 있다면 0 ~ m - 1의 주소 값을 가짐

        -  해시 테이블에 원소가 차 있는 비율이 해시 테이블의 성능에 매우 중요한 영향을 미침

        -  충돌 처리는 해시 테이블 이론의 핵심
         ( 충돌 ( Collision ) : 원소를 저장하려는 위치에 다른 원소가 이미 자리를 차지하고 있는 경우 )

        -  데이터가 순차적으로 저장되는 것이 아니라 테이블 전 영역에 걸쳐 고루 분포

        -  자료의 저장, 탐색에서 극단적인 효율 추구
         ( 이진 검색 트리는 저장, 검색 시 평균 Θ(logn) 시간 소요. 최악의 경우 Θ(n)이 걸림.
          그를 보완한 AVL 트리, 레드 블랙 트리는 최악의 경우에도 Θ(logn) 시간 소요.
          해시 테이블은 저장된 원소 수에 관계 없이 상수 시간 소요 추구 )

 

      ●  해싱 ( Hashing )

        -  해시 함수를 사용하여 주어진 값을 변환한 뒤, 해시 테이블에 저장하고 검색하는 기법

        -  해싱에 사용되는 자료구조는 배열(array)과 연결리스트(linked list)가 조합된 형태

 

출처 :  「쉽게 배우는 알고리즘」 책, 해시넷 사이트