알고리즘 공부 - 해싱

안녕하세요. yeTi입니다.
오늘은 알고리즘 공부 중 해싱(hashing)에 대해 학습한 내용을 공유하려고 합니다.
강의 : 권오흠 교수님의 2015 봄학기 알고리즘

개요

해쉬 테이블(hash table)은 트리(tree)와 같이 dynamic set을 구현하는 효과적인 방법 중 하나입니다.

적절한 가정하에 Insert, Delete, Search 연산의 시간복잡도는 O(1)을 가지지만 최악의 경우에는 O(n)을 가집니다.

Hash Table

해시 테이블은 일반적으로 일차원 배열을 활용하여 데이터를 관리합니다.

이 때, 배열의 인덱스가 특정 데이터의 키를 해시한 값을 활용하여 키를 해시하는 연산 시간만 주어지면 데이터에 바로 접근할 수 있는 특징을 가지고 있습니다.

하지만, 데이터의 크기가 해시 테이블의 배열의 크기보다 크거나, 특정 데이터의 키를 해시한 값이 중복되었을 때는 충돌(collision)이 발생합니다.

이러한 충돌을 해결할 수 있는 방법으로 chaining과 open addressing 이 있습니다.

Chaining

Chaining은 해시 테이블에 링크드 리스트를 조합한 관계를 사용하여 충돌 발생 시 동일한 해시 테이블의 인덱스에 링크드 리스트 형태로 데이터를 추가하여 관리합니다.

따라서 최악의 경우에는 O(n) + 해쉬함수 계산시간의 시간복잡도를 가질 수 있으나 평균시간복잡도의 경우에는 키들이 여러 슬롯에 얼마나 잘 분배되어 있느냐에 의해서 결정됩니다.

Insert 연산에서는 일반적으로 O(1)의 시간복잡도를 가지지만 만일, 중복된 키를 허용하지 않는다면 링크드 리스트의 길이에 비례하는 연산만큼 시간복잡도가 늘어납니다.

Search 연산의 경우에도 링크드 리스트의 길이에 비례하는 연산만큼 시간복잡도를 가집니다.

Delete 연상의 경우에는 링크드 리스트에서 데이터를 제외하면 되기 때문에 O(1)의 시간복잡도를 가집니다.

Open Addressing

Open Addressing은 모든 키를 단일 해시 테이블에 저장하는 컨셉을 가집니다. 따라서 충돌 발생 시 키의 해시값을 규칙에 의해 재생성하여 빈슬롯을 찾습니다.

Open Addressing을 구현하는 방법은 다양하게 존재하는데요. 이번 강의에서는 Linear Probing과 Quardratic Probing, Double Hashing Probing 을 다룹니다.

Linear Probing

Linear Probing 은 충돌 발생시 다음 슬롯을 확인하는 컨셉을 가집니다. 따라서 Chaining 방식과 유사한 검색형태를 가집니다.

해당 방식은 연속된 슬롯, cluster의 크기가 커질 수록 성능이 떨어질 수 있습니다.

이를 보완하기 위한 방식들이 Quardratic Probing, Double Hashing Probing 입니다.

Quardratic Probing

Quardratic Probing은 충돌 발생시 해시값의 offset을 자연수의 제곱으로 증가시키는 방식입니다. (1, 4, 9, 16, ...)

해당 방식은 linear probing의 cluster를 각 키에 종속되어 생기도록 해결한 방식입니다.

Double Hashing Probing

Double hashing Probing 은 충돌 발생시 해시를 반복함으로써 offset의 증가값을 일정하지 않게 생성하는 방식입니다.

해당 방식은 quardratic probing의 키마다 가지는 offset의 종속마저 해결한 방식입니다.

좋은 해시 함수

좋은 해시 함수란 키값이 비슷하거나 특정 패턴을 가지더라도 불규칙적으로 해시를 생성해주는 것이 좋은 해시 함수입니다.

왜냐하면, 해시를 가장 이상적인 성능으로 사용할 수 있는 경우는 키가 고르게 분포되어 균일하게 키가 배치되는 것입니다.

하지만 현실에서의 데이터는 정렬되어 있거나 특정 패턴을 가진 데이터가 일반적입니다. 따라서 데이터는 편향을 가지게 되는데요. 이렇게 편향된 데이터를 고려한 해시 함수를 만들수도 있겠지만 현실적인 어려움이 있습니다.

따라서 이러한 데이터 특성을 깰 수 있도록 불규칙적으로 해시를 생성하는 것이 좋은 해시 함수 입니다.

자바에서 해시의 활용

자바를 하다보면 다음과 같은 hashcode 함수를 볼 수 있습니다.

public Zlass {

  @Override
  public int hashcode() {
    ...
    return hashcode;
  }
}

이 함수는 해당 객체의 해시코드를 생성해주는 함수인데요. 해시 컬랙션 사용시 해시키를 계산할 때 활용합니다.

예를 들어, HashMap에 put() 시 키의 hashcode()를 호출하여 해시 코드를 가져온 수 키 연산하는 방식으로 키를 생성합니다.

따라서 HashMap의 성능을 제대로 활용하기 위해서는 hashcode의 값이 불규칙하게 생성할 수 있도록 override를 해주는것이 좋습니다. (feat. 객체 비교를 잘 하자)

관련 강의

• [알고리즘] 제13-1강 hashing01
• [알고리즘] 제13-2강 hashing02
• [알고리즘] 제13-3강 hashing03

관련 글

• 알고리즘 공부의 필요성
• 알고리즘 공부 - 트리
• 알고리즘 공부 - sort
• 알고리즘 공부 - recursion
• 알고리즘을 공부해야하는 이유