← 질문 목록
#381깊이 0
체이닝과 개방 주소법은 어떤 상황에서 갈리는가?
자료구조 · 알고리즘
답변 연습
내 답변 적어보기접힘
이 브라우저에 자동 저장 · 0자
모범답안 확인하기내 답변 뒤에 열어보세요
데이터 양이 불확실하고 삭제가 잦으면 체이닝을, 메모리가 한정적이고 캐시 적중률이 중요하면 개방 주소법을 고른다.
| 기준 | 체이닝 | 개방 주소법 |
|---|---|---|
| 메모리 구조 | 외부 연결 리스트 | 연속된 배열 내부 |
| 부하율 영향 | 1 이상도 가능 | 1 미만 유지 필요 |
| 캐시 적중률 | 포인터 추적으로 낮음 | 연속 공간으로 높음 |
체이닝은 배열의 각 버킷에 연결 리스트를 둔다. 충돌이 발생해도 노드를 이어 붙이면 되므로 해시 테이블이 차서 생기는 오버플로가 없다. 대신 포인터를 저장하는 메모리 비용이 늘어난다.
개방 주소법은 모든 데이터를 해시 테이블 배열 안에 저장한다. 연속된 메모리 공간을 사용하여 CPU 캐시 적중률이 높다. 하지만 테이블이 찰수록 충돌이 연속해서 터지는 탐사 길이가 길어진다.
개방 주소법에서 삭제가 일어나면 빈 슬롯과 삭제된 슬롯을 구분해야 한다. 구분 표시 없이 비워두면 검색 탐사가 중간에 끊기는 오류가 생긴다.