추상 자료형_2(Python)

딕셔너리

자바에서의 맵 자료형과 비슷하다고 한다.(맵을 딕셔너리로 이해해도 좋다. 뜯어보면 다른 녀석이지만 말이다.)

이전 추상 자료형들과 달리 데이터의 순서 관계를 약속하지 않는다.

Key-value 쌍 데이터를 탐색 / 삽입/ 삭제할 수 있도록 도와주는 자료형이다.

리스트와 마찬가지로 자료형 이름인 딕셔너리(Dictonary)를 그대로 가져와 사용한다.

딕셔너리에서는 탐색/ 삽입 / 삭제 연산은 O(1)의 시간 복잡도를 갖는다.

왜냐하면?

딕셔너리는 해시 테이블 자료구조로 구현되어 있기 때문이다.

 

해시 테이블에서와 마찬가지로 

하나의 key는 하나의 value만 가지고 있어야 한다.

앞서 말했던 바와같이 딕셔너리는 해시 테이블로 구현되어 있기에 충돌이 일어나는 상황에서는

Open Addressing 방법으로 충돌을 해결한다. ( github.com/python/cpython/blob/master/Objects/dictobject.c#L773 )

---

세트

한국어로 집합이란 뜻으로

딕셔너리와 마찬가지로 데이터의 순서 관계를 약속하지 않는다.

Key - value 쌍이 아닌, 데이터의 탐색/ 삽입/ 삭제를 도와주는 자료형으로 순서에 상관없이 데이터를 저장하고자 할 때 사용한다.

세트는 똑같은 데이터가 중복으로 저장되는것을 허용하지 않는다. (중복 제거의 효과가 있다)

A = {} => 빈 dict 만드는 방법
B = set() => 빈 set 만드는 방법

 

세트 또한 해시 테이블로 구현되어 있는 자료형이다.

해시 테이블은 key- value 데이터를 저장하는 자료구조라고 배웠는데 세트를 어떻게 해시 테이블로 구현할 수 있는 걸까?

답은 Key -value에서 value를 저장하지 않고 Key 값만 저장하는 것이다.

해시 테이블에서 탐색 등의 연산을 처리할 때 파라미터로 Key만을 사용했던 점을 기억하자.

따라서 Key가 저장되었는지 확인하고 탐색하고 삭제하면 되는 것이다.

어떠한 문제를 해결할 때 데이터의 순서에 상관없이 단순히 데이터 탐색/ 삽입/ 삭제를 하고자 할때 세트를 떠올리면 되겠다.

따라서 세트를 사용한 연산에서도 O(1)으로 효율적으로 사용할 수 있다.

 

출처 : 코드 잇(자료구조)

자료 구조 | 코드잇 (codeit.kr)