자료구조 TIL - 2. Set, Dictionary, Hash

Set

• Array나 List와 같은 순열 자료구조(Collection) 단, 순서의 개념이 존재하지 않음
• Set를 사용하면 좋은 상황
  • 중복된 값을 골라내야 할 때
  • 빠른 Look up을 수행해야 할 때
  • 순서가 상관 없을 때
• 특징
  • 데이터를 비순차적으로 저장할 수 있는 순열 자료구조
  • 삽입(Insertion) 순서대로 저장되지 않음, 특정한 순서를 기대할 수 없는 자료구조
  • 수정이 가능합(Mutable)
  • 같은 값을 여러번 입력할 수 없다. 여러번 입력할 경우 하나의 값만 저장
  • Fast Lookup이 필요할 때 주로 사용됨

Set의 구조

Set의 구조

• 요소들이 저장될 때의 순서는 Hash를 통해서 정해진다.
  1. 저장할 요소의 Hash 값을 구한다.
  2. 해쉬값에 해당하는 공간(Bucket)에 값을 저장한다.
• 순서가 없다는 것은 Indexing도 없다는 의미
• 같은 값은 Hash 결과가 같기 때문에 같은 값을 여러번 저장할 수 없도록 작동
• Hash 값을 기반으로 저장하기 때문에 Look up이 굉장히 빠르다.
  • Look up  -  특정 값을 포함하고 있는지를 확인 하는 것
  • Set의 총 길이와 상관없이 주어진 값의 Hash 값을 구한 후에 해당 Bucket을 확인하면 완료됨

Hash란?

• 단방향(One way) 암호화로서 한번 암호화를 수행하면 복호화가 안되는 특성이 있다.
• 실제 값의 길이와 상관없이 결과 값인 Hash 값을 일정한 길이로 가진다.
• 임의의 길이를 가지는 임의의 데이터에 대해서 고정된 길이의 데이터로 매핑을 할 때 주로 사용된다.

 

Dictionary

• 파이썬에서는 Dictionary라고 부르며 다른 언어에서는 Hashmap 또는 Hash table이라고 칭함
• Key - Value 형태의 값을 저장하는 자료구조
• 실제 데이터 값과 데이터를 설명하는 대응 관계를 표현할 때 유용
• Dictionary를 사용하면 좋은 상황
  • DB처럼 키와 값을 함께 묶어서 표현할 경우에 유용하게 사용할 수 있다. 실제로 DB에서 읽어낸 값을 Dictionary로 변환해서 사용하는 경우가 잦음
• 특징
  • Set와 마찬가지로 특정 순서대로 데이터를 반환하지 않는다.
  • Key값의 경우, 중복될 수 없다. 중복될 경우에는 나중에 입력된 Key와 Value가 이미 존재하던 Key와 Value를 대체한다.
  • 수정가능(Mutable)

Dictionary의 구조

Dictionary의 구조

• Set와 비슷하게 Key  값의 Hash 값을 구한 후 해당 Bucket에 값을 저장
• Set와 마찬가지로 순서가 없고 중복된 Key를 허용하지 않는다.