- 오픈 어드레싱은 해시 충돌 시 빈 슬롯을 찾아 엔트리를 삽입하는 방식으로, 체이닝과 달리 같은 자리에 여러 엔트리를 넣지 않습니다. ➡️
- 충돌 발생 시, 해시 인덱스부터 시작하여 다음 빈 자리를 순차적으로 탐색하여 엔트리를 저장합니다. 🔍
- 테이블 순회 시 나머지 연산자를 사용하여 원형으로 탐색하며, 이는
put,get,delete메소드에 공통적으로 적용됩니다. 🔄 - 엔트리 삭제 시, 원래 비어 있던 자리와 삭제된 자리를 구분하기 위해 특별한 '삭제됨' 엔트리를 사용합니다. 👻
put메소드는 해시 인덱스부터 원형으로 순회하며 빈 슬롯이나 '삭제됨' 슬롯을 찾으면 삽입하고, 동일 키가 있으면 값을 갱신합니다. ➕get메소드는 해시 인덱스부터 원형으로 순회하며 키를 찾고, 빈 슬롯을 만나면 탐색을 중단하지만 '삭제됨' 슬롯은 건너뛰어 계속 탐색합니다. 🎯delete메소드는 키를 찾으면 해당 슬롯에 '삭제됨' 엔트리를 넣어 논리적으로 삭제하며, 빈 슬롯을 만나면 탐색을 중단합니다. 🗑️- 오픈 어드레싱은 모든 데이터가 배열 내에 저장되어 메모리 접근이 빠르고 캐시 효율이 높다는 장점이 있습니다. ⚡
- 단점으로는 테이블이 가득 차면 삽입이 불가능하고, '삭제됨' 엔트리 관리로 인해 삭제 처리 및 재해싱이 복잡해진다는 점이 있습니다. 🚧
Recommanded Videos
