728x90 반응형 개별 체이닝2 11장. 해시 테이블 (3) - 충돌 처리 방식 (개별 체이닝 파이썬 구현) 다음의 기능을 제공하는 해시맵을 디자인하라.- put(key, value): 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다. - get(key, value): 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.- remove(key, value): 키에 해당하는 키, 값을 해시맵에서 삭제한다. 풀이1. 개별 체이닝 방식을 이용한 해시 테이블 구현 우리가 구현할 MyHashMap 클래스의 전체 메소드는 아래와 같다.초기화 __init__()삽입 put()조회 get()삭제 remove()class MyHashMap: def __init__(self): def put(self, key:int, value: int) -> None: .. 2024. 11. 4. 11장. 해시 테이블 (2) - 충돌 처리 방식 (개별 체이닝, 오픈 어드레싱) 파이썬 딕셔너리는 해시 테이블을 기반으로 한 자료형으로, 충돌 해결을 위해 오픈 어드레싱 방식을 사용합니다. 이를 통해 메모리 할당 오버헤드를 줄이고, 성능 저하를 막기 위해 로드 팩터를 낮게 설정하여 최적화를 이루고 있습니다. 충돌 (Collision)해시 함수가 아무리 좋아도 충돌(Collision)은 피할 수 없습니다.예를 들어, 그림 1에서 윤아와 서현의 해시 값이 모두 2로 같아 충돌이 발생했습니다.이렇게 충돌이 발생했을 때는 어떤 방법으로 이를 처리할 수 있을까요?우선 개별 체이닝(Separate Chaining) 방식을 살펴보겠습니다. 1. 개별 체이닝 (Separate Chaining)우선, 입력 데이터는 아래의 표와 같이 구성되었습니다.해시는 키를 해싱한 결과 값이며, 윤아와 서현의 .. 2024. 11. 1. 이전 1 다음 728x90 반응형
