목록2024/01/25 (1)
개발하는 리프터 꽃게맨입니다.
[C++/자료구조] 해쉬 입문
1. 해쉬란? 1) 개요 탐색에 있어서 매우 강력한 자료구조입니다. 앞서 살펴봤던 배열, 연결리스트의 경우 삽입/삭제/탐색 에 있어서 O(N) 트리 기반 자료구조의 경우 삽입/삭제/탐색 에 있어서 O(log2 N) 의 시간 복잡도가 소요됩니다. 하지만 해쉬의 경우 O(1) 라는 매우 빠른 시간에 삽입/삭제/탐색을 수행할 수 있죠. 그런데, 어떻게 이런 일이 가능할까요? 해쉬는 키를 해쉬함수를 통해 유의미한 정수로 바꿉니다. 그리고 해쉬테이블에 데이터를 저장하죠. 이런 일련의 과정을 해싱이라고 합니다. 잘 이해가 안가신다면 이렇게 생각해보세요. 사이즈 100의 배열이 있고, 우리가 접근하고 싶은 데이터의 주소를 알고있다면 바로 접근이 가능하잖아요? 이것을 기본 개념으로 출발합니다. key값을 해쉬테이블을 ..
자료구조/자료구조 이론
2024. 1. 25. 13:54