[210702]

Hello Coding 알고리즘

5. 해시 테이블

해시 함수hash function

예시

• 식료품 가게에서 일을 한다.
• 물건의 가격은 장부에 적혀 있다.
  • 장부가 알파벳 순서로 정렬되어 있지 않다면 - 일일이 탐색해야 하므로 O(n) 시간이 걸림
  • 장부가 정렬되어 있다면 - 이진 탐색을 사용할 수 있으므로 O(log n) 시간이 걸림
• 이진 탐색이 아무리 빨라도 매번 탐색을 해야 한다는 번거로움이 있다.
• 어떤 직원이 모든 물건의 이름과 가격을 외우고 있다면? 매우 편할 것.
  • 모든 항목에 대해 O(1) 시간 만에 즉시 가격을 알려줄 수 있다.
• 이 '직원'같은 역할을 하는 것이 해시 함수이다!

해시 함수 hash function

: 해시 함수는 문자열(string)을 받아 숫자를 반환하는 함수이다.

즉, 문자열에 대해 숫자를 맵핑(mapping, 할당)한다.

해시 함수의 요건

• 일관성. 같은 단어에 대해 항상 같은 숫자를 리턴한다.
  • apple을 넣었을 때 4를 반환한다면, apple을 넣을 때마다 반환되는 값은 항상 4여야 한다.
• 다른 단어가 들어가면 다른 숫자가 나와야 한다.
  • (가장 좋은 경우) 서로 다른 단어에 대해 모두 서로 다른 숫자가 나와야 한다.
• 해시 함수는 배열이 얼마나 큰지 알고 있어야 하며, 유효한 인덱스만 반환해야 함.

해시 함수 사용

위 예제에 적용하자면..

가격을 배열에 저장한다.

• apple의 가격을 추가하려 한다. 해시함수에 apple을 넣어 4라는 값을 얻는다.
• apple의 가격을 배열의 4번 인덱스에 저장한다.
• milk의 가격을 넣기 위해, 해시함수에 milk를 넣어 2라는 값을 얻는다.
• milk의 가격을 배열의 2번 인덱스에 저장한다.
• ..
• 이제 apple의 가격을 알기 위해서는, 해시 함수에 apple을 넣고 반환되는 숫자에 대한 인덱스만 찾아가면 된다. (O(1))
  • 매번 배열을 뒤질 필요가 없다! = 탐색할 필요가 없다.

해시 테이블 hash table

위 예제처럼, 해시 함수와 배열을 합치면 해시 테이블이라는 자료구조가 된다.

해시 테이블의 동의어 = 해시 맵 hash maps, 맵 maps, 딕셔너리 dictionaries, 연관 배열 associative arrays

• 해시 테이블은 키key 와 값value 을 가진다!
• 속도가 빠르다 - 탐색, 삽입, 삭제가 모두 빠르다.
• 쓸모가 매우 많다

해시 테이블 코드

해시 테이블 (파이썬에서는 딕셔너리) 사용 예제 코드

book = dict() # 빈 해시 테이블 만들기 (1)
book = {} # 빈 해시 테이블 만들기 (2)

book["apple"] = 0.67 # apple의 가격 = 0.67달러
book["milk"] = 1.49 # milk의 가격 = 1.49달러

print book # {'apple': 0.67, 'milk': 1.49}
print book["avocado"] # 1.49

해시 테이블을 사용하는 예

해시 테이블로 조회하기

• 어떤 항목을 다른 항목과 연관시키려 할 때
• 어떤 항목을 찾아보고자 할 때

위와 같은 경우 해시테이블을 사용하면 좋다.

'표'로 항목-항목 간 관계를 모형화하고 싶은 경우 해시테이블이 적절하다.

예시 : DNS확인(DNS resolution) 작업 - 웹 주소에 대해 IP주소를 할당하는 작업

중복 항목 방지하기

• 해시테이블을 통해, 입력되려는 항목이 이미 존재하는지 아닌지 빠르게 확인할 수 있다.
• (파이썬) get() : 해시테이블 내에 해당 키가 있으면 그 키에 해당하는 값을 반환하고, 없으면 None을 반환함.

예시 : 선거에서 어떤 사람이 이미 투표한 사람이라면 돌려보내고, 투표한 적 없는 사람이라면 이름을 추가한 후 투표하게 한다.

voted = {}

def check_voter(name):
    if voted.get(name):
        print "돌려 보내세요!"
    else:
        voted[name] = True
        print "투표하게 하세요."

해시 테이블을 캐시로 사용하기 - 캐싱

캐싱 caching

: 정보를 매번 탐색/계산하지 않고, 미리 저장했다가 알려주는 것.

비유 : 지구에서 달까지의 거리를 처음 물어보면 구글링하느라 시간이 걸리지만, 10번 물어보면 외워서 바로 대답하게 된다.

이처럼 웹 페이지를 요청할 때마다 매번 서버에서 받아오는 게 아니라, (자주 쓰는) 어떤 페이지는 미리 저장해 두었다가 바로 보여주는 것이 캐싱이다.

캐싱의 장점

• 웹 페이지를 더 빠르게 보여 줌
• 서버가 일을 덜 할 수 있음 (부하를 줄임)

모든 대형 웹 사이트는 캐싱을 사용하고, 캐싱한 자료가 해시 테이블에 저장된다.

URL 호출 시 캐싱된 해시테이블에 저장되어 있는지 확인하고, 있다면 저장된 내용을 / 없다면 서버로붙어 받아온 내용을 보여준다.

cache = {}

def get_page(url):
    if cache.get(url):
        return cache[url] # 캐싱된 자료 전송
    else:
        data = get_data_from_server(url)
        cache[url] = data # 캐시에 처음으로 자료를 저장
        return data 

충돌 collision

: 두 개의 키가 같은 공간에 할당되는 것.

해시 테이블의 성능을 이해하기 위해 충돌을 이해해야 한다.

사실 첫 설명처럼 모든 데이터에 대한 배열 공간을 할당하는 해시함수를 만드는 것은 거의 불가능하다.

충돌이 발생해, 이미 할당된 공간에 또 할당하려 하면 기존 데이터에 덮어씌워지게 된다. -> 막아야 함!

해결1

: 배열의 한 공간에 여러 키를 링크드리스트로 만들어 넣는다.

• 단점 : 한 공간에만 많은 데이터가 넣어질 경우, 링크드리스트가 길어지므로 그 공간에 있는 데이터를 찾을 때 속도가 느려진다.

결론1

• 해시 함수가 중요함. 이상적으로는 해시 함수는 키를 해시 테이블 전체에 고르게 할당해야 함.
• 링크드리스트가 길어지면 해시테이블의 속도도 느려진다. (좋은 해시 함수를 통해 보완할 수 있다)

좋은 해시 함수 = 충돌을 최소화시키는 함수.

성능

평균적인 경우, 해시 테이블은 모든 항목에 대해 O(1)(상수 시간) 이 걸린다.

상수 시간 constant time : 크기에 상관없이 항상 똑같은 시간이 걸린다.

but 최악의 경우, 해시 테이블은 모든 항목에 대해 O(n)(선형 시간)이 걸린다.

-> 최악의 경우를 피하려면 충돌을 피해야 한다.

-> 충돌을 피하려면 아래와 같이 해야 한다.

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

사용률 (load factor,로드 팩터)

해시 테이블의 로드팩터 = 해시 테이블에 있는 항목의 수 / 해시 테이블에 있는 공간의 수.

예를 들어 { , 2, , 4}와 같은 배열에서 사용률은 50%이다. (2개/4칸)

로드팩터는 해시 테이블에 빈 공간이 얼마나 남아 있는지를 측정한다.

로드 팩터가 낮을수록 충돌이 적게 일어나고, 해시 테이블의 성능이 좋아진다.

• 로드팩터 > 1 : 배열에 공간의 수보다 항목의 수가 많다. 리사이징이 필요한 상태.
  • 보통 로드 팩터가 0.7 이상일 때 리사이징을 한다.
• 리사이징resizing : 테이블의 공간을 추가하는 것.
  • 기존 배열의 두 배 크기의 배열을 새로 만든다.
  • 새로 만든 배열에, 해시 함수를 통해 모든 항목을 다시 넣는다.
  • 리사이징은 시간이 걸리는 작업이지만, 해시테이블 리사이징은 평균적으로O(1)시간이 걸린다.

좋은 해시 함수란?

: 배열에 값을 골고루 분포시키는 함수.

가능한 한 항목들을 넓게 할당해야 한다.

참고 : SHA함수. (11장 참조)

<-> 나쁜 해시 함수 : 값들이 뭉쳐져 있음. 충돌이 자주 발생함.