알고리즘에서 '해시 충돌(Hash Collision)'을 해결하는 '체이닝(Chaining)' 방식이란?

Q: 알고리즘에서 '해시 충돌(Hash Collision)'을 해결하는 '체이닝(Chaining)' 방식이란?

같은 해시값을 가진 원소들을 연결 리스트나 다른 자료구조로 연결하여 하나의 버킷에 저장한다 체이닝에서 각 버킷은 연결 리스트(또는 트리)를 가지고, 같은 인덱스에 매핑된 원소들을 리스트에 추가합니다. 반면 개방 주소법(Open Addressing)은 충돌 시 다음 빈 슬롯을 탐사합니다. Java의 HashMap은 체이닝을 사용하며, 리스트가 길어지면 트리로 전환합니다.

쉬움 freeCodeCamp

보기 및 정답

A 같은 해시값을 가진 원소들을 연결 리스트나 다른 자료구조로 연결하여 하나의 버킷에 저장한다

B 충돌이 발생하면 해시 테이블의 전체 크기를 자동으로 축소하여 메모리를 절약하는 축소 관리 방식이다

C 해시 충돌이 발생한 원소를 테이블에서 즉시 삭제하고 새로운 원소만 저장한다

D 충돌 시 현재 슬롯 다음의 빈 슬롯을 순차적으로 탐색하여 데이터를 저장한다

해설

체이닝에서 각 버킷은 연결 리스트(또는 트리)를 가지고, 같은 인덱스에 매핑된 원소들을 리스트에 추가합니다. 반면 개방 주소법(Open Addressing)은 충돌 시 다음 빈 슬롯을 탐사합니다. Java의 HashMap은 체이닝을 사용하며, 리스트가 길어지면 트리로 전환합니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

로그인

추가 정보 입력

회원가입

비밀번호 찾기

알고리즘에서 '해시 충돌(Hash Collision)'을 해결하는 '체이닝(Chaining)' 방식이란?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

모두를 위한 진짜 쎈 바이브코딩