[자료구조] 해시 테이블 (Hash Table)

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'