반응형 충돌해결2 초보 자바 프로그래밍(30) - 개방주소법 (Open Addressing) 🔖 INDEX 개방 주소법(Open Addressing)은 모든 키-값 쌍을 해시 테이블 자체에 직접 저장하는 방법입니다. 충돌이 발생하면, 다른 버킷에 키-값 쌍을 저장하는 방법을 사용합니다. 개방 주소법에는 선형 탐사(linear probing), 이차 탐사(quadratic probing), 더블 해싱(double hashing) 등의 충돌 해결 방식이 있습니다. 개방 주소법의 특징개방 주소법의 장점은 다음과 같습니다:해시 테이블 외부에 추가적인 메모리를 사용하지 않으므로 공간 효율성이 높습니다.캐시 지역성이 좋아서 연속된 메모리 위치에 데이터를 저장할 수 있습니다. 개방 주소법의 단점은 다음과 같습니다:해시 테이블의 로드 팩터가 높아지면 성능 저하가 심해집니다. 일반적으로 로드 팩터가 0.. 2023. 5. 2. 초보 자바 프로그래밍(29) - 개별체이닝 (Separate Chaining) 🔖 INDEX 개별 체이닝은 각 해시 버킷에 연결 리스트(linked list) 또는 트리와 같은 자료 구조를 사용하여 키-값 쌍을 저장하는 방법입니다. 충돌이 발생하면, 해당 버킷에 있는 연결 리스트에 새로운 키-값 쌍을 추가합니다. 개별 체이닝의 특징개별 체이닝의 장점은 다음과 같습니다:해시 테이블의 크기와 상관없이 삽입, 삭제, 검색 연산이 상수 시간에 가능합니다(연결 리스트의 길이가 작은 경우).해시 테이블의 로드 팩터가 높아져도 성능 저하가 덜 합니다. 개별 체이닝의 단점은 다음과 같습니다:연결 리스트를 사용하므로, 메모리 할당 및 해제에 추가적인 오버헤드가 발생합니다.연결 리스트를 사용하기 때문에 캐시 지역성이 떨어져 성능이 저하될 수 있습니다. 개별 체이닝 구현 예제개별 체이닝 방.. 2023. 5. 2. 이전 1 다음 반응형
