[Data Structure] Hash Table

1️⃣ Hash Table

해시 테이블의 구조

• key에 value를 저장하는 데이터 구조

  • key를 통해 바로 데이터를 받아오기 때문에, 다른 자료구조에 비해 검색 속도가 빨라진다.

  • 보통 배열로 미리 해시 테이블의 크기를 생성한 후에 사용한다.

  • Python - Dictionary (파이썬에선는 해시를 별도로 구현하지 않고 딕셔너리를 사용)

    
    

해시 테이블의 장단점

• 장점
  • 검색 속도가 빠르다. (저장/읽기 속도)
  • 데이터의 중복 처리가 쉽다. → 배열처럼 하나씩 데이터를 거쳐가며 확인할 필요 없이, 키에 대한 데이터만 확인하면 되므로
    
• 단점
  • 저장공간이 일반적으로 더 많이 든다.
    → 해시테이블이 데이터가 없더라도 저장공간을 마련해 둔다.
    
  • 충돌(여러 키가 동일한 주소를 갖는 경우)을 해결하기 위한 별도의 조치가 필요하다.
• 활용

  • 검색이 잦은 경우

  • 저장, 삭제, 읽기가 많은 경우

  • 캐시 구현 (중복 확인이 유용하기 때문에)

    
    

용어

• Hash : 임의의 값을 고정길이로 변환

• Hash Table : 키값이 해시 함수 연산을 거쳐 직접 접근이 가능하도록 한 데이터 구조

• Hashing Function : key를 넣으면 산술 연산을 실행해 찾고자 하는 데이터의 위치를 알아내는 함수

• Hash Value / Hash Address : key의 hashing function 연산 결과로 해시값을 구하고, 이를 통해 해시 테이블에서 해당 key에 대응하는 데이터의 위치를 일관성 있게 찾을 수 있다.

• Slot : 한 개의 데이터를 저장할 수 있는 공간

  
  

---

2️⃣ 해시테이블 구현하기 예제

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_func(key):
    return key % 5

def save_data(data, value):
    hash_address = hash_func(get_key(data))
    hash_table[hash_address] = value

def read_data(data):
    hash_address = hash_func(get_key(data))
    return hash_table[hash_address]

---

3️⃣ 충돌(Collision) 해결 알고리즘

추가 예정

---

📂 참고 자료

https://www.fun-coding.org/post/Chapter09-hashtable-live.html#gsc.tab=0