Chaining 개념
아이디어는 해시 테이블의 각 셀이 동일한 해시 함수 값을 가진 연결된 레코드 목록을 가리키도록 만드는 것입니다.
- 충돌이 발생한 key들은 한 위치에 모여 저장 (linked list 이용)
- Chain (linked list)를 이용하여 충돌 문제를 해결하는 방법 -> Chaining의 이유
- 두 가지 방법
- Separate Chaining
- Coalesced Chaining
Separate Chaining(분리 체인법)
충돌이 발생하면 link로 연결
Coalesced Chaining(Open Addressing)(합병 체인법)
Separate Chaining과 마찬가지로 Open Addressing은 충돌을 처리하는 방법이다. Open Addressing에서는 모든 요소가 해시 테이블 자체에 저장된다. 따라서 어느 시점에서든 테이블의 크기는 총 키 수보다 크거나 같아야 한다.
충돌이 발생할 경우
- 비어 있는 위치 중 맨 아래 (주소가 가장 큰 것) 를 선택
Hash Table 구성요소
- HA
- record
- link
LISCH(Late Insertion Standard Coalesced Hashing) Algorithm
예시: k mod 5, N: 5, (1, 5, 21, 10, 15 삽입)
EISCH(Early Insertion Standard Coalesced Hashing) Algorithm
예시: k mod 5, N: 5, (1, 5, 21, 10, 15 삽입)
LICH(Late Insertion Coalesced Hashing) Algorithm
LISCH 방법과 비슷하나 Cellar 영역이 있어서 충돌이 발생하면 Cellar 영역에 추가한다.
다음시간은 Delete를 알아보도록 하겠습니다.
meme