Hashing(해싱)이란?(Deletion)

※ Deletion(불완전한 버전)

ex)Delete X(2)

HA	record	link
0		NULL
1	W(1)	2
2	Z(2)	3
3	Y(1)	5
4		NULL
5	M(3)	NULL
6		NULL

(1) h = 1

(2) h (=1)로부터 chain에서 삭제할 record 찾음 -> loc 2에서 X 발견

(4) s = 2

(5) s (=2)로부터 chain에서 2를 HA로 가지는 마지막 record 찾음 -> loc 4에서 Z 발견

(7) r = 4

(8) loc r (=4)의 record Z를 loc s (=2)의 record로 copy Z (2)

(9) s = r (= 4) (10) Go to (5) (5) s (=4)로부터 chain에서 4를 HA로 가지는 마지막 record 찾음

(6) 발견 실패이므로 go to (11)

(11) s (=4) ≠ h (=1) 이므로 else 상황

p = 3 (s를 가리키고 있는 loc)

f = 5 (s의 link)

Link(p) = f -> Link(3) = 5

Link(s) = NULL, Record(s) = Garbage

 

=> 문제 발생) Z(2)가 chain의 첫 노드가 아니라서 문제 발생.

 

Delete Z(2)

HA	record	link
0		NULL
1	W(1)	2
2		NULL
3	Y(1)	5
4		NULL
5	M(3)	NULL
6		NULL

(1) h = 2

(2) h (=2)로부터 chain에서 삭제할 record 찾음 -> loc 2에서 Z 발견

(4) s = 2

(6) 발견 실패이므로 go to (11)

(11) s (=2) = h (=2)

Link(s) = NULL, Record(s) = Garbage

 

=> 문제 발생) 이 record를 delete하려 할 때, 먼저 HA(=2)를 구하고 여기 (2)에서 출발하여 처리를 시작하므로 체인 상에서 이 위치(s)를 가리키는 바로 앞 선행자를 알 수 없다.

 

※Deletion(완전한 버전)

≫ case 1. del_start(h) -> HA가 h인 record X(즉, X(h) )

≫ case 2. del_middle(s, p) -> s는 현재 X의 위치, p는 X의 선행자 주소.

 

○del_start

-> HA가 s인 record를 s 주소부터 chain을 따라가면서 모두 찾는다.

≫ 1. 해당되는 record를 찾지못하면(없으면):

      -> 주소 s를 가지는 record는 삭제되는 record만 있다.

      -> s에 위치하는 record와 pointer를 비우고 del_start를 끝낸다.

≫ 2. 해당되는 record가 있으면:

      -> r이 그러한 record(주소를 s로 가지는 record)가 있는 마지막 위치이고, p가 r의 전임자의 loc(위치)이 된다고 하

         자.

      -> del_middle을 실행한다.

 

○del_middle

-> Chain에서 s의 후속부터 시작하여 HA가 s인 레코드를 찾는다.

≫ 1. 해당 기록을 찾을 수 없는 경우:
      -> Chain에서 주소(위치) s를 건너뜁니다. ((loc p의 link field에 loc s의 link 값을 넣음)
      -> dummy record 및 NULL pointer를 저장하여 loc s를 비웁니다.

≫ 2. 해당 record을 찾았을 경우:

      -> s에서 시작하는 chain 요소의 위치 집합이 D라고 하자.

      -> s의 뒤를 잇는 것부터 시작해서,  HA가 D가 아닌 체인의 마지막 레코드를 찾으세요.

         (이러한 record는 chain에서 s 앞에 있는 요소의 위치 집합에 있는 HA를 가집니다.)

      -> 이때, 해당 reocrd를 찾았을 경우:

          -> r을 이 레코드의 위치로 하고 p를 r의 전임자의 loc으로 한다.
          -> r의 레코드는 s로 이동됩니다(loc r의 레코드로 loc s를 덮어씁니다).
          -> del_middle(r, p) 호출

      -> else:

          -> loc p의 link 파일을 NULL로 설정합니다.  // 이것은 분리를 달성합니다.
          -> chain의 첫 번째 요소인 s에서 record 삭제를 완료하려면 del_start(s)  // 호출

 

ex) Delete X(1) = 2에 위치

HA	record	link
0		NULL
1	W(1)	2
2	Y(1)	3
3	Y(1)	4
4	Z(2)	5
5	M(3)	NULL
6		NULL

(1) h = 1 -> 자신의 HA에 저장되어 있는 경우가 아니므로 case 2

- chain에서 loc h로부터 record X 위치 찾음

- loc 2에서 발견 -> r = 2, p = 1 (r=현재 위치, p=r의 전임자)

- Call del_middle(r=2, p=1)

 

(2) del_middle(2, 1) : s=2, p=1

- chain에서 loc 3부터 HA를 s (=2)로 가지는 last record 찾음

- loc 4에서 Z 발견 -> D(s) = {2, 3, 4, 5}, D'(s) = {1}

- loc 3에서 시작하여 D(s)에 속하지 않는 HA를 가진 최종 노드를 찾음

- loc 3에서 Y 발견 -> r = 3, p = 2

- loc r (=3)의 record Y를 loc s (=2)로 overwrite

- Call del_middle(r=3, p=2)

HA	record	link
0		NULL
1	W(1)	2
2	Y(1)	3
3	Z(2)	5
4	dummy	NULL
5	M(3)	NULL
6		NULL

(3) del_middle(3, 2) : s=3, p=2

- chain에서 loc 5부터 HA를 s (=3)로 가지는 last record 찾음

- loc 5에서 M 발견 -> D(s) = {3, 4, 5}, 𝐷(s) = {1, 2}

- loc 4에서 시작하여 D(s)에 속하지 않는 HA를 가진 최종 노드를 찾음

- loc 4에서 Z 발견 -> r = 4, p = 3

- loc r (=4)의 record Z를 loc s (=3)로 overwrite

- Call del_middle(r=4, p=3)

 

(4) del_middle(4, 3) : s=4, p=3

- HA를 s (=4)로 가지는 last record를 chain의 아래에서 찾아야 하는데 loc 5 다음에는 노드가 없으므로 발견 실패

- loc 4을 chain에서 skip

- Empty the loc s (=4) -> loc p (=3)의 link field에 loc s (=4)의 link field를 넣고 loc s (=4)에 dummy record를 저장

 

ex) Delete W(1)

HA	record	link
0		NULL
1	X(1)	NULL
2	X(1)	3
3	Y(2)	4
4	Z(3)	5
5	M(2)	6
6	N(5)	NULL
7		NULL

(1) h = 1 -> 자신의 HA에 저장되어 있는 경우이므로 case 1 -> del_start(1) 호출

 

(2) del_start(1) :

- chain에서 loc 2부터 HA를 s (=1)로 가지는 last record 찾음

- loc 2에서 X 발견 -> r = 2, p = 1

- loc r (=2)의 record X를 loc s (=1)로 overwrite

- Call del_middle(r=2, p=1)

 

(3) del_middle(2, 1) : s=2, p=1

- chain에서 loc 3부터 HA를 s (=2)로 가지는 last record 찾음

- loc 5에서 M 발견 -> D(s) = {2, 3, 4, 5, 6}, 𝐷(s) = {1}

- loc 3에서 시작하여 D(s)에 속하지 않는 최종 노드를 찾음 -> 발견 실패 (chain separation)

- loc p (=1)의 link field를 NULL

- Call del_start(s=2)

HA	record	link
0		NULL
1	X(1)	NULL
2	M(2)	3
3	Y(2)	4
4	Z(3)	NULL
5	M(2)	6
6	N(5)	NULL
7		NULL

(4) del_start(2) :

- chain에서 loc 3부터 HA를 s (=2)로 가지는 last record 찾음

- loc 5에서 M 발견 -> r = 5, p = 4

- loc r (=5)의 record M를 loc s (=2)로 overwrite

- Call del_middle(r=5, p=4) 

 

(5) del_middle(5, 4) : s=5, p=4

- chain에서 loc 6부터 HA를 s (=5)로 가지는 last record 찾음

- loc 6에서 N 발견 -> D(s) = {5, 6}

- loc 6에서 시작하여 D(s)에 속하지 않는 최종 노드를 찾음 -> 발견 실패 (chain separation)

- loc p (=4)의 link field를 NULL

- Call del_start(s=5)

HA	record	link
0		NULL
1	X(1)	NULL
2	M(2)	3
3	Y(2)	4
4	Z(3)	NULL
5	N(5)	NULL
6	dummy	NULL
7		NULL

(6) del_start(5) :

- chain에서 loc 6부터 HA를 s (=5)로 가지는 last record 찾음

- loc 6에서 N 발견 -> r = 6, p = 5

- loc r (=6)의 record N를 loc s (=5)로 overwrite

- Call del_middle(r=6, p=5)

 

(5) del_middle(6, 5) : s=6, p=5

- HA를 s (=6)로 가지는 last record를 chain의 아래에서 찾아야 하는데 loc 6 다음에는 노드가 없으므로 발견 실패

- loc 6을 chain에서 skip

- Empty the loc s (=6) -> loc p (=5)의 link field에 loc s (=6)의 link field를 넣고 loc s (=6)에 dummy record를 저장