데이터구조.2 Set & HashMap(ditctionary)

https://www.notion.so/Data-Structure-2-Set-Dictionary-Hash-ffa428d2ef8149a7841a5ebbc80459ec

Set이란

array나 list처럼 순열자료구조(collection), but set에는 순서라는 개념이 없다.

Set 특징

• 데이터를 비순차적으로 저장하는 순열자료구조 (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

Set 구조

• array와 달리 set은 순차적으로 저장하지 않는다.
• set에서 요소들이 저장될 때 순서는 다음과 같다.
  1. 저장할 요소의 값의 hash 값을 구함
  2. 해쉬값에 해당하는 bucket에 값을 저장함.
• 위와같이 set은 저장하고자 하는 값의 hash값을 해당하는 bucket에 저장하기 때문에 순서가없다. 그래서 index가 존재 않는다.
• hash값 기반의 bucket에 저장되기 때문에 중복된 값을 저장 할수없다.
• hash값 기반으로 저장하기 때문에 lookup 이 빠르게 가능하다
  • look up: 특정 값을 포함하고 있는지를 확인 하는것 ex) 5 in my_set
  • set의 총 길이와 상관없이 단순히 hash값 계산 후 해당 bucket을 확인하면 됨 0(1)

• hash는 one way 암호화 이다. 원웨이란 한번 암호화를 하면 복호화가 안된다.
• 실제 값의 길이와 상관없이 hash 값은 일정한 길이를 가집니다.
• 그럼으로 hash는 주로 임이의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 mapping할때 사용됩니다.

HashMap
hashmap이란?
kay-value형태의 값을 저장할 수 있는 자료구조.

ex) 이름은 "정우성" --> 실제 데이터 값과 데이터를 설명하는 key의 대응관계를 표현할때 유용하다.

• set과 마찬가지로 특정 순서대로 데이터를 리턴하지 않는다.
• key의 값은 중복될 수 없다. (만일, 중복된 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'}

hashmap 내부구조

• set과 비슷하게 key값의 hash값을 구한후 hash값에 속해있는 buck에 값을 저장한다.
• 그럼으로 set과 마찬가지로 순서가없고 중복된 key값을 허용되지 않는다.

언제사용하는가?

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