20.5.18
자료 구조 두 번째 세션이다.

이번에는 데이터 구조의 종류 중 Set, Dictionary, Hash에 대해 알아보도록 하겠다.

Set

set은 Array나 list처럼 순열 자료구조(collection)이다. 하지만 set은 순서라는 개념이 존재하지 않는다.
Set의 특징은 다음과 같다.

• 데이터를 비 순차적(unordered)으로 저장할 수 있는 순열 자료구조(collection)이다.
• 삽입(insertion)순서대로 저장되지 않는다. 즉 특정한 순서를 기대할 수 없는 자료구조이다.
• 수정 가능하다. (mustable)
• 동일한 값을 여러번 삽입 불가능하다. 동일한 값이 여러번 삽입되면 하나의 값만 저장된다.
• Fast Lookup이 필요할때 주로 쓰인다.

Set의 구조

Array와 달리 set은 요소들을 순차적으로 저장하지 않는다. Set에서 요소들이 저장될 때 순서는 다음과 같다.
1. 저장할 요소의 값의 hash 값을 구한다.
2. 해쉬값에 해당하는 공간(bucket)에 값을 저장한다.

이렇게 set은 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없다. 순서가 없기 때문에 indexing도 없다. 그리고 해쉬값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없는 것이다.

hash값을 기반으로 저장하기 때문에 look up이 굉장히 빠르다.

• Look up : 특정 값을 포함하고 있는지를 확인 하는 것 --> 5 in my_set
• set의 총 길이와 상관없이 단순히 해쉬값 게산 후 해당 bucket을 확인 하면 된다. 0(1)

list는 넣는대로 추가되지만 set은 list와 대부분 같지만 중복된 값은 허용하지 않는다.

set을 사용하는 경우

• 중복된 값을 골라내야 할 때
• 빠른 look up을 해야할 때
• 순서는 상관 없을 때

Hash

Hash는 단방향 (one way)암호화 이다. 단방향이란 한번 암호화 하면 복호화가 안된다는 뜻이다. 실제 값의 길이와 상관없이 일정한 길이를 가진다. 따라서 hash는 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할 때 사용된다.

Dictionary

key-value 형태의 값을 저장할 수 있는 자료 구조
실제 데이터 값과 데이터를 설명하는 key의 대응 관게를 표현할 때 유용하다.

Dictionary의 특성

set과 마찬가지로 특정 순서대로 데이터를 리턴하지 않는다. key의 값은 중복될 수 없다. 중복된 key가 있으면 먼저 있던 key와 value를 대체한다.

Dictionary의 내부 구조

Set와 비슷하게 key 값의 해쉬값을 구한 후 해쉬값에 속해있는 bucket에 값을 저장한다.
set와 마찬가지로 순서가 없고 중복된 key 값은 허용 되지않는다.

When To Use Dictionary

데이터베이스처럼 키와 값을 묶어서 데이터를 표현해야 할때 유용하다. 데이터베이스에서 읽어들인 값을 dictionary로 변환해서 사용 자주 한다.