Hash Table

• Hash 함수
• 해시테이블을 사용하는 예
• 충돌
• 해시 테이블의 성능
  • 사용률
• 정리하기
• 참조

안녕하세요! caution입니다. 오늘은 해시함수에 대해서 배워봅시당.

가격표에 물건의 가격이 적혀져 있는데, 물건의 가격을 찾기 위해서 얼마만큼의 시간이 소요될까요? 가격표가 이름 순으로 정렬되어 있지 않아 단순 탐색으로 진행한다면 O(n) 시간이, 정렬되어 있어 이진 탐색으로 찾아본다면 O(log n) 시간이 걸릴겁니다. 만약 가격표를 다른 직원이 모두 외우고 있다면 어떨까요? 그 직원에게 물어본다면 O(1) 시간 만에 가격을 알려줄 수 있을 겁니다. 이름으로 가격을 바로 검색할 수 있는 자료구조를 만들어봅시다.

Hash 함수

해시 함수는 문자열을 받아서 이 문자열에 대한 숫자를 할당해주는 함수입니다. 해시 함수는 다음과 같은 요건을 갖추어야 합니다.

해시함수에는 일관성이 있어야 합니다. 같은 문자열을 넣으면 항상 같은 수가 나와야 합니다. 다른 문자열을 넣으면 다른 숫자가 나와야 합니다. 예를 들어 어떤 단어를 넣어도 1만 나온다면 좋은 해시 함수가 아닙니다. 가장 좋은 경우는 서로 다른 단어에 대해 모두 서로 다른 숫자가 나와야 합니다.

가격표로 크기가 5인 배열이 있다고 생각해봅시다. 우리는 모든 물건의 가격을 이 배열에 넣을 겁니다.

먼저 사과의 가격을 추가합니다. 해시함수에 apple를 넣으면 3이 나옵니다. 그럼 apple의 가격은 3번 index에 넣을 겁니다.

다음으로 우유를 추가합니다. 해시함수에 milk를 넣으면 0이 나옵니다. 그럼 milk의 가격은 0번 index에 넣을 겁니다.

이런 방식을 반복하면 가격표를 모두 채울 수 있습니다.

아이스크림의 가격을 알아보려면 어떻게 해야할까요? 해시함수에 coke를 넣으면 4가 나오겠죠? 그렇기 때문에 전체 가격표를 훑어볼 필요 없이 바로 4번째 배열의 값을 가져오면 됩니다. 바로 탐색 없이 가격을 가져오기 때문에 O(1)의 매우 빠른 시간으로 데이터를 가져올 수 있습니다.

해시 함수는 배열이 얼마나 큰지 알고 있어야 하며, 유효한 인덱스만 반환해야 합니다. 배열이 5개의 원소만 가질 수 있다면 10을 반환해서는 안됩니다.

이때 해시 테이블의 상품 이름은 키(Key)가 되고, 가격은 값(Value)이 됩니다. 해시 테이블은 키에 대한 값을 할당하는 자료구조입니다.

swift에도 해시함수가 있을까요? swift에서는 Dictionary의 이름을 가진 해시 테이블이 존재합니다. 다음과 같이 사용해볼 수 있죠.

var dictonary: [String:Int] = [:]
dictonary["milk"] = 1500
dictonary["banana"] = 800

print(dictonary["milk"])  //1500

해시테이블을 사용하는 예

해시 테이블을 사용하면 키 값을 알고 있을 때 매우 빠르게 데이터에 접근할 수 있습니다. 예를 들어 DNS를 해시 테이블로 사용할 수도 있겠죠.

var dns: [String:String] = [:]
dns["google.com"] = "74.125.239.133"
dns["naver.com"] = "173.252.120.6"

또한 해시 테이블에서는 키-값이 1:1 매칭이기 때문에 중복 항목을 방지할 수 있습니다. 유권자의 투표 여부를 확인하려면 어떻게 해야할까요?

var voted: [String:Bool] = [:]

func checkVotable(identifier: String) -> Bool {
  return voted[identifier] == nil
}

func vote(identifier: String) {
  guard checkVotable(identifier: identifier) else {
    print("이미 투표했습니다.")
    return
  }
  // 투표를 한다.
  voted[identifier] = true
}

해시 테이블에 이미 유권자에 대한 값이 존재한다면 이 사람은 이미 투표를 했다는 걸 알 수 있습니다.

해시 테이블은 캐싱에도 사용할 수 있습니다. 키를 URL로 하고 그에 대응하는 자료를 할당하여 사용할 수 있습니다.

var cache: [URL:Any] = [:]

func load(url: URL) -> Any {
  if let cacheData = cache[url] {
    return cacheData
  } else {
    let data = requestData()
    cache[identifier] = data
    return data
  }
}

그럼 캐싱된 데이터가 있다면 그 데이터를 넘겨주고, 캐싱된 데이터가 없을 때에만 데이터를 요청할 수 있습니다.

충돌

아까 우리는 5개의 물건의 가격을 담을 수 있는 가격표를 해시 테이블로 만들었습니다.

이번엔 다른 방식으로 가격표를 만들어보죠. 26개의 공간이 있는 배열을 가격표로 지정합니다.

이번에는 물건의 첫 글자에 따라 공간을 할당하는 방식의 해시 함수를 사용하겠습니다. 먼저 apple은 가장 첫 번째 공간에 들어갈겁니다.

다음으로 banana를 index 1에 넣겠습니다.

자 이제 beer를 넣어보죠. 이때 문제가 발생합니다. beer의 첫 글자는 b 니까 index 1에 넣어야 하는데 이미 banana가 들어가 있습니다. 그럼 beer를 넣기 위해 banana를 덮어쓰게 됩니다. banana의 가격을 요청했지만 beer의 가격을 넘겨주게되죠. 이러한 현상을 충돌 이라고 합니다.

이 충돌을 해결하기 위해선 어떻게 해야할까요? 여러 가지 방법이 있지만, 간단한 방법 중 하나는 같은 공간( index 1 )에서 여러 개의 키를 연결 리스트로 만들어 넣는 겁니다.

그럼 b로 시작하는 어떤 물건을 찾기 위해서는 이 연결 리스트를 탐색해야합니다. 연결 리스트가 커질 수록 물건을 찾는 시간이 O(n)이므로 길어지겠죠.

• 해시 함수가 매우 중요합니다. 방금 전의 해시 함수는 여러 키를 하나의 공간에 할당하는 문제가 발생합니다. 이상적으로는 해시 함수는 키를 해시 테이블 전체에 고르게 할당해야 합니다.
• 만약 연결 리스트가 길어지면 해시 테이블의 속도도 느려집니다. 좋은 해시 함수가 있다면 이런 일이 발생하지 않겠죠!

해시 테이블의 성능

해시 테이블의 성능은 어떻게 될까요? 앞서 말한 것과 같이 연결 리스트가 길어진다면 해시 테이블의 속도가 매우 떨어지게 됩니다. 그래서 평균적인 성능과 최악의 성능을 비교해볼 수 있겠죠.

평균적인 경우 해시 테이블의 성능을 살펴보면 탐색을 할 때 배열만큼 빠릅니다. 그리고 삽입이나 삭제에서는 연결 리스트만큼 빠릅니다. 평균적인 상황에서는 매우 빠른 자료구조입니다. 하지만 최악의 경우에는 해시 테이블이 가장 느리기도 합니다. 따라서 최악의 상황이 발생하지 않도록 하는 것이 좋습니다. 이를 위해서는 충돌을 피해야 하고, 충돌을 피하려면 다음과 같은 것이 필요합니다.

• 낮은 사용률
• 좋은 해시함수

사용률

해시 테이블의 사용률을 계산하는 방법은 다음과 같습니다.

해시 테이블에 있는 항목 수 / 해시 테이블 공간 크기

해시 테이블의 모든 공간에 항목이 들어가 있다면, 해시 테이블의 사용량은 1이 될 겁니다. 사용량이 1보다 크다는 것은 공간보다 항목의 수가 많다는 뜻이므로, 해시 테이블의 공간을 추가해야 합니다. 이를 리사이징 이라고 합니다.

앞 서 만들었던 가격표를 다시 봅시다. 이때 신제품인 coffee를 추가해야한다면 이 테이블을 리사이징 해야 합니다. 보통은 두 배 정도 큰 배열을 만드는 것이 보통입니다.

이제 coffee를 넣을 수 있겠네요.

새로 만들어진 해시 테이블의 사용률은 6/10 입니다. 사용률이 낮을 수록 충돌이 적게 일어나고, 해시 테이블의 성능 또한 좋아집니다. 이 리사이징은 엄청 비싼 작업이기 때문에 자주 일어나는 것은 좋지 않습니다. 보통은 사용률이 0.7보다 커지면 리사이징 하며, 해시 테이블은 리사이징을 해도 O(1)의 시간이 걸립니다.

정리하기

• 해시 테이블은 해시 함수와 배열을 결합해서 만듭니다.
• 충돌은 해시 테이블의 성능을 떨어뜨리기 때문에 충돌을 줄이는 해시 함수가 있어야 합니다.
• 해시테이블은 탐색, 삽입, 삭제 속도가 매우 빠른 상수시간을 가집니다.
• 해시 테이블은 어떤 항목과 다른 항목의 관계를 모형화 하는 데 좋습니다.
• 보통 사용율이 0.7보다 커지면 해시 테이블을 리사이징합니다.
• 해시 테이블은 데이터를 캐싱하는 데도 사용되고, 중복을 잡아내는 데에도 뛰어납니다.

참조

• Hello Coding 그림으로 개념을 이해하는 알고리즘