검색에는 선형 검색과 이진 검색을 활용할 수 있습니다. 선형 검색은 배열의 맨 앞부터 순서대로 요소를 검색하는 방식으로 O(n)의 시간복잡도를 가지며, 이진검색은 테이터가 정렬되어있는 배열에서 원하는 값을 찾아낼 수 있는 알고리즘으로, 배열의 중간에 있는 임의의 값을 선택하여 원하는 값과 비교합니다. 원하는 값이 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로 다시 탐색하고, 원하는 값이 중간 값보다 크면 중간 값을 기준으로 우측의 데이터들을 대상으로 다시 탐색합니다. 시간복잡도는 O(logN) 입니다.
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조입니다. Key값에 해시함수를 적용해 index를 생성하고 이 index에 값을 저장하면 됩니다.
해쉬 충돌은 체인법과 오픈 주소법으로 해결할 수 있습니다. 체인법은 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결합니다. 오픈 주소법은 충돌이 발생했을 때 재해싱을 수행하여 빈 버킷을 찾는 방법으로, 빈 버킷이 나올 때까지 해싱을 반복합니다.
해시 테이블의 평균 시간 복잡도는 O(1)이고 최악 시간 복잡도는 O(N)입니다.
해싱 함수를 통한 한번의 연산으로 key에 따른 value를 찾을 수 있기 때문에, 해시 테이블의 평균 시간 복잡도는 O(1)입니다. 해시 충돌 발생 시 탐색 시간 복잡도가 O(N)에 점점 수렴하게 됩니다.
빅오는 최악의 경우 시간복잡도를 의미하고, 빅오메가는 최선의 경우 시간복잡도를 의미합니다. 빅세타는 빅오와 빅오메가의 공통부분입니다. 최소와 최악의 중간인 평균적인 시간복잡도를 의미합니다.
이진 검색은 정렬된 리스트에서 이루어집니다. 먼저 배열의 중간 값을 가져와서 구하고자 하는 검색 값을 비교합니다. 만약 검색값이 중간값보다 작다면 왼쪽 구간을 대상으로, 크다면 오른쪽 구간을 대상으로 탐색합니다. 위 과정을 값을 찾거나 간격이 비어있을 때까지 반복합니다.
해시 테이블을 크게 하면 충돌 발생을 억제할 수 있어 검색, 추가, 삭제의 시간을 줄일 수 있지만 테이블의 크기를 늘리는 만큼 메모리를 많이 사용하게되는 것을 말합니다. 충돌을 피하려면 해시 함수는 해시 테이블 용량 이하의 정수를 고르게 만들어 내야 하는데, 해시 테이블의 용량은 소수가 좋다고 알려져 있습니다.
체이닝 방식은 해시값이 같은 데이터를 사슬(chain) 모양의 연결 리스트로 연결하는 방법입니다. 원하는 key를 가지고 있는 노드가 있는지 선형 탐색을 합니다. n개의 동일한 key를 갖는 value를 탐색할 때 최악의 경우, n번의 탐색 과정을 거치게 됩니다. 따라서 체인법 방식으로 조회할 때 worst case의 시간 복잡도가 O(n)입니다.