선형 탐색법 - 해시 테이블

 

자료 삽입 순서 : GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E

 

자료를 삽입하기에 앞서,

반드시 다음과 같은 배열 구조를 그려야 한다.

숫자는 메모리 주소를 나타내고, 알파벳은 그 주소에 들어가야 할 데이터의 첫 글자를 나타낸다.

예를들어 데이터가 A7이라면 A7의 첫 글자는 A이기 때문에 1번 주소에 들어가야 하고,

데이터가 QA라면 QA의 첫 글자는 Q이기 때문에 17번 주소에 들어가야 한다.

 

 

 

자료 삽입 순서 : GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E

제시된 글자의 첫 글자와 일치하는 주소에 해당 데이터를 삽입한다.

자료 삽입 순서를 보면 GA가 가장 먼저 제시되었기 때문에 GA부터 시작한다.

GA는 G로 시작하기 때문에 G로 시작하는 7번 주소에 자료를 삽입한다.

 

 

자료 삽입 순서 : GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E

이제는 두번째 데이터인 D를 삽입해야 한다.

데이터 D의 첫글자는 D이기 때문에 D의 위치에 해당하는 4번 주소에 삽입한다.

 

 

자료 삽입 순서 : GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E

이제는 데이터 A와 G, L 순서대로 자료를 삽입해보자. 이전의 방법과 동일하다. 한번 시도해보길 바란다.

 

 

 

---

 

데이터 A는 A로 시작하기 때문에 A위치에 해당하는 1번 주소에 삽입한다.

 

 

데이터 G는 G로 시작하기 때문에 G위치에 해당하는 7번 주소에 삽입한다.

 

어? 그런데 G위치에 해당하는 7번 주소에 데이터 GA가 이미 들어있다.

선형 탐색법으로 해시 테이블을 구성하기 위해 가장 핵심이 되는 부분이다.

어떻게 배치하면 될 지 과정과 결과를 반드시 기억해야 한다. 한번 고민해보자.

 

 

이미 G에 해당하는 7번 주소에 데이터 GA가 들어있다.

그렇다면, GA의 바로 다음 주소인 8에 G를 삽입해야 한다.

 

 

그러면 이제 또 새로운 고민이 생기게 되는데,

주소 8에 해당하는 H자리는, H가 와야하는것이 아니었나? 한번 생각해봐야할 문제다. 뒷부분에서 다시 다뤄보기로 한다,

 

이제, 데이터 L을 삽입해야 하는데

데이터 L은 L로 시작하기 때문에 L위치에 해당하는 12번 주소에 삽입한다.

 

 

자료 삽입 순서 : GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E

이제는 데이터 A2를 삽입해야 한다.

삽입하려고 보니 이미 A에 해당하는 1번 주소는 A로 채워져 있다.

앞서 실습해본 G와 GA내용과 동일하게 적용하면 된다.

1번의 다음 주소인 2번 주소에 A2를 삽입하면 된다.

 

 

자료 삽입 순서 : GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E

이제는 데이터 A1을 삽입해보자.

데이터 A1을 삽입하려고 보니 이미 A에 해당하는 1번 주소는 A로 채워져 있다.

그리고 그 다음 주소에 삽입하려고 보니 A2로 채워져 있다.

그렇다면 어떤 위치에 삽입하면 될까?

간단하다. A1도 동일한 규칙을 적용하면 된다.

1번 주소가 원래 채워져야 하는 주소였지만 채워져있다면 다음 주소인 2번 주소를 보자.

만약 2번 주소도 채워져 있다면 그 다음 주소인 3번 주소에 데이터를 삽입하면 된다.

즉, A1을 3번 주소에 삽입하면 된다.

 

 

자료 삽입 순서 : GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E

이제는 데이터 A3과 A4를 삽입해보자.

데이터 A3을 삽입하려고 보니 이미 A에 해당하는 1번 주소는 A로 채워져 있다.

그리고 그 다음 주소에 삽입하려고 보니 A2로 채워져 있다. 그리고 그 다음 주소에 삽입하려고 보니 A1으로 채워져 있다. 또 그 다음 주소를 확인해보니 4번 주소에 D가 채워져 있다.

A3를 채워야 해서 A부터 탐색했더니 중간에 D가 끼워져있다.

이런 경우에도 앞서 설명한 것과 동일한 규칙을 적용하면 된다.

데이터를 채우려고 확인했는데, 해당하는 주소에 데이터가 이미 들어있다. 그런 경우, 다음 주소에 데이터를 삽입한다.

 

단순히 5번 주소에 A3을 삽입하면 된다.

 

 

이제 A4와 Z를 어디에 삽입해야할지 생각해보자.

 

---

 

 

 

 

자료 삽입 순서 : GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E

이제 ZA를 삽입해야 할 순서이다.

한번 시도해보자.

 

 

---

ZA를 삽입하기 위해 Z에 해당하는 26번 주소를 확인하니 이미 Z가 들어있다.

그렇다면 다시 동일한 규칙을 

데이터를 채우려고 확인했는데, 해당하는 주소에 데이터가 이미 들어있다. 그런 경우, 다음 주소에 데이터를 삽입한다.

그 다음 주소를 어디라고 생각해야할지 고민한다면,

다시 1번 주소로 돌아가는 것을 그 다음 주소라고 생각해야 한다.

 

 

그리고

데이터를 채우려고 확인했는데, 해당하는 주소에 데이터가 이미 들어있다. 그런 경우, 다음 주소에 데이터를 삽입한다.

이제까지와 동일한 규칙을 적용하면 된다.

 

 

탐색 결과 9번 주소가 비어있다. 9번 주소에 ZA를 삽입하면 된다.

 

 

자료 삽입 순서 : GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E

그리고 마지막으로 데이터 E를 삽입해보자.

 

 

---

 

데이터 E를 삽입하기 위해 E의 위치인 5번 주소를 확인했더니 데이터가 이미 들어있다면,

앞서 동일한 규칙으로 데이터의 삽입 위치를 찾아주면 된다.

 

 

모든 데이터의 삽입을 완료했다.

 

기억해야 할 내용들을 짚어보면서 글을 마무리하기로 한다.

 

1) 데이터(예 : G)를 삽입하려는 위치에 같은 종류의 데이터(예 : GA)가 이미 들어있는 경우, 데이터를 어느 위치에 삽입해야 할까?

2) 이미 다른 종류의 데이터(예 : A)로 채워진 경우, 새로운 데이터(예 : E)는 어느 위치에 삽입해야 할까?

3) 가장 마지막 주소에 데이터가 채워져있다면, 그 다음 주소는 어디로 생각해야 하는걸까?