기출 도르마무 방에 같힌 중,
list는 왜 dictionary의 key 값이 될 수 없는가? 라는 질문이 이써꼬,
dictionary의 key는 변하는 값으로 지정할 수 없는데?
원.래.
원래가 어디써!
원래가 있지 왜 업써!
그렇다면 dictionary의 key가 무엇인가가 첫 번째!
키는 원소, 데이터의 값을 찾기 위한 식별자
인덱스에서도 한 번 살짝 거치고 갔지만,
식별자는 말그대로 식별자이니까 변하면 안되겠쥬?
dictionary라는 자료구조는
키와 값으로 이루어져 있고,
키는 해시 함수를 통해서 해시 테이블의 주소 값으로 변경
(이 때, 고유한 index 생성)되어
해시 테이블에 저장한다
일단 해시 모르겠고,
해시 테이블의 주소가 변하면 못 찾겠쥬?
자 그럼 알겠고, 해시가 뭐,,,,,라고 했,,,,,,지이,,,???
해싱은 특정 키를 해시 함수를 통해서 해시 테이블의 주소 값으로 변경한다
해싱
해시함수
해시테이블
이게 다 모람?
해시 테이블
-
해싱은 자료 구조에서 특정 값을 가장 신속하게 찾는 방법
-
키에 대한 데이터가 있는지 중복 확인이 쉽다
-
해시 함수는 어떤 키에 해당하는 값의 주소를 테이블에서 찾아주는 함수이므로 조회 속도가 매우 빠르고 간단하다.
-
해시 테이블의 특정 부분만 밀도가 높아서도 안되고, 연산도 빨라야 하고, 해시함수 값의 충돌이 적어야 함
→ 로드 팩터(Load Factor)
-
load factor = n/k
-
n : 해시 테이블에 저장된 데이터 개수
-
k : 해시 테이블의 총 칸(버킷) 개수
따라서, 로드 팩터가 증가할 수록 해시 테이블의 성능은 감소
-
-
용도 : 검색이 많이 필요한 경우, 저장/삭제/읽기가 빈번한 경우 / 캐쉬구현시(중복 확인이 쉽기 때문)
그런데 만나면?
해시 함수의 값이 이미 차버린 버킷의 인덱스를 가리킨다면?
그러니까 이미 주소가 같다!
그럼 어떻하지?
그 집이랑 합치던지
다른 주소를 찾아 가던가
Chaining & linear probing(Open Addressing)
crazy debugging으로 이게 다 뭔 소린지 한 번 보자구요
chaining 그 집에 얹혀 산다
linear probing 딴 집 찾는다
즉, 충돌이 발생하면,
chaining은 링크드리스트로 연결 → 공간을 확장
- 구현이 단순하다
- 링크드리스트로 저장하기 때문에 테이블이 가득 차지 않는다
- 해시 함수 및 로드팩터에 영향을 덜 받는다
- 사용하지 않는 공간이 발생할 수 있다
- 한 slot에 계속 저장된다면? 시간 복잡도 O(n) 최악
linear probing → 빈 저장공간을 찾는다
- linear probing은 애초에 해시함수 값이 인덱스의 시작점으로 공간을 찾기 때문에
해시 테이블의 특정 부분에 데이터가 몰릴 수 있다
→ Primary clustering
- 연속된 데이터 그룹이 생기는 현상
- 탐색 시간이 오래걸려 해싱 효율이 떨어진다
reference
https://yoongrammer.tistory.com/82
https://fierycoding.tistory.com/68
