[그림으로 개념을 이해하는 알고리즘] Hash Table (해시테이블)

해시테이블 (hash table)

• 유용한 자료 구조의 하나인 해시 테이블에 대해서 알아봄.

1. 해시 함수의 소개

• 식료품 가게에서 일을 하고 있다고 생각해보자. 손님이 물건을 사러 왔을 때 물건의 가격이 적혀져있는 장부를 찾아서 가격을 봐야 한다.
• 만약 장부가 정렬이 정렬이 되어 있지 않다면 만큼의 시간이 걸릴 것이다.
• 정렬이 되어있다면 이진 탐색을 통해 만큼의 시간이 소요될 것이다.
• 두 차이는 크다.
• 정렬이 되어있더라도 지속적으로 장부를 보고 찾는 일은 힘들 것이다. 이때 가장 필요한 것이 가격을 외우고 있는 동료가 옆에 있는 것.

이를 자료 구조 관점으로

---

• 배열과 리스트 2개의 자료구조를 학습하였다.
• 장부 구조
• 시간에 찾아내고 싶어하는데 이를 가능하게 하는 것이 이다.

2. 해시 함수

• 해시 함수는 문자열(String)을 받아서 숫자를 반환하는 함수.

• 함수는 문자열에 대해 숫자를 Mapping(할당)한다.

• 해시 함수의 요건

  • 일관성을 유지해야 한다. (Apple -> 4, Banana -> 5) 를 무조건 유지.
  • 다른 단어가 들어간다면 꼭 다른 숫자가 나와야 한다. 같은 수가 나온다면 해시 함수가 아니다.

어떻게 사용할 수 있을까?

---

• 빈 배열

  0	1	2	3	4

• 모든 가격을 위의 배열에 저장할 것이다.

  • apple의 가격을 추가. 해시 함수에 apple을 넣음.

  • 해시 함수는 3을 출력, apple의 가격(0.67)은 배열 3번 인덱스 위치에 저장 한다.

    			0.67
    0	1	2	3	4

  • milk도 추가. 해시 함수에 milk를 넣음.

  • 해시 함수가 0을 반환, 인덱스 0 위치에 milk 가격(1.49)을 저장.

    1.49			0.67
    0	1	2	3	4

  • 이와 같은 방법으로 전체 배열이 가격으로 채워질 것이다.

    1.49	0.79	2.49	0.67	1.49
    0	1	2	3	4

• 이제 아보카도 가격이 얼마지 라는 물음이 온다면, 배열을 탐색할 필요 없이 아보카도를 해시함수에 넣기만 하면 해당 가격이 있는 인덱스를 출력하게 될 것이다.

  • 4를 출력, 가격 list[4] = 1.49

• 해시함수는 가격이 저장되어있는 배열이 얼마나 큰지 알고 있어야 하며, 유요한 인덱스만 반환해야 한다.

• 해시함수는 해시 맵, 맵, 딕셔너리, 연관 배열과 같은 이름으로도 알려져 있다.

 
​x
book = dict()
​
book["apple"] = 0.67
book["milk"] = 1.49
book["avocado"] = 1.49
​
print(book) # {'avocado':1.49,'apple':0.67,'milk':1.49}
print(book['avocado']) # ouput : 1.49

• 해시테이블은 Key와 Value를 가진다.

3. 해시 테이블 사용 예

해시 테이블로 조회하기(전화번호부)

---

• 휴대폰에는 간단한 전화번호부가 있다.

• 각각의 이름은 관련된 전화번호를 가지고 있다.

  • BADE MAMA -> 581-660-9820
  • ALEX MANNING -> 484-234-4680
  • JANE MARIN -> 415-567-3579

• 만드는 전화번호부에는 다음과 같은 기능을 가지고 있다.

  • 사람이름과 관련된 전화번호를 추가
  • 사람 이름을 입력하면 그 이름과 관련된 전화번호를 알려준다.

• 해시테이블은 다음과 같은 일을 하고자 할 때 좋다.

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

 
xxxxxxxxxx
phone_book = dict() # phone_book = {} 
phone_book["jenny"] = 8675309
phone_book["emrtgency"] = 911
​
print(phone_book["jenny"]) # 8675309 

• 다른 예로는 웹사이트와 IP 맵핑이 동일한 작업이다.

중복된 항목방지

---

• 투표를 한다고 하자. 투표의 경우 1명에 1번의 기회만 주어지게 된다. 즉, 누군가가 올때마다 이미 투표했는지 확인하기 위해 긴 목록을 확인해야 한다.
• 해시 테이블을 이용.

 
xxxxxxxxxx
voted = {}
value = voted.get{"tom"} # 톰이 있다면 tom의 Value를 없다면 None을 출력
​
voted = {}
def check_voter(name):
    if voted.get(name):
        print("이미 투표하였습니다.")
    else:
        voted[name] = True
        print("투표하세요.")

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

---

• 웹 사이트를 개발한다면 캐싱이 적합하다는 이야기를 들어 본 적이 있을 것이다.
• 사용자가 이전에 사용했던 부분들을 일정량 저장해놓고, 재호출시 서버로 데이터를 요청하는 것이 아니라 캐시에 존재하는 페이지를 호출하는 방식

 
xxxxxxxxxx
cahce = {}
​
def get_page(url):
    if cache.get(url):
        return cache[url]
    else:
        data = get_data_from_server(url)
        cache[url] = data
        return data

해시 테이블의 장점

---

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

4. 충돌

• 해시 함수는 서로 다른 키를 배열의 서로 다른 위치에 할당한다고 이전에 설명하였는데, 이 부분은 조금 오류가 있는 부분이다.
• 예를 들어 26개 배열에서 0~25 (A~Z)까지를 각각 넣는다고 한다면 동일한 철자로 시작하는 Apple, Avocado의 경우 하나를 덮어쓰게 되어 다른 값이 나오게 될 것이다.
• 이러한 문제를 해결하기 위해서 배열과 리스트에서 설명했던 배열과 리스트를 조합하여 사용하는 자료구조를 사용하면 될 것이다.

5. 성능

	해시테이블(평균)	해시테이블(최악)	배열	연결리스트
탐색
삽입
삭제

• 해시테이블이 가장 느릴 경우도 발생하는데 이러한 상황이 발생하지 않도록 하는 것이 가장 중요하다.

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

사용률

---

• 사용률 : 해시 테이블에 있는 항목 수 / 해시 테이블에 있는 공간의 수
• 50%의 사용률의 해시테이블이 점점 차게 되어 80% 와 같은 높은 수를 차지할 경우 리사이징이 필요하다. 해당 크기 만큼 늘어남으로써 충돌을 방지 할 수 있다.

좋은 해시 함수

---

• 값들을 골고루 분산시키는 함수가 좋은 해시 함수이다.
• 값들이 뭉쳐져 있을 경우 충돌이 일어날 확률이 높다.