ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 해시(Hash)와 해시 충돌 해결 방법
    CS(Computer Science)/Data Structure 2021. 11. 26. 16:08
    728x90

    1. 해시란?

    💡 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑
    • 해시 함수: 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다.
    • 해시 테이블: 키와 값을 매핑해둔 데이터 구조이다. 해시 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장하여 효율적인 검색을 위해 사용된다.

    1-1. 해시 순서

    1. 해당 원소의 해시 함수를 이용하여 해시값을 얻는다.
    2. 해시값을 주소로 하는 위치에 원소를 저장한다.
    3. 저장 후 검색 시에도 원소의 해시값으로 계산하여 해당 위치로 이동한다.

    1-2. 사용 용도

    1. 무결성 검사: 파일 다운로드 시 문제가 없는지 확인하는 용도로 다운로드하는 파일이 일부라도 변경된 경우 Checksum 값이 크게 달라진다.
      • 예시 : WebStrom 다운로드 파일 체크섬 확인하여 일치하는지 볼 수 있다. WebStrom에서 제공하는 해시 값과 일치하면 정상적으로 다운된 것을 알 수 있다. 
        맥 환경에서 체크썸 예시
    2. DB 비밀번호 저장
    3. 해시 테이블 사용

    2. Direct Addressing Table

    먼저 가장 간단한 형태의 해시테이블로 이름 뜻대로 키 값을 주소로 사용하는 테이블을 말한다. 크기가 U인 테이블 T를 생성하고 key k를 slot key에 저장하는 방식이다. 해당 테이블은 중복되는 키가 없다고 가정한다. 이는 삽입, 삭제, 검색 모두 O(1)이지만, 모든 키를 넣어야 하기 때문에 공간 낭비가 심하다. 예를 들어 모든 학생들에게 한 자리씩 할당해 준 것이다.

    이러한 형태의 테이블은 키 값들이 골고루 분포되어있지 않다면 메모리 낭비가 심할 수밖에 없다. 또한 최대 키값이 작을 때 실용적으로 사용된다. 이러한 공간 낭비 문제로 Hash Table를 사용하게된다.

    Direct Addressing Table


    3. Hash Table

     key k를 저장할 때 slot k를 저장하는 것이 아니라 slot h(k)에 저장한다. key k가 slot h(k)로 해시되었다고 하며, h(k)를 key k의 해시값이라고 부른다. 이때 h( )는 해시 함수라고 부른다.

    Hash Table은 Direct Addressing Table와 다르게 U 만큼의 테이블을 생성하지 않아도 되어 공간 낭비는 줄인다. 그러나 충돌 문제가 있다. 아래 그림에서는 h(k2) = h(k5) 부분이 충돌이 났다.

    시간 복잡도는 삽입, 삭제, 검색 모두 O(1)이다.

    Hash Table

     

    3-1. Hash Table 용어

    3-1-1. 충돌

    두 개의 다른 key가 동일한 hash 값을 갖는 경우 "충돌이 발생했다"라고 한다. 충돌을 피하는 방법은 충돌이 적은 좋은 해시 함수를 사용하는 것이다. 아래에서 충돌을 해결하기 위한 Chaining과 Open Addressing 두 가지 방법을 알아보자.

    3-1-2. 로드 팩터

    로드 팩터란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k(테이블 크기)로 나눈 것이다. 로드 팩터의 비율에 따라서 해시 함수를 재작성해야 될지 또는 해시 테이블 크기를 조정해야 할지를 결정한다. 자바 10에서는 해시 맵 디폴트 로드 팩터를 0.75로 정하여 이를 넘는 경우 해시 테이블의 공간을 재할당한다.

    load factor = n/k

    3-2. 좋은 해시 함수

    좋은 해시 함수는 simple uniform hashing을 만족하는 함수이다. 이는 중복이 없이 확률적으로 슬롯에 골고루 나눠지는 것이다.

     


    4. 해시 충돌 해결 방법

    충돌을 해결하기 위한 Chaining과 Open Addressing 두 가지 방법을 알아보자.

    4-1. Chaining

    💡 충돌 시 연결 리스트에 추가하는 방식이다.

    Chaining

    중복된 해시 값이 있는 경우, 해당 슬롯을 연결 리스트로 저장한다. 이 방법은 연결 리스트로 인해 최악의 경우 수행 시간이 O(n)이 된다. 해시를 사용하는 이유는 O(1)이라는 장점으로 사용하는 것인데 O(n)이 된다면 문제가 된다. 이런 문제로 트리로 구성하여 더 시간 복잡도를 줄일 수도 있다.

    4-2. Open Addressing

    💡 충돌 발생 시 해시함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장한다.

     오픈 어드레싱은 충돌을 피하기 위한 다른 방법으로 key를 해시 테이블에 직접 저장한다. 오픈 어드레싱의 장점은 포인터를 사용하지 않아도 되어 구현이 간편하며, 검색도 미세하게 빨라진다.

    오픈 어드레싱은 총 3가지 종류가 있다. 각 종류의 특징을 알아보도록 하자.

    4-2-1. 선형 프로빙(Linear probing)

    선형 프로빙은 충돌이 발생할 경우 빈 slot이 나올 때까지 탐색 후, 빈 slot이 나오면 위치가 결정된다. 선형 프로빙은 아래와 같은 해시 함수가 사용된다. 여기서 k는 키, i는 충돌 횟수, h()는 해시 함수, m은 해시 테이블 크기를 의미한다.

     

    • 해시 삽입

    아래는 선형 프로빙에서 키를 삽입하는 수도 코드이다. NIL이 있으면 넣고, 아닌 경우 다음 칸으로 이동하는 것을 확인할 수 있다.

    • 해시 검색

    아래는 선형 프로빙에서 키를 검색하는 수도 코드이다. NIL이 아닐 때까지 계속 다음 칸으로 이동하면서 검색하는 것을 확인할 수 있다.

    • 해시 삭제

    값을 지우는 경우는 해당 slot에 "DELETED"라고 표시해야 한다. 왜냐하면 검색할 때 빈 slot이 있을 때까지 검색하기 때문에 빈 값으로 두면 그 이후를 검색이 안 되는 경우가 발생합니다. 따라서 "DELETED"와 같은 특정 값을 넣어 줘야 검색 시 문제가 없습니다.

    • 장단점

    선형 프로빙의 장점은 구현은 매우 쉬우나 primary clustering 문제가 있다. primary clustering는 한 번 충돌이 나면 집중적으로 충돌이 발생하는 것을 의미한다. 이로 인하여 평균 검색 시간이 증가한다.

     

    4-2-2. 이차식 프로빙(Quadratic probing)

    이차식 프로빙은 아래와 같은 해시 함수를 사용한다. i에 대한 2차 함수 꼴로 slot를 이동하면서 빈 slot를 찾는다.

    • h: 보조 해시 함수
    • c1, c2: 0이 아닌 상수

    • 장단점

    이차식 프로빙은 선형 프로빙에 비해 충돌이 적지만 secondary clustering이 발생한다. secondary clustering은 처음 충돌한 위치가 같다면 다음 충돌할 위치도 반복적으로 계속 충돌이 나게 된다는 의미이다.

     

    4-2-3 이중 해시(Double hasing)

    이중 해시는 다음과 같은 형태의 해시 함수를 사용한다. 충돌이 없을 때는 h1으로 위치를 탐색하고, 충돌이 있으면 h2 mod m 만큼 이동하면서 탐색한다.


    5. 언어별 해시 충돌 해결 방법

    chaining vs Linear probing

     파이썬에서 해시 테이블로 구현된 자료형은 딕셔너리다. 그렇다면 파이썬의 해시 테이블은 충돌 시 어떤 방식을 사용할까? 파이썬에는 오픈 어드레싱 방식으로 구현되어 있다. C언어로 구현된 파이썬에서 오픈 어드레싱 방식을 사용한 이유는 체이닝 시 malloc으로 메모리 할당하는 오버헤드가 높아서 오픈 어드레싱을 선택했다고 한다.

    오픈 어드레싱 방식은 체이닝에 비해 성능이 좋다. 하지만 슬롯이 80% 이상 차게 되면 급격하게 성능 저하가 일어나며, 체이닝과 달리 로드 팩터 1 이상은 저장할 수 없다. 따라서 파이썬은 오픈 어드레싱 방식을 택해 성능을 높이지만 로드 팩터를 작게 잡아 성능 저하 문제를 해결한다. 파이썬 로드 팩터는 0.66으로 설정되어 있다.

    그 외 언어는 아래 링크로 사용하는 이유를 파악할 수 있다.

    언어 방식 
    C++ 개별 체이닝 
    Java 개별 체이닝 
    Go 개별 체이닝 
    Ruby 오픈 어드레싱 
    Python 오픈 어드레싱 

    참고

    Introduction to Algorithms - 3rd Edition


    면접 질문

    1. hashtable에 대해 설명하시오
    2. hashtable의 collision이 발생할 경우 해결방법을 설명하시오
    3. 특정 언어 hashtable 충돌 해결 방법에 대해 설명하시오

    댓글

Designed by Tistory.