삽입, 삭제가 O(1)이면 검색이라도 O(N)이 되어야 되는데 어떻게 모두가 다 O(1)일까?
검색이 O(1)이란 말은 인덱싱을 사용할 수 있다는 말이다.
C언어 포큐아카데미
가장 작은값 0부터 가장 큰 값 793까지의 배열을 만들고(총 794개) 값을 입력하면 1로 비어있으면 0으로 세팅한다.
이렇게 되면 입력할때 O(1)이 되고 검색할때도 인덱스를 사용할 수 있으니 O(1)이 된다. 이렇게 사용하지도 않은 메모리를 너무 많이 사용한다는 단점이 있다. 말그대로 무식 그자체다.
덜 무식하게
C언어 포큐아카데미
무식하게 모든 범위의 메모리를 잡아 두지말고 임의의 숫자에 메모리 인덱스를 매핑 시키면 좀 더 아름다워진다.
배열의 크기가 10이라고 가정하고 숫자에 메모리 인덱스를 매핑 시키는 방법은 간단하게 10으로 나눈후 나머지를 인덱스값으로 세팅하면 된다.
여기서 중요한 점은 중복이 발생한다는 점이다. 703이나 793이나 나머지는 3으로 똑같다. 이미 3번 인덱스에는 703이 들어가있는데 793의 값이 들어오면 덮어 쓸수도 없고 난감해진다. 중복을 제거해보자.(물론 불가능)
배열의 크기도 충분히 늘리고(2배) 나누는 값을 소수로 두면 중복을 최소화 할 수 있다. 하지만 중복을 막을 순 없다 중복이 하나라도 발생한다면 데이터의 신뢰성이 보장 될 수 없다. 어떻게 하면 좋을까?
중복 제거(불가능)
원칙은 나머지값의 인덱스에 값을 넣으면 되지만, 이미 그 인덱스에 값이 존재한다면(충돌) 가장 인접해 있는 빈 공간에 값을 넣으면 된다. 즉 색인을 1씩 증가 시키면서 빈 공간을 찾다가 비어 있으면 넣는다는 말이다. 물론 이때는 자신의 나머지 값을 인덱스로 같지 않는다.
일단 배열을 만들면 절대 사용하지 않을 값 INT_MIN으로 초기화 한 뒤 자신의 인덱스에 해당하는 배열에 값을 넣는다.
1. 793을 11인덱스에 넣는다
2. 724를 11인덱스에 넣으려고 한다. 하지만 793이 이미 있다
3. 인덱스를 1증가 시키면서 빈공간을 찾은뒤 가장 가까운 빈공간에 넣는다.(12 인덱스에 넣음)
4. 계속 반복
코드
#include <limits.h>
#define BUCKET_SIZE (23)
int s_numbers[BUCKET_SIZE];
void init_hashtable(void)
{
size_t i;
for (i = 0; i < BUCKET_SIZE; i++)
{
s_numbers[i] = INT_MIN;
}
}
int has_value(int value)
{
int i;
int start_index;
start_index = value % BUCKET_SIZE;
i = start_index;
do
{
if (s_numbers[i] == value) {
return true;
}
else if (s_numbers[i] == INT_MIN) {
return false;
}
i = (i + 1) % BUCKET_SIZE;
} while (i != start_index);
return false;
}
int add(int value)
{
int i;
int start_index;
start_index = value % BUCKET_SIZE;
i = start_index;
do
{
if (s_numbers[i] == value || s_numbers[i] == INT_MIN)
{
s_numbers[i] = value;
return true;
}
i = (i + 1) % BUCKET_SIZE;
} while (i != start_index);
return false;
}
int main()
{
init_hashtable();
add(703);
add(793);
add(724);
add(441);
add(219);
add(1);
add(81);
add(546);
add(777);
add(747);
return 0;
}
임의의 함수를 CALL하면(main에서 add 함수 호출) 링커가 그 구멍을 메워줄테니 일단은 컴파일하자!
어셈블러
입력값: 어셈블리 코드
출력값: 오브젝트 코드 : 기계어, 바이너리코드, 이진코드
설명: 어셈블러와 마찬가지로 구멍이 있음
포큐아카데미 C언어
링크
입력값:모든 오브젝트 코드
출력값: 실행파일(.exe 파일)
설명: 모든 오브젝트 코드를 모아다 구멍을 메꾼 뒤 실행파일로 저장
좀 더 자세히(서술): 링커가 오브젝트 파일을 다 모아서 하나의 이진(binary)파일로 만들고 있었다. 그러다가 main 함수에서 add를 호출하는 것을 보았다. 현재 main함수에 add call은 선언만 있지 정의(내용)은 없다 즉 구멍이 뚫려있다. 이것을 본 링커는 똥구멍을 긁으며 "내가 오브젝트 파일을 다 검토하고 있는데 add 함수의 정의(내용)는 XX주소에 있는걸 확인했어 그러니 그 구멍에 XX주소로 점프하는 코드를 넣어줄게!
