고정 헤더 영역
상세 컨텐츠
본문
728x90
[해시 함수 intro]
'자료구조' 관점에서 살펴보면, 상품과 가격을 배열로 표현 가능
(계란, 2) (우유 1) (배 0.5) ...
조선시대(이건 내가 설정한 상황) 한 가게에서 일을 하고 있다고 생각.
손님이 올 때마다 장부에서 가격을 확인해서 알려주는데,
ㄱ ㅎ a ... 정리되지 않다면 '단순 탐색'으로 시간이 좀 걸리고
ㄱ ㄴ ㄷ ... 정리되어 있다면 '이진 탐색'으로 시간이 줄어들 것
그리고 모든 가격을 다 외운 '갑순이'가 있다면 '즉시' 알 수 있을 것 (해시함수)
[해시 함수]
해시 함수 : String (문자열)을 받아서 -> 숫자를 반환하는 함수
- 문자열에 대한 숫자를 할당(mapping)함
- 문자열을 넣었을 때 나오는 숫자들에 대한 특정한 패턴이 보이지 않는 것 같지만, 다음과 같은 요건을 갖추어야 함
1) 일관성이 있어야 함. ex) apple을 넣었을 때 4가 나오면, 계속 apple을 넣었을 때라면 4가 나와야 함
2) 다른 단어가 들어가면 다른 숫자가 나와야 함. ex) 어떤 단어를 넣어도 같은 숫자가 나오면 좋은 함수가 아님
| 1.49 |
ex) 아보카도를 -> 해시함수에 넣어서 4가 나오면, 인덱스 위치 4번째가 아보카도 가격인것 (1.49)
해시 함수는 가격이 저장된 위치를 '정확하게' 알려주어 탐색을 할 필요가 전혀 없는데, 이럴 수 있는 이유.
1) 해시 함수는 같은 이름에 대해서는 항상 같은 인덱스를 할당. (아보카도는 -> 계속 4)
2) 다른 문자열에 대해서는 다른 인덱스를 할당 (모든 가격을 각각 배열의 다른 위치에 저장)
3) 해시 함수는 배열이 얼마나 큰지 알고 있어야 하며, 유효한 인덱스만 반환함. (만약 배열이 5개 원소만 가질 수 있는데 100을 반환해서는 안 됨)
// 갑순이 만들기 완료
해시 함수 + 배열 -> 해시 테이블
- 자료 구조 그 자체 외에도 해시 함수라는 추가적인 논리구조를 가지는 첫 번째 자료 구조
- 배열과 리스트는 직접 메모리를 할당하지만, 해시 테이블은 해시 함수를 사용해서 더 총명하게 어디에 원소를 저장할지를 결정함
- 해시 테이블은 복잡한 자료구조 중 가장 쓸모가 많을 것 (+ 속도가 정말 빠름)
- 자료를 저장할 때 배열을 사용
- 해시 테이블 = hash map, maps, dictionaries, 연관 배열 (associative arrays)
- 해시 테이블은 key와 value(값)을 가짐.
ex) 상품 이름 - key, 가격 - value
- 해시 테이블은 키에 대한 값을 할당함
[해시 테이블 사용 예]
- 어떤 것을 다른 것과 연관 시킬 때
- 무언가를 찾아볼 때
웹 주소에 대해 IP 주소를 할당하는 작업
-> 해시테이블을 위한 일! 이런 과정을 DNS 확인 (DNS resolution) 작업이라고 함.
1. 해시 테이블로 조회하기
전화번호부가 해시 테이블을 사용하는 '완벽한' 예
다음과 같이 만들어야 할 것
1) 사람 이름, 그 사람 전화번호 추가
2) 사람 이름을 입력하면 그 사람 전화번호를 알려줌
| (파이썬이긴 함) 1. 해시 테이블 만들기 phone_book = dict() -> (더 쉽게 표현하면) phone_book = {} 2. 사람 이름, 전화번호 추가 phone_book["Jenny"] = 123456 phone_book{"emergency"] = 911 // 완성 Q. Jenny 전화번호는? -> print phone_book["Jenny"] |
2. 중복된 항목 방지하기
투표소 관리인이라고 생각
- 모든 사람은 한 번만 투표할 수 있도록 관리해야 함
- 사람이 오면 이름 list를 보고 투표를 했는지 안했는지 확인해야함
- 몇 십 만명을 관리하면 종이가 엄청 길텐데 ..... -> 해시 테이블!
| 1. 이미 투표한 사람을 추적하기 위한 해시 테이블 만들기 voted = {} 2. 사람이 오면 해시 테이블 안에 이름이 있는지 확인 value = voted.get("tom") - tome이라는 키가 있으면, 그 키에 해당하는 값을 반환. (없으면 None) 전체 코드 voted = {} def check_voter(name): if voted.get(name): print "돌려 보내세요!" else: voted[name] = True print "투표하게 하세요" |
만약 투표한 사람의 이름을 리스트에 저장한다면 리스트 전체에 대해 단순 탐색을 반복해야 해서 함수가 정-말 느려질 것. 하지만 해시 테이블에 저장하면 순간적으로! 알 수 있다는거~
3. 해시 테이블을 캐시로 사용하기
캐싱 - 정보를 다시 계산하지 않고 저장했다가 알려주는 것
ex) 조카가 하도 지구에서 달이 몇 km 떨어져 있냐고 물어보는 통에 구글링하다가 ... 384,000km 라고 바로 대답할 수 있는게 캐싱
캐싱의 장점
1) 웹페이지를 더 빨리 보여줌. (조카가 또 물어볼 때 384,000km라고 바로 대답할 수 있는 것처럼)
2) 페북이 일을 덜 할 수 있게 해줌. (=작업 속도를 올려줌)
- 모든 대형 웹 사이트는 캐싱을 사용함 -> 그리고 그 자료는 해시 테이블에 저장됨!
| cache = {} 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) 서버에게 작업 시키지 않고 자료를 캐싱할 수 있음
[충돌]
위 내용에서 거짓말한 내용 - 사실 정!확!한! 위치를 보내주는 해시 함수를 만드는 것은 거의 불가능함.
ex) 25개의 배열은 만들어서 a, b, c, d에 해당하는 과일을 넣는다고 할 때
apple -> 첫 번째 배열에, banana -> 두 번째 배열에 ... 근데 만약 avocado를 넣어주게 되면? apple 대신 avocadeo가 덮어쓰게 됨. 그래서 누가 apple 가격을 찾는데 avocado 가격이 나오는 상황이 발생하는데 이걸 '충돌'이라고 함.
-> 충돌을 해결하는 가장 간단한 방법은 같은 공간에 여러 개의 키를 연결 리스트로 만들어 넣는 것
| A | B | C | ... |
만약 첫 번째에
| Apple | 3 |
| Avocado | 4 |
| Almond | 2 |
...
식료품에 a로 시작하는 모든 상품을 다 넣는다고 생각하면, 뭐 하나 찾는데 시간이 엄-청 오래걸리게 될 것
-> 근데 위에 B, C ... 나머지 공간은 모두 지금 낭비가 되고 있는 중.
-> 이건 해시테이블이 아니라 그냥 연결 리스트와 다를 바가 없음. 결국 this 해시 테이블은 느려지게 됨.
교훈
1) 해시 함수는 키를 해시 테이블 전체에 고르게 할당해야 함
2) 연결 리스트가 길어지면 해시 테이블 속도가 느려짐 (but 좋은 해시 함수가 있다면 이런 일은 벌어지지 않음)
Q. 좋은 해시 함수를 고르는 방법은?
[성능]
- 평균적으로 해시 테이블은 모든 항목에 대해 O(1) 시간이 걸림
O(1) 시간은 상수 시간(constant time)으로 불리는데, 순간적이라는 뜻이 아니라 해시 테이블 크기에 상관없이 항상 똑같은 시간이 걸린다는 의미.
단순 탐색 (선형 시간)
이진 탐색 (로그 시간) - 단순 탐색보다 빠르지만 로그 시간이 걸림
해시 테이블 - 일정한 상수 시간이 걸림
해시 테이블이 하나의 항목을 가지든 10억 개의 항목을 가지든 무언가를 찾는데 걸리는 시간은 항상 같다는 것
그런데 해시 테이블을 잘못 사용하면 O(n) 만큼의 시간이 걸리기도 함
-> 충돌을 피해야 함.
-> 충돌을 피하기 위해 1) 낮은 사용률 2) 좋은 해시 함수
사용률
* 해시 테이블 사용률(load factor) 계산법*
해시 테이블에 있는 항목 수 / 해시 테이블에 있는 공간 수
| 2 | 3 |
-> 사용률은 2/10 (1/5인 것)
ex) 공간은 50개인데 100개의 물건 가격을 저장한다면? 사용률은 100/50 -> 2가 됨
즉, 사용률이 1보다 크다는 것 = 배열에 공간의 수보다 항목 수가 많다는 뜻
-> 사용률이 커지기 시작하면 해시 테이블 공간을 추가해야함 (리사이징 resizing)
보통 2배 정도 크기로 배열을 만듦.
- 사용률이 낮을수록 충돌이 적게 일어나고, 해시 테이블 성능이 좋아짐. (보통 사용률이 0.7보다 커지면 리사이징함)
좋은 해시 함수란
= 배열에 값을 고루 분포시키는 함수
나쁜 해시 함수는 값들이 뭉쳐져 있어서 충돌이 자주 발생함
출처 : 그림으로 개념을 이해하는 알고리즘 (한빛미디어)
728x90
반응형
'자료구조 > 개념' 카테고리의 다른 글
| Linked List (0) | 2021.06.06 |
|---|---|
| Array List (0) | 2021.06.06 |
| List (0) | 2021.06.06 |
| 배열(Array) (0) | 2021.06.06 |
| 자료구조란? (feat. 자료구조의 필요성) (2) | 2021.06.06 |
