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

• 추상? => 막연하다
• 구체화(concrete)
• 추상 데이터 타입 : 어떻게 동작해야 한다라고 설명한 것.
  • List : 데이터를 순차적으로 저장한 구조
  • Stack : LIFO
  • Queue : FIFO
  • Tree : 계층
  • Graph : 관계
  • Set : 중복 없이 데이터 저장
  • Map : Key-Value 쌍으로 데이터 저장 => 연관 컨테이너 (Associative Container), 사전(Dictionaty)이라고도 함.
    • Array : Key(인덱스), Value(데이터)
• ADT를 가지고 구현체(implementation)를 만든 것이 자료구조 (data structure)

Set / Map

• Array
• Binary Search Tree
• HashTable

HashTable (암호화에 용이)

• Array 사용 (Array의 단점 : 인덱스는 항상 int 이다)

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

• Hash

  • 어떤 크키의 입력이던지 간에 고정된 크기의 출력값으로 변환하는것
  • 균일성 : 충돌이 적은 것 => 출력 값이 균일하게 나타난다.
  • 효율성 : 계산이 빨라야 하는 것
  • 결정적 : 같은 입력이면 똑같은 출력이 만들어져야 된다는 것 (무작위 X)

• 충돌이 발생함
  - 조사법(Probing) : 해시테이블 내 빈 공간을 찾아서 데이터 저장 / 새로운 공간을 할당하진 않지만 시간이 오래걸릴 수 있다.
  - 선형(Linear) : 순차적으로 찾음
  - 2차(Quadrantic) : 다항식 사용해서 찾음(hash(k) + i * i)
  - 이중 해싱(double hashing) : hashB(hashA(k))
  - 체이닝(Chaining) : 연결 리스트로 저장한다. / 속도가 빠르지만 새로운 공간을 할당하게 된다.

  체이닝
  컨테이너에 헤쉬를 연결리스트에 값을 넣는다.
  "foo" / A => 2
  "Boo" / B => 2
  [][][&list[8]][][][][][][][][]
  []-[]-[]-[]-[]-[]-[]-[]-[A]-[B]-[]

컴퓨터는 캐싱을 활용해야 속도가 빨라진다

장점
검색 O(1) 키를 인덱스로 가져갈 수 있다.

단점
최악의 경우 탐색이 느릴 수 있다.
정렬되어 있지 않다
탐색이 일방향이다
캐시친화적이지 않다