Hash Table

Hash Function

• 해시 함수는 키(key)를 입력받아 해당 키의 저장 위치(버킷 또는 인덱스)를 결정하는 계산을 하는 함수

• 좋은 해시 함수 ⇒ 데이터를 골고루 분배시켜주는 함수

장점

• 빠른 데이터 읽기, 삽입, 삭제

단점

• 메모리를 많이 차지한다.

• 좋은 해시 함수의 구현이 필수적이다.

Hash Collision

• 해시 충돌은 해시 함수가 서로 다른 두 개 이상의 입력 값에 대해 동일한 해시 값을 출력하는 상황을 의미

• Hash 충돌이 발생한 곳의 Value들을 연결리스트로 구성하여 데이터들을 연결한다.

  • 기존값과 새로운 값을 동시에 저장할 수 있다.

  • 찾고자 하는 Value가 나올 때까지 연결리스트를 탐색한다.
    → O(n)의 성능을 갖는다.

해결 방법

1. 체이닝 (Chaining)

   • 각 버킷에 연결 리스트를 사용하여 충돌된 항목들을 저장한다.

   • 장점: 구현이 간단하고, 해시 테이블의 확장이 필요 없다.

   • 단점: 최악의 경우 검색 시간이 O(n)이 될 수 있다.

2. 개방 주소법 (Open Addressing)

   • 충돌 발생 시 다른 빈 버킷을 찾아 데이터를 저장한다.

   • 유형:

     • 선형 탐사 (Linear Probing)

     • 제곱 탐사 (Quadratic Probing)

     • 이중 해싱 (Double Hashing)

   • 장점: 추가적인 메모리 사용이 없다.

   • 단점: 클러스터링 현상이 발생할 수 있다.

3. 재해싱 (Rehashing)

   • 해시 테이블의 크기를 동적으로 조정하여 충돌 가능성을 줄인다.

Tip.

• Java의 HashMap의 경우에는 기본적으로 체이닝 방식을 사용한다.
  But. 성능 최적화를 위해 다음과 같이 구현된다.
  - 하나의 버킷에 8개 이상의 항목이 저장되면 연결 리스트를 트리 구조로 변환한다.
  - 버킷의 항목 수가 6개 이하로 줄어들면 다시 연결 리스트로 변환한다.
  참조 : https://d2.naver.com/helloworld/831311

시간 복잡도

• 읽기, 삽입, 수정, 삭제 : Key만 알고 있으면 Value에 O(1)로 읽기가 가능

HashTable ADT

• set() - 데이터 삽입

• get() - 데이터 읽기

• remove() - 데이터 삭제

Set

• 데이터의 중복을 허용하지 않는 자료구조

• HashTable을 사용하여 구현할 수 있다.
  → HashTable을 사용하기 때문에 HashSet이라고도 한다.
  → HashTable의 value 값은 사용하지 않고 key만 사용하여 구현한다.
  (key가 key와 value의 역할을 수행한다.)

Set ADT

• add(data) - 데이터 삽입

• isContain(data) - 데이터 체크

• remove(data) - 데이터 제거

• clear() - 셋 비우기

• isEmpty() - 셋이 비었는지 확인

• printAll() - 모든 데이터 출력

CPU Scheduling

• 스케줄러가 고려해야 할 사항

  • 어떤 프로세스에게 CPU를 할당해야 하는가?

  • CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 점유해야 하는가?
    → 컴퓨터의 성능에 굉장히 큰 영향을 미친다.

CPU Burst

• CPU를 할당받아 실행하는 작업

I/O Burst

• I/O 작업

목표

• 목표들을 전부 만족할 수는 없다.
  → 목표들에 따라 Trade-Off가 있기 때문
  ex) 처리량 ↑ ⇒ CPU 오래 할당, 응답시간 ↓ ⇒ 여러 프로세스에 CPU를 골고루 할당
  ⇒ 처리량과 응답시간 사이에 Trade-Off가 발생한다.

리소스 사용률

• CPU 사용률 높이기

• I/O 디바이스의 사용률 높이기

오버헤드의 최소화

• Context Switching시에 발생하는 오버헤드를 최소화하는 것

공평성

• 모든 프로세스에게 우선순위에 따라 공평하게 CPU가 할당되어야 한다.

처리량

• 같은 시간내에 더 많은 처리를 할 수 있게 하는 것

대기시간

• 작업을 요청하고 실제 작업이 실행되기 전까지 대기하는 시간이 짧은 것

응답시간

• 사용자의 요청이 얼마나 빨리 요청하는지

다중 Queue

• 프로세스가 대기하고 있는 준비상태와 대기상태는 Queue라는 자료구조로 관리된다.

• OS는 해당 프로세스의 우선순위를 보고, 그에 맞는 준비 큐에 PCB를 넣는다.

• CPU 스케줄러는 준비상태의 다중 큐에 들어있는 프로세스들 중에 프로세스를 선택해서 실행상태로 전환시킨다.

• 프로세스가 실행상태에서 I/O 요청을 받아 대기상태로 전환되는 경우 I/O 작업 종류에 따라 분류된 큐에 PCB가 들어간다.

• I/O 작업이 완료되어 인터럽트가 발생되면 분류된 큐에서 프로세스를 꺼낸다.

FIFO(First-In First-Out)

• 먼저 들어온 작업이 먼저 나간다.

• 스케쥴링 큐에 들어온 순서대로 CPU를 할당받는 방식

단점

• 먼저 들어온 프로세스가 완전히 종료되어야만 다음 프로세스가 실행될 수 있다.
  → I/O 작업이 발생하면 CPU는 I/O 작업이 끝날 때까지 쉬기 때문에 CPU 사용률이 떨어진다.
  → 작업이 빠르게 종료될 수 있는 간단한 프로세스가 작업이 무거운 프로세스 뒤에 들어오면 무거운 프로세스가 완료될 때까지 기다려야 한다.

• 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기 때문에 현대 OS에서 사용되지 않고, 주로 일괄 처리 시스템에서 사용된다.

스케줄링의 성능

평균 대기 시간

• 스케줄링 성능 평가의 척도

• 프로세스 여러개가 실행될 때 해당 프로세스들이 모두 실행되기까지 대기시간의 평균값
  ex)