포인터 기반의 연결 방식(4) - 추상 데이터 타입(해시테이블)

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 자료구조 내용입니다

목차

• 추상 데이터 타입 - 해시테이블

• 해시 충돌

<추상 데이터 타입 - 해시테이블>

해시테이블(Hash Table)

• 키(Key)에 데이터(Value)를 저장하는 데이터 구조  ex)딕셔너리 타입
  
• ※파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨.
• 각각의 Key(해싱함수에 넣어 해쉬 주소 알아냄)를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐.
• 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용

알아둘 용어

• 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
  
• 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  
• 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터(Value) 위치를 찾을 수 있는 함수
  Key를 해싱 함수로 연산해서, 해쉬 주소를 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 알 수 있음

시간 복잡도

조회, 삭제, 삽입 - O(1)

해시 충돌 발생하면 - O(n)

 

해시 충돌 : 여러 키에 해당하는 (해쉬함수를 통해 만들어낸) 해쉬주소가 동일한 경우 충돌이 발생하는 것.

키가 중복되지 않도록 데이터를 고루 분산시킬수 있는 해쉬함수를 사용하거나(ex. SHA) 각 버킷에 키-값 쌍의 연결 리스트를 저장하는 것이 해쉬 충돌을 해결할 수 있다.