해시테이블(Hash Table) 2

https://zuha.tistory.com/entry/해시테이블HashTable1

해시 테이블 (Hash Table) 1

 

4. 자료 구조 해시 테이블의 장단점과 주요 용도

 

장점

- 데이터 저장/읽기 속도가 많이 빠르다. (검색 속도가 빠르다.)

- 해시는 키에 대한 데이터가 있는지(중복) 확인이 쉽다.

 

단점

- 일반적으로 저장공간이 좀 더 많이 필요하다.

- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.

 

주요 용도

- 검색이 많이 필요한 경우

- 저장, 삭제, 읽기가 빈번한 경우 

- 캐시 구현 시 (중복 확인이 쉽기 때문에)

 

 

5. 프로그래밍 연습

연습 1 : 리스트 변수를 활용해서 해시 테이블 구현해보기

1. 해시 함수  : key % 8

2. 해시 키 생성 : hash(data)

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')

hash_table

hash라는 내장 함수를 거쳐온 데이터 키의 키를 8로 나눈 나머지 값을 가지고 저장 위치를 판단함.