[자료구조/알고리즘] 해시(Hash) 란?

Hash

개념

• 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것

• 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array 이다

• 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이때 사용하는 함수(알고리즘)를 해시함수 라고 한다

• 해시값 자체를 index로 사용하기 때문에 평군 시간복잡도가 O(1) 로 매우 빠르다

해시함수

• 위에 설명한 것과 같이 키에 대한 해시값을 만드는 함수

• 계산이 복잡하지 않고 키값에 대해 중복없이 해시값을 고르게 만들어 내는 함수가 좋은 함수 (충돌이 일어나지 않을수록 좋다)

• 대표적으로 나눗셈법(Division Method)와 곱셉법(Multiplication Method)이 있다

• 나눗셈법:
• 원소를 해시테이블의 크기로 나누어 나머지값을 테이블의 주소로 사용하는 방법
• 테이블의 크기보다 원소의 갯수가 많으면 충돌이 일어난다

ex) 해시테이블의 크기가 8일때 

Collision

• 키에 대한 해시값이 같은 경우 = 사용하고자하는 해시 버킷이 이미 사용중인 경우

• 충돌 해결을 위해

  • Chaining

    • 충돌이 일어날 경우 데이터들을 포인터를 이용해 서로 링크드 리스트(체인)형태로 연결하는 것

    • key값을 포인터로 이어서 연결

    • 최악의 경우 모든 데이터가 같은 해시값을 가져 O(n)의 복잡도를 가짐

    • JDK 라이브러리에 구현된 HashMap 은 chaining 방식을 사용하며 해당 버킷의 길이에 따라 LinkedList에서 Tree로 변경될수 있다

  • Open Addressing

    • 모든 데이터를 테이블에 저장하는 방법

    • 사용하려는 해시 버킷(테이블)이 이미 사용중인 경우 다른 버킷을 사용

    • 포인터를 쓰지 않아 오버헤드를 방지할 수 있고 데이터가 적을 경우 연속된 공간에 인자를 저장하기 때문에 공간 효율이 높다

    • 하지만 테이블의 크기가 커질수록 장점이 사라진다

    • Linear Probing

      • 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식 다음으로 이동한 이후에도 충돌이 발생했다면 또 다시 바로 다음인덱스에 저장

    • Quadratic Probing

      • 충돌시 i^2 만큼씩 이동