파이썬으로 알아보는 자료구조 - hash table

Hash Table

• 해시 테이블
• 키(key)에 값(데이터 - value)를 저장하는 구조
• 즉, key를 알면 한 번에 데이터를 가져올 수 있다

용어

• 해시(hash)

예시

• 파이썬의 딕셔너리(사전 - Dictionary) 데이터 타입을 생각하면 됨

장단점

장점

• 데이터의 저장 / 읽기 속도가 다른 구조와 비교했을때 매우 빠르다
• 검색 속도가 빠르다
• 데이터 중복 확인이 쉽다

단점

• 저장공간이 조금 더 필요하다
• 여러 키에 대해 동일한 해시 주소가 동일할 수도 있다. 해시 주소의 충돌을 해결하기 위해서 별도의 자료구조가 필요할 수 있다.

사례

• 검색이 많이 필요한 경우
• 저장 / 삭제 / 읽기 / 수정 작업이 자주 일어날 때
• 캐시(중복 확인이 용이하기 때문)