2022.11.29 경일 메타버스 수업내용. 자료구조 특강.

ADT (Abstract Data Type) : 추상 데이터 타입

• 추상 => 막연하다
  <-> 구체화 (concrete)

• 추상 데이터 타입 : 어떻게 동작해야 한다라고 설명한 것

  • List : 데이터를 순차적으로 저장한 구조

  • Stack : LIPO

  • Queue : FIFO

  • Tree : 계층

  • Graph : 관계

  • Set : 중복 없이 데이터 저장, 유일한 데이터만 저장
    => { 1, 1, 2, 3 } (X)

  • Map : Key-Value 쌍으로 데이터 저장
    => 연관 컨테이너 (Associative Container), 사전(Dictionary)이라고도 함.

    • Array : Key(인덱스), Value(데이터)

• ADT를 가지고 구현체(implementation)를 만든 것이 자료구조 (Data Structure)

Set / Map

• 구현할 수 있는 자료구조

  • Array

    • ex) bool isExistAlphabet[26]; -> set의 한 종류

  • Binary Search Tree

  • HashTable

HashTable

• Array 사용

  • 단점 : Key 타입이 항상 int로 고정된다.

• HashTable : Key를 구할 때, Hash를 사용하는 배열

• Hash

  • 어떤 크기의 입력이던지 간에 고정된 크기의 출력값으로 변환하는 것.

  • Hash의 특징

    • 균일성 : 충돌이 적은 것 => 출력 값이 균일하게 나타난다.

      • 충돌 : 서로 다른 값이 같은 해시 값을 생성한 것

    • 효율성 : 계산이 빨라야 하는 것.

    • 결정적 : 같은 입력이면 똑같은 출력이 만들어져야 하는 것. 무작위가 아니다.

    • ex)

      int MyHash(byte[] someData)
      {
          return 4;
      }
      			```
      
      => Hash가 아니다!

  • 사용 예시

    • 암호화 : 비밀번호 등

    • 커밋 : ID가 해시값

    • 공인인증서 : PKI (Public Key Infrastructure; 공개 키 기반 구조)

    • 디지털 서명 등등

• 주의 : 충돌이 발생함.

  • 내부구조 :

    64비트의 unsigned int (0 ~ 2^63 - 1)

    hashValue % tableSize => tableSize < 2^63 - 1 이면? 충돌이 발생

  • 충돌 회피법

    • 조사법 (Probing) : 해시테이블 내 빈 공간을 찾아서 데이터 저장

      • 종류

        • 선형 (Linear) : 순차적으로 찾음.

        • 2차 (Quadrantic) : 다항식 사용해서 찾음 (hash(k) + i * i 등)

        • 이중 해싱 (Double Hashing) : 해싱을 거듭함 (hashB(hashA(k)))

      • 장점 : 추가적인 공간 할당을 하지 않는다.

      • 단점 : 충돌이 나면 시간이 오래 걸린다.

    • 체이닝 (Chaining) : 연결 리스트로 저장한다.

      • 장점 : 충돌이 나도 시간이 오래 걸리지 않는다.

      • 단점 : 빈 공간이 많이 남아도 추가적으로 공간을 할당해야 한다.

      • 구현이 간단하기에, 보통 체이닝으로 구현되어 있다.

• MSVC의 unordered_map을 기준으로, HashTable의 구현은

  • 선형 리스트와 연결 리스트로 구현되어 있다.

    • [][][][][][][][] 배열 => std::list::iterator
      []-[]-[]-[]-[]-[]

  • 선형 리스트에 위치값을 저장한다.

  • 연결 리스트에 실제 데이터(해시값)를 저장한다.

• 다만, 성능을 생각했을 때 해시테이블을 남용하는 것은 생각해볼 필요가 있다.

  • 컴퓨터는 순차적으로 데이터를 처리할 때 제일 빠르기 때문 -> 캐시 사용

  • 캐시를 최대한 활용하기 어렵다.

• 장점도 물론 있다.

  • 검색에 최적화되어있다 -> O(1)

  • 키를 유연하게 가져갈 수 있다.

• 단점은 다음과 같다.

  • 탐색이 어렵다 -> 최악의 경우 O(n)

  • 검색이 일방향이다. Key => Value만 가능하다.

  • 캐시를 활용하기 어렵다.