What you will learn
-
자료구조의 개념 필요성, 그리고 다양한 종류의 자료구조에 대한 이해
-
set의 개념과 장점, 단점, 그리고 언제 사용하면 좋을지에 대한 이해
-
dictionary 의 개념과 생성방법, 그리고 어떻게 접근하는 지에 대한 이해
SET
-
Set은 리스트처럼 순열 자료구조이지만, 순서라는 개념이 부재.
-
데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조(collection)
-
삽입(insertion) 순서대로 저장되지 않는다. 즉 특정한 순서를 기대할 수 없는 자료구조.
-
수정 가능하다 mutable
-
동일한 값을 여러번 삽입 불가능하다. 동일 값이 여러번 삽입되면 하나의 값만 저장된다.
-
Fast Lookup이 필요할 떄 주로 쓰인다.
-
Set에서 요소들이 저장될 때 순서는 다음과 같다
-
1) 저장할 요소의 값의 hash값을 구한다.
-
2) hash값에 대하당하는 공간(bucket)에 값을 저장한다.
-
-
이렇게 set은 저장하고자 하는 값의 해쉬값에 해당하는 버켓에 값을 저장하기 때문에 순서가 없다. 순서가 없기 때문에 인덱싱도 없다.
-
그리고 해쉬값 기반의 버켓에 저장하기 때문에 중복된 값을 저장할 수 없다.
-
해쉬값을 기반으로 저장하기 때문에 look up이 굉장히 빠르다
-
Look up: 특정한 값을 포함하고 있는 지를 확인하는 것. ==> 5 in my_set
-
Set의 총 길이와 상관없이 단순히 해쉬값 계산 후 해당 버켓을 확인하면 됨으로 0(1)
-
-
hash는 단방향(one way) 암호화 이다. 단방향이란 한 번 암호화가 하면 복호화가 안된다는 뜻이다. 실제 값의 길이와 상관없이 헤쉬값을 일정한 길이를 가진다. 그러므로 hash는 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할 때 사용된다.
When To Use Set
-
중복된 값을 골라내야 할 때
-
빠른 look up 을 해야 할 때
-
그러면서 순서는 상관 없을 때
Dictionary / HashMap / HashTable
Dictionary(다른 언어에서는 hashmap이나 hash table이라고 하기도 함)는 Key-value 형태의 값을 저장할 수 있는 자료구조이다. 이름은 "정우성" 등 실제 데이터 값과 데이터를 설명하는 key의 대응 관계를 표현할 때 유용하다.
딕셔너리의 특성
- Set과 마찬가지로 특정 순서대로 데이터를 리턴하지 않는다.
- Key의 값은 중복될 수 없다. 만일 중복된 key가 있으면 먼저 있던 key 와 value 를 대체한다.
- 수정가능하다(mutable)
딕셔너리 안에 찾으려는 Key 값이 없을 경우 미리 정해 둔 디폴트 값을 대신 가져오게 하고 싶을 때에는 get(x, '디폴트 값')을 사용하면 편리하다.
>>> a.get('foo', 'bar')
'bar'
- Set와 비슷하게 key 값의 해쉬값을 구한 후, 해쉬값에 속해있는 bucket에 값을 저장한다.
- 그러므로 set과 마찬가지로 순서가 없고, 중복된 키값은 허용되지 않는다.
When To Use Dictionary
- 마치 데이터베이스처럼 키와 값을 묶어서 데이터를 표현해야 할 때 유용하다. 실제 데이터베이스에서 읽어들인 값을 딕셔너리로 변환해서 사용 자주 함.
Set 자료구조는 어떤 경우에 유용하게 사용할까? set 을 사용하면 배열의 중복 항목을 간단하게 확인하는 함수를 구현할 수 있다.
그리고 여러 배열들로부터 유일한 값을 가지는 배열을 재생성할 수 있다.
hash값은 일정한 길이를 가지고, 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할 때 사용한다.