[Hello Coding 알고리즘] 5. 해시 테이블
[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장 참조)
<-> 나쁜 해시 함수 : 값들이 뭉쳐져 있음. 충돌이 자주 발생함.
Author And Source
이 문제에 관하여([Hello Coding 알고리즘] 5. 해시 테이블), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bibi6666667/Hello-Coding-알고리즘-5.-해시-테이블저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)