Data Structure - 02

1. Set

Set은 array나 list처럼 순열 자료구조(collection)이지만, 순서라는 개념이 존재하지 않는다.
아래는 Set의 특징을 나열한 것이다.

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

>>> my_set = {1, 2, 3, 4, 5, 1, 2}
>>> my_set
{1, 2, 3, 4, 5}
>>> for i in my_set:
...     print(i)
...
1
2
3
4
5
>>> my_set.append(7)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'set' object has no attribute 'append'
>>> my_set[0]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'set' object does not support indexing
>>> my_set.add(7)
>>> my_set
{1, 2, 3, 4, 5, 7}
>>>
>>> 5 in my_set # look up
True

• Array와 달리 Set은 요소들을 순차적으로 저장하지 않는다.
• Set에서 요소들이 저장될 때 순서는 다음과 같다.
  • 저장할 요소의 값의 hash값을 구한다.
  • hash값에 해당하는 공간(bucket)에 값을 저장한다.
• 이렇게 Set은 저장하고자 하는 값의 hash값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없고, indexing 또한 불가능하다.
• 또한 hash값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없다.
• hash값을 기반으로 저장하기 때문에 look up이 굉장히 빠르다.
  • Look up: 특정 값을 포함하고 있는 지를 확인하는 것 ==> 5 in my_set
  • Set의 총 길이와 상관없이 단순히 hash값 계산 후 해당 bucket을 확인하면 되므로 0(1)

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

When to use Set

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

https://youtu.be/2BldESGZKB8

2. Dictionary

Dictionary(다른 언어에서는 hashmap이나 hash table이라고 하기도 함)는 Key-value 형태의 값을 저장할 수 있는 자료구조이다. Dictionary의 특징은 아래와 같다.

• Set와 마찬가지로 특정 순서대로 데이터를 리턴하지 않는다.
• Key값은 중복될 수 없고, 중복된다면 먼저 있던 key와 value를 대체한다.
• 수정 가능하다.(mutable)

>>> my_dict = {1 : "one", "two" : 2, 3 : 3.0, 1: "one_one"}
>>> my_dict
{1: 'one_one', 'two': 2, 3: 3.0}
>>> for key, value in my_dict.items():
...     print(f"{key} : {value}")
...
1 : one_one
two : 2
3 : 3.0
>>> my_dict[1]
'one_one'
>>> my_dict.get("two")
2
>>> my_dict[5]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 5
>>> my_dict.get(5, 0)
0
>>> my_dict[7] = "Seven"
>>> my_dict
{1: 'one_one', 'two': 2, 3: 3.0, 7: 'Seven'}

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

When to use Dictionary

• Database처럼 Key와 Value값을 묶어서 데이터를 표현해야 할 때 유용하다.
  실제로 Database에서 읽어들인 값을 Dictionary로 변환해서 자주 사용해야 한다.