체이닝 (chaining) 앞서 충돌이 일어났을 경우 해시 함수를 변형해 다른 버킷에 삽입 하는 방식이었습니다. 그러나 비어있는 곳을 찾기 위해 시간이 더 소요되는 단점이 있었습니다. 체이닝은 해시 테이블의 구조를 변경해 각 버킷이 하나 이상의 값을 저장할 수 있도록 하는 것입니다. 즉, 오버플로우 문제를 해결하는 방식을 기존의 각 버킷에 고정된 슬롯을 할당하는 대신 삽입과 삭제가 용이한 연결 리스트로 변경해 해결하는 것입니다. 체이닝 구현 해시 함수 설정 충돌이 일어났을 시 새로운 연결 리스트의 노드를 생성해주면 되기 때문에 체이닝에서 해시 함수는 어느 것을 사용해도 상관 없습니다. int hash_function(int key) { return key % TABLE_SIZE; } 연결 리스트 체이닝 ..

개방 주소법 (open addressing) 개방 주소법은 특정 버킷에서 충돌이 발생하면, 비어있는 버킷을 찾아 항목을 저장하게 됩니다. 해시 테이블에서 비어있는 공간을 찾는 것을 조사(probing)라고 합니다. 선형 조사법 (linear probing) 선형 조사법은 충돌이 발생한 곳에서 다음 버킷이 비어있는 곳이 나올 때까지 계속해서 조사하는 방법입니다. 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 갑니다. 선형 조사법 구현 삽입 연산에서 해당하는 해시 값에 비어있는지 검사합니다. 비어 있으면 해당 버킷에 삽입합니다. 비어 있지 않으면 그 주소에 저장된 키와 동일한지 체크합니다. 동일하지 않다면, 주소를 나타내는 변수를 1 증가해 다음 버킷을 가리키도록 합니다. void hash_lp_..

해시 함수 해싱에서는 키 값을 해시 테이블의 주소로 변환하는 해시 함수가 잘 설계되어있어야 탐색의 효율을 높일 수 있습니다. 좋은 효율을 가지고 있는 해시 함수는 다음과 같은 특징을 가집니다. 충돌이 적어야 함 해시 함수 값이 해시 테이블 주소 영역 내 고르게 분포되어야 함 계산이 빨라야 함 제산 함수 제산 함수는 나머지 연산자를 사용해 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법입니다. $$ h(k) = k \space mod \space M $$ 여기서 $M$은 해시 테이블의 크기입니다. 해시 테이블의 크기를 어떻게 해야 해시 주소가 좋은 효율을 가지게 될까요? 답은 소수(prime number)입니다. $M$이 짝수라면 메모리 주소는 대부분 짝수이므로 해시 함수값 또한 짝수가..

해싱이란? 해싱(Hashing)은 키(key)에 산술적인 연산(해시 함수)을 적용해 항목이 저장되어 있는 테이블의 주소를 계산해 항목에 접근합니다. 해시 함수(hash function): 키를 입력으로 받아 해시 주소(hash address)를 생성 해시 테이블(Hash Table): 키에 대한 연산에 의해 직접 접근이 가능한 구조 해싱(Hashing): 해시 테이블을 이용한 탐색 해싱의 구조 탐색 키들의 문자열이나 매우 큰 숫자가 나오는 경우에 탐색 키를 직접 배열의 인덱스로 사용할 수는 없으니 작은 정수로 매핑(함수의 사상)시키는 어떤 함수가 필요합니다. 키값 $k$를 입력받아 해시 함수로 연산한 결과인 해시 주소 $h(k)$를 인덱스로 사용해 해시 테이블에 있는 항목에 접근합니다. 해시 테이블 버킷..

AVL 트리란? AVL 트리는 트리가 비균형 상태로 되면 스스로 노드들을 재배치해 균형 상태로 만듭니다. 이 탐색 기법에서는 균형 인수라는 것을 정의합니다. 균형 인수 (Balance Factor) = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 모든 노드의 균형 인수가 $\pm 1$ 이하이면 AVL 트리입니다. 여담으로, Adelson-Velskii와 Landis의 제안자 이름을 따 AVL이라고 지어졌습니다. AVL 트리 구현 AVL 트리의 핵심은 균형 인수를 1 이하로 맞추는 것입니다. AVL 트리인 상태에서 균형 인수가 깨지게 될 경우는 삽입 연산, 삭제 연산 총 두 가지입니다. 연산을 수행하고 생기는 결과의 경우에 따라 균형 인수를 1 이하로 맞출 수 있도록 대응해주면 됩니다. 그렇다면 어..

보간 탐색이란? 보간이라는 어휘가 생소해 사전에서 찾아봤습니다. 요약하자면, 몇 가지 알려져있는 함숫값으로 임의의 값을 추정하는 탐색 기법임을 알 수 있습니다. 말로만 들으면 생소하다고 생각됩니다. 자세한 건 아래 그림과 함께 살펴보겠습니다. 보간 탐색에서는 찾고 싶은 $key$값과 $low$, $high$ 값을 고려해 $pos$(탐색 위치)를 결정합니다. 위의 그림을 수식으로 표현하면 다음과 같습니다. pos에 대한 식으로 변경해보겠습니다. $$ pos = {(high - low) \times (k - list[low]) \over list[high] - list[low]} + low $$ 코드로 구현하면 다음과 같습니다. int interpol_search(int key, int n) { int lo..

색인 순차 탐색이란? 색인 순차 탐색은 인덱스 테이블을 사용해서 탐색의 효율을 높이는 방법입니다. 인덱스 테이블 (index table) 탐색하려고 하는 리스트의 일정 간격으로 떨어져 있는 요소들을 가지고 온 테이블입니다. 정렬된 리스트의 데이터 수가 $n$개이고, 인덱스 테이블의 크기가 $m$이라면 각 인덱스 항목은 정렬된 리스트의 각 $n/m$번째 데이터를 가지고 있습니다. 색인 순차 탐색 구현 색인 순차 탐색의 핵심은 인덱스 테이블입니다. 인덱스 테이블에서 찾고자 하는 값이 있는 범위만 조사합니다(index_table[i].key ≤ x < index_table[i + 1].key). 어느 범위에 있는지 알아냈다면, 해당 범위에서만 순차 탐색을 수행합니다. 코드로 구현하면 다음과 같습니다. int ..