손님이 물건을 사러온다고 가정해보자.
가게 주인은 물건의 가격 (예, 사과)을 확인 하기 위해서 장부를 뒤져서 알려 주어야 한다.
하지만 가게 주인이 가게의 모든 물건의 가격을 외우고 있는 직원을 고용하고 있다면, 이럴 필요가 없어진다.
자료구조적으로 살펴본다면, 사과 이름을 이름순으로 정렬 되어있는 장부에서 탐색해 볼 경우 이진 탐색의 경우 O(log n) 시간이 걸린다.
하지만 우리는 모든 물건의 가격을 외우고 있는 직원과 같이 O(1)시간에 찾아내고 싶다. 이럴때 필요한 것이 바로 해시 함수(Hash function)이
다.
해시함수는 문자열 -> 숫자로 1:1 변환 시켜주는 함수이다.
만일 특정한 길이의 배열이 있다면, 배열 내의 인덱스 하나하나에 다른 문자열의 해쉬 값(가격)이 들어가서 자리할 수 있다.
값이 모두 입력된 상태라면, 이제 문자열만 입력하면 바로 가격을 찾아낼 수 있는것이다.
해쉬 함수는 배열의 크기를 정확히 알고 있어야만 사용 가능하고, 크기를 벗어나는 값을 반환하는 경우는 없어야 한다.
해시 함수 + 배열 = 해시 테이블
해시 테이블은 해시 맵, 맵, 딕셔너리, 연관 배열로도 불린다.
파이썬에서는 딕셔너리라고 하는 해시 테이블이 있다.
*파이썬 3에서는 print함수 뒤에 출력할 대상을 ()로 감싸주어야 한다...
전화번호부를 직접 만든다고 가정하자.
이름 - 전화번호 로 매핑한다.
사람 이름을 입력시 즉시 전화번호를 알려주어야 한다.
어떤것을 다른것과 연관 시키고자 할때, 무언가를 찾아보고자 할때 해시테이블을 사용하면 좋다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:06:47) [MSC v.1914 32 bit (Intel)] on win32 Type "help", "copyright", "credits" or "license" for more information. >>> phone_book = {} >>> phone_book["jenny"] = 1234567 >>> phone_book["emergency"] = 119 >>> print(phone_book["jenny"]) 1234567 >>> | cs |
해시 테이블은 웹 사이트를 조회 할때도 사용된다.
예를들어 Google.com을 접속할때는 74.12.239.133으로 자동 번역되어 입력된다. 이런 작업을 DNS resolution작업이라고 한다.
중복 방지
투표소에서 투표를 한다고 가정해보자. 투표소에는 이미 투표한 사람의 목록이 있어야한다. 중복 투표를 방지하지 위해서 리스트에 투표를 할
때마다 그 사람의 이름을 적어 두어야 한다. 하지만, 투표자의 수가 100만명이라면, 리스트를 조회하기에는 시간이 너무 오래걸린다.
파이썬의 해시테이블은 get()이라는 함수로 키에 값이 담겨있는지 확인 할 수 있다.
1 2 3 4 5 6 7 | >>> voted = {} >>> value = voted.get("tom") >>> print(value) None | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | >>> voted = {} >>> def check_voter(name): ... if voted.get(name): ... print("쫓아내세요!") ... else: ... voted[name] = True ... print("투표하게 하세요.") ... >>> check_voter("tom) File "<stdin>", line 1 check_voter("tom) ^ SyntaxError: EOL while scanning string literal >>> check_voter("tom") 투표하게 하세요. >>> check_voter("mike") 투표하게 하세요. >>> check_voter("mike") 쫓아내세요! >>> | cs |
해시 테이블을 캐시로 사용하기
웹 사이트를 접속할때, 로그인 페이지와 같은 것들은 서버가 굳이 고민할 필요없이 모든 사람에게 똑같은 내용만을 출력하는 페이지다.
이런 것들은 저장된 것을 바로 출력해주기만 하면 되는 형태인데, 마치 우리가 지구에서 달까지의 거리를 암기하고 있을때 처럼, 즉시 말해
줄 수 있게 할 수 있다.
캐싱을 하면 서버에 부담이 줄어들기 때문에 작업 속도를 올릴 수 있다.
1 2 3 4 5 6 7 8 9 10 | >>> cache = {} >>> def get_page(url): ... if cache.get(url): ... return cache[url] ... else: ... data = get_data_from_server(url) ... cache[url] = data ... return data ... >>> | cs |
'자료구조, 알고리즘' 카테고리의 다른 글
| [강의노트]이진트리의 운행법 (0) | 2018.07.17 |
|---|---|
| 이화여대 이상호 교수의 자료구조 강의 (0) | 2018.07.15 |