Data Structure Set, Dictionary, Hash

박상영·2020년 6월 15일
0
post-thumbnail

Set

Set은 array 나 list 처럼 순열 자료구조(collection) 입니다.
하지만 set은 순서라는 개념이 존재하지 않는다.

set의 특징

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

set의 구조

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

set은 언제 사용할까?

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

보이는 것과 같이 len으로 set을 한 list 와 하지않은 list의 크기를 비교했을때, my_list 는 set()로 중복되는 값이 하나로 되어 기존의 list보다 크기가 작아지게 된다.

set은 list와 tuple과 달리 삽입, 포함 연산 외에도 수학 집합 연산을 지원한다.

  • union
    union() 함수를 사용하여 두 set을 병합하거나 "|" operator 를사용한다.
    두개의 해시 테이블 값에 access하고 병합 조작으로 순회하여 요소를 결합하고 동시에 중복이 제거된다. 시간 복잡도는 O(len(s1) + len(s2)) 이며 s1 과 s2는 합집합이 필요한 set 입니다.

  • intersection
    intersection() 또는 "&" operator 를 사용할수있다.
    공통된 요소가 선택이된다. hash목록에 대한 반복과 유사하며 두 테이블에서 동일한 값을 결합한다. 시간 복잡도는 O(min(len(s1), len(s2))) 이며 s1과 s2는 합집합이다.

  • Difference
    set() 간의 차이점을 찾기위해 사용된다. 연결된 목록에서 차이점을 찾는 것과 비슷하다. difference() 또는 "-" operator를 사용한다. s1 - s2를 찾는 시간 복잡도는 O(len(s1))이다.

Dictionary

  • my_dict1
    데이터가 주어지거나 딕셔너리의 내용이 고정되어 있는 경우 사용되는방법
  • my_dict2
    my_dict2라는 빈 딕셔너리를 생성한다음 데이터 베이스를 조회해서 필요한 정보를 동적으로 채워야 할 때 편리하다
  • my_dict3
    숫자로 딕셔너리의 키로 사용할 수 있지만 문자열만 키로 사용되는 경우 사용할 수 있는 방법이다.
  • my_dict4
    튜플로 받아온 정보로 키와 값을 만들어야 할 경우에 사용할 수 있다.

Hash

해시란 단방향 (one way) 암호화 입니다. 입력 데이터를 변환하여 원본 데이터로 복호화할 수 없도록 하는 과정이다. SHA(보안 해시 알고리즘)을 예로 들수 있다. SHA 함수를 이용하여 문자열 데이터를 입력받아서 해시값을 구할 수있다.

이처럼 hash값은 일정한 길이를 가지고, 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 mapping할때 사용된다.
해시함수는 같은 문자열에 대해서는 같은 인덱스를 구할 수 있어야 해시함수로 구한 버킷의 인덱스를 저장 후에도 구할 수 있다.

profile
backend

0개의 댓글