데이터 구조 2

오늘은 비시퀀스 데이터 구조를 배워보자.

set 보단 딕셔너리를 위주로 볼 것

 

• 비시퀀스 데이터 구조

순서가 존재하지 않아서 인덱스로 접근이 불가능

 

• set

순서도 없고 (정렬되지 않음) 요소가 중복되지 않음. (고유한 항목들)

빈 set 는 set() 로 나타낸다. {}는 빈 딕셔너리로 인식함!

 

파이썬에서 is로 시작하는 연산은 보통 T/F 를 판별한다.

ex) issubset() , issuperset()

 

• 딕셔너리

고유한 항목들(중복x), 정렬되지 않은 컬렉션, key : value 형식

 

.get(key[,default])

→ 배커스-나우르 표기법에서 [ ] = 선택 인자, 앞에 key는 필수로 들어가야 한다.

 

키가 있을 때 :

print(person[’name’]) = print(person.get(’name’))

 

print(person.get(’country’)) = None 일 때 :

print(person.get(’country’, ‘키가 없습니다.’)) = 키가 없습니다.

 

print(person.keys()) = dict_keys([’name’, ’age’])

→ 파이썬이 내부적으로 본인이 쓰는 데이터 타입이다. 대괄호로 감싸져 있다. 그럼 반복이 가능? (실제로 반복 가능)

 

.items() → 딕셔너리의 키/값을 모두 반환한다. 튜플 형태로 쌍으로 묶여서 대괄호 안에 담겨 나옴.

 

.update( )

→ 기존 딕셔너리랑 겹치는 키가 있으면 나중에 넣은 키/밸류 값이 기존 값을 덮어씌운다.

여러 인자를 넣어도 작동한다.

 

• 해시 테이블

해시 함수를 이용하여 변환한 값을 인덱스로 삼아 키/값을 저장하는 자료 구조

데이터를 효율적으로 저장하고 검색하기 위해 사용함.

키를 해시 함수를 통해 해시 값으로 변환하고 , 이 해시 값을 인덱스로 사용해서 데이터를 검색,저장

곧 바로 인덱싱이 가능해져서 데이터 검색이 아주 빠르게 이루어진다.

 

• 해시

데이터를 고정된 크기를 가진 고유값으로 변환하는 것

이 값은 해당 데이터를 식별하는데 사용될 수 있다.

파이썬에서 해시 값은 정수로 표현되고 지문처럼 식별하는 색인으로 사용된다.

 

• 해시 함수

임의의 길이의 데이터를 입력받아서 고정된 길이의 해시 값을 출력하는 함수

매우 빠른 데이터 검색을 위해 사용함.

 

set의 요소 & 딕셔너리의 키와 해시 테이블 관계

세트의 요소와 딕셔너리의 키는 해시 테이블을 이용해서 중복되지 않는 고유 값을 저장함

둘다 해시 함수를 통해 해시 값으로 변환한 후에 해시 테이블에 저장하는 원리를 사용

 

set의 pop 메서드 예시 - 정수

정수 값 자체가 곧 해시 값!

해시 값이 원래 정수니까 복잡한 연산할 거 없이 그냥 정수 값은 그 자체로 해시 값을 부여하는 것이다.

그래서 pop 으로 빼오는 순서가 항상 동일함!

 

set의 pop 메서드 예시 - 문자열

문자열은 pop으로 빼올 때마다 받는 해시 값이 달라지기 때문에 순서가 달라짐.

 

파이썬에서의 해시 함수

해시 함수 동작 방식은 객체의 타입에 따라 달라짐.

정수와 문자열은 서로 다른 타입이고 따라서 해시 값을 계산하는 방식도 다름.

 

정수는 항상 같은 해시 값을 가짐.

문자열은 가변적인 길이를 갖고 문자열에 포함된 각 문자들의 유니코드 코드 포인트 등을 기반으로 해시값을 계산하여 실행 시마다 해시 값이 다르게 계산된다.

 

• hashable

해시 함수에 넣어서 결과를 받을 수 있는 객체를 hashable 하다고 한다.

대부분의 불변형 데이터 타입은 해셔블 하다.

단, 튜플은 불변형이지만 해시 불가능한 객체를 참조할 때는 같이 해시 불가능해지는 경우가 있다.

 

hashable과 불변성 간의 관계

해시 테이블의 키는 불변해야 한다.

→ 객체가 생성된 후에 그 값을 변경할 수 없어야 함

불변객체는 해시 값이 변하지 않으므로 동일한 값에 대해 일관된 해시 값을 유지가능

단, hashable ≠ 불변하다

 

set과 딕셔너리를 쓰는 가장 큰 이유는 검색 성능 때문이다.

찾아야할 자료 수가 증가하면 일반적으로 검색 시간이 오래 걸림.

key in list 이런 명령어 쓰면 for 문이 안보여도 내부적으로는 for 문처럼 돌고 있음.

그리고 자료 수가 엄청 많으면 코드를 처리하는데 시간이 오래 걸림.

 

근데 자료가 리스트가 아니고 set , 딕셔너리일 때는 멤버십 연산자 in을 사용하면

내부적으로 for 문처럼 도는게 아니라 해시 함수로 처리해서 시간이 덜 걸린다.

따라서 시간을 단축해야할 때는 리스트말고 set 나 딕셔너리를 사용하기