Today I Learned
Search

해시 테이블

Table of contents

  1. 해시 함수
  2. 해시 테이블
  3. 해시 테이블의 충돌
  4. 해시 함수의 성능 올리기
    1. 해시 함수의 사용률 계산하기
    2. 좋은 해시 함수란
  5. References

해시 함수

해시 함수의 원리

  • 평균적인 경우: O(1)
  • 최악의 경우: O(n)

해시 함수는 문자열(String)을 받아서 숫자를 반환하는 함수이다. 해시 함수는 문자열에 대해 숫자를 할당한다. 문자열을 넣었을 때 나오는 숫자들에 특별한 패턴이 보이지 않는 것 같지만, 사실 해시 함수는 다음과 같은 요건을 갖추어야 한다.

  • 해시 함수에는 일관성이 있어야 한다. 만약 ‘apple’을 넣었을 때 ‘4’를 반환한다면 ‘apple’을 넣을 때마다 반환되는 값은 항상 ‘4’이여야 한다. 그렇지 않으면 해시 함수로서의 역할을 할 수 없다.
  • 다른 단어가 들어가면 다른 숫자(index)가 나와야 한다. 예를 들어, 어떤 단어를 넣어도 ‘1’만 나온다면 좋은 해시 함수가 아니다. 가장 좋은 경우는 서로 다른 단어에 대해 모두 서로 다른 숫자가 나와야 한다.
  • 해시 함수는 배열이 얼마나 큰지 알고 있어야 하며, 유효한 인덱스만 반환해야 한다. 만약 배열이 5 개의 원소만 가질 수 있다면 100을 반환해서는 안 된다.

해시 테이블

해시 함수와 배열을 합친 것이 바로 해시 테이블이다. 배열과 리스트는 직접 메모리를 할당하지만, 해시 테이블은 해시 함수를 사용해서 어디에 원소를 저장할지 결정한다. 해시 테이블은 해시 맵(Hash map), 맵(Map), 딕셔너리(Dictionaries), 연관 배열(Associative arrays)이라는 이름으로도 알려져 있다.

대부분의 프로그래밍 언어에는 해시 테이블이 구현되어 있다. 파이썬에는 딕셔너리(dictionary)라는 이름의 해시 테이블이 있다.

해시 테이블은 키(key)와 값(value)을 가진다. 그리고 순서가 상관없다.

book = dict()
# or book = {}

book["apple"] = 0.67
book["milk"] = 1.49
book["avocado"] = 1.49

print(book)
# {'apple': 0.67, 'milk': 1.49, 'avocado': 1.49}

print(book["avocado"])
# 1.49

해시 테이블은 이럴 때 사용하면 좋다

  • 어떤 것을 다른 것과 연관시키고자 할 때
  • 무언가를 찾아보고자 할 때

예를 들어, https://www.abc.com와 같은 웹사이트에 접속한다고 하자. 컴퓨터는 해당 주소를 IP 주소로 번역해 준다. 어떤 웹사이트에 접속하든 그 주소는 모두 IP 주소로 번역된다. 이런 과정을 DNS 확인 작업이라고 한다. 해시 테이블은 이 기능을 제공하는 방법 중 하나이다.

해시 테이블의 장점은 다음과 같다.

  • 어떤 것과 다른 것 사이의 관계를 모형화할 수 있다.
  • 중복을 막을 수 있다.
  • 서버에게 작업을 시키지 않고 작업을 캐싱할 수 있다.

해시 테이블의 충돌

서로 다른 입력 값에 대해 동일한 해시 값, 즉 해시 테이블 내의 동일한 주소를 반환하는 것이다. 어떤 해시 함수든, 그 알고리즘이 아무리 정교하게 설계되었다 하더라도 모든 입력 값에 대해 고유한 해시 값을 만들지는 못한다. 해시 함수의 충돌은 피할 수 없다. 충돌이 많이 일어날수록 해시 함수는 느려지게 된다.

충돌을 해결하는 방법은 여러 가지가 있는데, 가장 간단한 방법은 같은 공간에 여러 개의 키를 연결 리스트로 만들어 넣는 것이다. 하지만 그 연결 리스트가 길어지게 되면 해시 테이블도 느려진다. 연결 리스트에 데이터를 넣는 것과 다를 것이 없기 때문이다.

좋은 해시 함수는 이런 충돌을 최소화한다. 그렇다면 어떻게 좋은 해시 함수를 고를 수 있을까?

해시 함수의 성능 올리기

해시 함수의 사용률 계산하기

해시 함수의 사용률을 계산하는 것은 쉽다. 해시 테이블에 있는 항목 수 / 해시 테이블에 있는 공간의 수이다.

만약 100개의 아이템을 해시 테이블에 넣어야 하는데, 해시 배열의 길이가 50이면 사용률은 2가 된다. 사용률이 1보다 크다는 것은 배열에 공간의 수보다 항목의 수가 많은 것을 뜻한다. 사용률이 커지기 시작하면 해시 테이블의 공간을 추가해야 한다. 이걸 리사이징이라고 한다.

리사이징은 대략 두 배 정도의 크기로 배열을 만드는 것이 보통이다. 보통 사용룰이 0.7보다 커지면 리사이징을 한다. 리사이징 작업은 비용이 많이 들어가는 작업이라 자주 하지 않는 것이 좋지만, 해시 테입르은 리사이징을 해도 평균적으로 O(1)시간이 걸린다.

좋은 해시 함수란

좋은 함수란 배열에 값을 고루 분포시키는 함수이다. 나쁜 함수는 값들이 뭉쳐져 있어서 충돌이 자주 발생한다. SHA 함수는 해시 함수로 사용할 수 있다.

References