Hashing(해싱) 이란?(Insertion)

※ Chain을 이용한 방법(=Chaining, 폐쇄주소법이라고도 불림.)

-> 동일 Chain 내에서 Coalescing이 일어나므로 coalesed hashing이라고 불림.

 

※Hashing의 Insertion 방법

1. record의 key값이 HA(Home address)를 얻어 삽입되기 위해서 Hash되어야한다.

≫case 1. HA가 비어있는 경우, 그 주소에 record를 삽입한다. (만약 동일한 record가 이미 존재하면 삽입하지 않고 제거한다.)

≫case 2. HA가 이미 차있다면, 

• table의 맨 밑에서부터 올라오면서 빈자리를 찾는다.(만약 table에 빈자리가 없다면 record는 삽입될 수 없다.)
• 빈자리에 record를 넣고 삽입된 주소의 pointer를 HA의 pointer와 연결(Chain)한다.

※빈자리 찾는 방법

- 단순한 방법 : 빈 위치중 맨 아래의 주소를 선택

▷문제점 = 삭제 작업 후에 R의 조정 문제

1. 삭제가 일어난 위치에 d와 R의 크기를 비교하여 R을 조정해준다.

2. 즉, 만약 R < d 이면 R = d+1을 한다.

 

- 고속 방법: 빈 위치들을 chain으로 연결해 놓음.(저장은 빠르지만 검색이 빠르지는 않음)

▷빈자리들을 연결해주는 두개의 연결리스트를 사용한다.

 - forward chain: 순방향으로 빈자리들을 순서대로 연결해 준다.

 - backward chain: 역방향으로 빈자리들을 연결하여 준다.

☆주의: 두가지의 chain이 필요한 이유는 빈자리를 고속으로 관리하기 위함이다.

 

• Hashing의 모든 고간에 dummy record를 저장하여 넣는다. (dummy record : key 필드에 전혀 불가능한 키 값을 가지게 한다.)
• 빈자리의 여부 체크 -> dummy record가 들어있는지 체크하면 된다.

ex) Hash(key) = key mod 11 (즉, 0~10이 address space이다.)

27, 18, 29, 28, 39, 13, 16, 42, 17을 빈 table에 순서대로 삽입한다고 생각해보자.

Hash(HA) = 5, 7, 7, 6, 6, 2, 5, 9, 6이고 각 probe(검사)순서: 1, 1, 2, 1, 2, 1, 2, 2, 4이다.

 

 

address space	record	link
0		NULL
1		NULL
2	13	NULL
3	17	NULL
4	42	3
5	27	NULL
6	28	9
7	18	10
8	16	NULL
9	39	4
10	29	NULL

(18->29)예를 들어, record 18이 들어있는 주소 7은 주소 10과 Chain(연결) 되어있다.link에는 나타나지 않았지만 각 HA와 연결이 되어있다. 

 

※Separate Chaining(분리 체인법)

º HA가 충돌이 일어나지 않으면 삽입

º 충돌이 발생하면 연결리스트로 처리함.

- 구조가 복잡.

- 기억장소 소모량이 많음.