오늘 공부한 내용📝
오늘은 자료구조 특강을 듣는 중 딕셔너리에서 데이터를 찾는 방법에 대해 학습했다. 튜터님께서 해당 내용에 관한 TIL을 작성하면 피드백을 주신다고하셔서 기회다 생각하고 해당 내용에 대해 공부해보고 글로 정리하는 시간을 가져보았다.
Q1. 딕셔너리에서 데이터를 찾는 연산의 시간 복잡도는 ?
그렇다면 그 이유는?🤔
시간 복잡도
딕셔너리에서 데이터를 찾는 연산의 시간 복잡도 평균적으로 O(1)이고 최악의 경우는 O(n)이다 .
이유:
- 딕셔너리는 Key값을 내부 함수로 변환 해 해시코드를 생성한 후 이를 배열의 크기로 나눠준다. 그리고 그 값이 배열의 인덱스가 된다.이때, 배열의 인덱스가 중복되지 않으면 값을 바로 찾기 때문에 평균 시간 복잡도는 O(1)이 된다.
- 그러나 배열의 인덱스가 중복되면 즉, 해시 충돌이 일어나면, 동일한 인덱스를 가진 여러 엔트리가 같은 인덱스에 저장되게 된다.
이때는 인덱스에서 연결리스트등을 사용해 해당 키를 찾게 된다. 이로 인해 최악의 경우는 시간 복잡도가 O(n)이 된다.
Q2. 딕셔너리에서 해싱을 통해 데이터를 찾는 과정을 설명해보시오.
딕셔너리의 값이 들어올 경우
1.해시 코드 생성
-키와 값이 딕셔너리로 추가 될 때, key를 해시 함수를 통해 해시코드로 변환해준다.
2. 버킷 배열의 크기에 따른 인덱스 계산
딕셔너리 버킷 배열의 크기가 부족하지 않으면 인덱스를 인덱스 = 해시코드 % 버킷 배열의 크기 공식으로 구해준다.
3. 버킷 배열의 크기가 부족한 경우
크기를 2배로 늘려준 후 , 기존의 모든 엔트리를 다시 재배치 해준 후 인덱스를 구해준다. 이는 해시 충돌을 최소화하기 위해서이다.
4.버킷 배열의 값 저장
이렇게 나온 버킷 인덱스 위치에 엔트리(키-값)를 저장해준다. 만약 같은 인덱스에 이미 엔트리값이 있다면(해시충돌발생), 딕셔너리는 연결리스트로 충돌된 항목들을 연결해준다.
딕셔너리에서 데이터 찾기
1. 해시 코드 생성
key 값을 해시코드로 변환해 준다. key 값이 int인 경우는 그대로 int 해시 코드를 사용하는 이유는 숫자로 데이터를 변환 해 빠르게 키 값을 찾기 위함. 문자열은 비교 연산을 사용해 복잡하고 비용이
2. 해시 코드를 버킷 배열 인덱스로 변경 해준다.
인덱스 = 해시코드 % 버킷 배열의 크기
3. 인덱스를 통해 엔트리로 접근
해시 코드를 기반으로 버킷 배열의 인덱스를 찾은 후, 해당 인덱스에 저장된 엔트리에 접근한다. 이때 중복이 없을 경우 시간복잡도는 O(1)
4. 엔트리값이 중복인 경우(해시 충돌 처리)
서로 다른 두 키값이 같은 버킷 인덱스 값을 가지는 경우 연결리스트를 통해 해당하는 키값으로 이동 한다. 이때 시간복잡도는 O(n)
😺마무리
자료구조에 대해 공부하면서 딕셔너리를 사용하는 방법은 알고 있었지만, 동작 원리는 잘 모르고 있었는데 이번에 조금이라도 알게 돼서 좋았다
'내일배움캠프' 카테고리의 다른 글
내일배움캠프: InputSystem Rebinding (인풋시스템을 활용한 키 리바인딩) (0) | 2024.10.25 |
---|---|
내일배움캠프: AnimationCurve (2) | 2024.10.24 |
내일배움캠프21: 람다식과 Func을 활용한 효율적인 코드 작성법 (2) | 2024.10.14 |
내일배움캠프 19일차 : SOLID 원칙 (0) | 2024.10.10 |
내일배움캠프 18일차: 비트연산과 LayerMask를 활용한 충돌처리 (1) | 2024.10.08 |