반응형
collision
-
[ 비선형 자료구조 ] 해시 테이블(Hash Table)Computer Science/자료 구조 2023. 3. 9. 18:07
1. 해시 테이블 해시 테이블은 key-value 쌍으로 데이터를 저장하는 자료구조입니다. 해시 테이블은 내부적 배열을 이용하며, 각 key에 해시 함수를 적용해 얻은 인덱스에 value를 저장합니다. 이때 value가 저장되는 장소를 슬롯이라 하며, 이러한 특성을 바탕으로 데이터 검색에서 빠른 퍼포먼스를 보여줍니다. 즉, 해시 테이블에서 각 key는 대응되는 인덱스를 가지며 O(1)의 시간 복잡도를 보여줍니다.(해시 테이블에 데이터가 찰수록 충돌 발생 가능성이 높아지고 가용 가능한 슬롯의 검색에 대한 비용이 추가되어 O(N) 까지 증가할 수 있습니다.) 해시 함수는 문자열 혹은 다른 데이터 타입의 인풋 인자를 받아 인풋 인자에 대응하는 고유하고, 고정된 사이즈의 아웃풋(일반적으로 수 혹은 문자열)을 출..