1. 해시 구조
- Key에 Value 값을 저장하는 데이터 구조이다.
- key만 알면 바로 해당 데이터를 가져올 수 있으므로 속도가 굉장히 빠르다.
- 파이썬에서는 굳이 해쉬 테이블을 구현하지 않고 딕셔너리 타입을 사용한다.
- 장점 : 데이터를 읽고 쓰는 속도가 빠르다. 키에 해당하는 데이터가 있는지 확인하기 용이하다.
- 단점 : 저장 공간이 많이 필요하다. 여러 키가 하나의 주소를 갖고 있는 경우 충돌이 일어 난다.
- 주요 용도 : 검색이 많이 필요한 경우. 데이터 저장/삭제/읽기를 자주 하는 경우.
2. 해시 테이블 관련 용어
- Hash : 임의의 값을 고정 길이로 변환하는 것을 의미한다.
- Hash Table 또는 Hash Map : 키를 이용하여 value 값을 매핑하는 자료 구조이다.
- Hashing Functiom : Key값을 넣으면 데이터 위치를 반환하는 함수이다.
- Hashing : 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 의미한다.
- Hash Value 또는 Hash Address : 데이터를 저장한 위치를 의미한다. Key를 해싱 함수에 넣으면 데이터의 위치를 일관성 있게 찾을 수 있게 한다.
출처 : 위키백과
해시 테이블 예제
hash_table = list([0 for i in range(8)])
def get_key(data):
return hash(data)
def hash_function(key):
return key % 8
def save_data(data, value):
hash_address = hash_function(get_key(data))
hash_table[hash_address] = value
def read_data(data):
hash_address = hash_function(get_key(data))
return hash_table[hash_address]
save_data('Dave', '0102030200')
save_data('Andy', '01033232200')
read_data('Dave')
# '0102030200'