자료구조와 알고리즘 A+ 기원 6.

1. Access Patterns

1. Sequential Access
   : 첫 번째 요소부터 시작해서 다음 요소로 Access 해나가는 방법
   - 대부분 Linked List에서 제공
   - Linear Time
   
   
2. Direct Access (= Random Access)
   : 원하는 Index를 통해 바로 Access
   - 대부분 Arrays 형태의 자료구조에서 제공
   - Constant Time
   - 하지만 index라는 사전 지식이 꼭 필요함

• index의 사전 지식이 필요 없으면서도,
• Direct Access 방법의 자료구조는 없을까?
  -> Hash Table

2. Hash Table

: 데이터를 효율적으로 삽입/삭제/탐색할 수 있는 알고리즘으로, Hash Map이라고도 불림

• 어떻게 Index에 대한 사전 정보를 없애나?
  : Hash Function을 이용하여 Key로부터 Index를 계산
  (Key로부터 Index를 계산하는데 시간이 걸리기는 하지만, 거의 Constant하다고 봄)

// java.util.*에 hash map이 구현되어 있음

Map<String, Integer> address = new HashMap<>();

1) Operation

• put(K, V)
• remove (K)
• ContainsKey(K)
• get(K)

2) 모든 요소에 접근하기

• Iterator
• Lambda

3. 충돌 Collision

• Closed Addressing
• Open Addressing
  • Linear Probing
  • Quadratic Probing
  • Double Hashing

1) Closed Addressing

: Separate Chaining -> 마치 Linked List처럼 구현되며, 한 index(key)가 겹칠 경우 Value들을 연결하여 표현하는 것 (Bucket)

• Linear Time
• 최악의 경우 한 리스트에 모든 Value들이 모이면서 단순한 Linked List가 될 수도 있음

2) Open Addressing

: hash table을 open addressing 방법을 사용하여 구현할 때를 probing이라고 함

01 Linear Probing

: 충돌이 발생한 경우, 다음 index에 해당 Value를 넣게 됨
-> Primary Clustering 발생 근처 인덱스에만 몰리는 현상이 일어남

02 Quadratic Probing

: 충돌이 발생한 경우, 해당 index의 제곱 index에 해당 value를 넣게 됨
-> Secondary Clustering 발생 제대로 된 공간 활용을 하지 못함

03 Double Hashing

: Hash를 2번 하여 생성된 index에 삽입

$h(i, k) = (h_1(k) + i * h_2(k)) mod |T|$

• 이때 47의 경우
  • 47%7 = 5 -> 이미 40 이라는 값이 있음
  • 5-(47%5) = 3 -> double hashing을 하여 5로부터 index가 3 떨어진 1에 47을 삽입

4. Performance

• Load Factor: (item의 개수) / (실제 hash table의 크기) * 100
  • 최대 75% ~ 80%
  • 너무 크면: probing이 자주 발생
  • item > table size: reshape할 필요 O

• 좋은 Hash Table은?
  • 충돌이 없음!
  • 100%의 load factor를 가지고 있음!