해쉬테이블

키(key)에 데이터(value)를 저장하는 데이터 구조
파이썬 딕셔너리 타입이 해쉬테이블의 키를 가지고 바로 데이터를 꺼냄
보통 배열로 미리 해쉬 테이블 사이즈만큼 생성 후 사용(공간과 탐색 시간을 바꾸는 기법)
파이썬에서는 딕셔너리 타입을 사용하면 해쉬를 별도로 구현할 필요없음

해쉬 테이블 용어

1.해쉬:임의 값을 고정 길이로 변환하는 것
2.해쉬 테이블: 키값의 연산에 의해 직접 접근이 가능한 데이터 구조
3.해싱 함수: 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
4.Hash Value 또는 Hash Address:키를 해싱 함수로 연산해서 해쉬값을 알아내고,이를 기반으로 해쉬 테이블에서 해당 키에 대한 데이터 위치를 일관성 있게 찾을 수 있음
5.Slot: 힌 개의 데이터를 저장할 수 있는 공간

hash table 만들기

hash_table = list([i for i in range(10)])
print(hash_table) #[0,1,2,3,4,5,6,7,8,9]

간단한 해쉬 함수 만들기

다양한 함수 고안 기법중,가장 간단한 방식은 Division 방식(나누기를 통해 나머지값을 사용하는기법)

def hash_func(key):
	return key % 5

해쉬 테이블 장점

1.데이터 저장/읽기 속도가 빠름(검색 속도가 빠름)
2.해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움

해쉬 테이블 단점

1.일반적으로 저장공간이 많이 필요함
2.여러키에 해당하는 주소가 동일한 경우,충돌을 해결하기 위한 별도 자료구조가 필요함

해쉬 테이블 시간 복잡도

1. 일반적인 경우는 0(1)
   2.최악의 경우 o(n)