해시(Hash)
해시 테이블이란?
컴퓨터에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 인덱스를 key, value의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
해시 테이블의 원리
파이썬에서 해시는 딕셔너리(dictionary)와 같다
likeLionAge = {"박수진": 24, "신정희": 24, "전승환": 25, "김하늘": 26, "성수연": 28, "김준호": 28}
Python
복사
해시 테이블의 시간복잡도는 O(1)이다.
likLionAges에서 박수진의 나이를 찾고싶다면 모든곳을 걸쳐가지 않고 key값이 박수진인것에 접근하면 되기 때문이다.
충돌
같은 인덱스끼리는 덮어씌어지며 먼저 저장된 데이터는 지워진다. 이것을 우리는 충돌 이라고 부른다.
그래서 인덱스끼리는 배열로 저장하고 같은 인덱스끼리는 LinkedList로 되어있다. 같은 인덱스가 생길 때마다 노드로 추가하는것이다.
장점
•
데이터 저장/ 읽기 속도가 빠르다.(검색 속도가 빠르다)
•
해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
•
서버에 작업을 시키지 않고 자료를 캐싱할 수 있다.
단점
•
일반적으로 저장공간이 좀 더 많이 필요하다.
•
여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.
주요 용도
•
검색이 많이 필요한 경우
•
저장, 삭제, 읽기가 빈번한 경우
•
캐쉬 구현시 (중복 확인이 쉽기 때문)
해시 테이블을 캐시로 사용하기
- 캐싱은 작업 속도를 올리는 일반적인 방법이다. 모든 대형 웹사이트는 캐싱을 사용한다. 그리고 그 자료는 바로 해시 테이블에 저장된다. 캐싱된 자료가 있으면 그 자료를 전송하고 없으면 서버에 요청하는 식으로 사용한다.
해시 테이블의 구현 코드
class LinkedTuple:
def__init__(self):
self.items = list()
def add(self, key, value):
self.items.append((key,value))
def get(self, key):
for k,v in self.items:
if key == k:
return v
class LinkedDict:
def__init__(self,length):
self.items = []
for i in range(length):
self.items.append(LinkedTuple())
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index].add(key,value)
def get(self,key):
index = hash(key) % len(self.items)
return self.items[index].get(key)
menu = LinkedDict(4)
menu.put("apple", 1000)
menu.put("potato", 500)
menu.put("melon", 9000)
menu.put("iceCream", 1500)
print(menu.get("apple")) # 1000
print(menu.get("potato")) # 500
Python
복사
