[중간정리] 2주차 - 해시 충돌과 체이닝, 병합 정렬, 큐, 캐시 메모리, 프로세스/스레드

해시 충돌과 체이닝

해시 충돌(Hash Collision)은 해시 테이블에서 두 개 이상의 서로 다른 키가 동일한 저장공간(인덱스)에 할당되는 현상이다. 해시 테이블에서는 주어진 키를 해시 함수를 통해 테이블의 인덱스로 변환하는데, 해시 함수의 특성상 입력 값의 범위를 제한된 인덱스 범위로 축소시키므로 서로 다른 키 값이 같은 해시 값을 가질 수 있게 된다. 그리고 이로 인해 충돌이 발생하게 된다.

 

체이닝(Chaining)은 해시 충돌 문제를 해결하기 위한 대표적인 방법 중 하나로, 해시 테이블의 각 인덱스에 연결 리스트(Linked List)를 두어 충돌이 발생한 여러 키-값 쌍을 함께 저장하는 방법이다. 체이닝을 사용하면 충돌이 발생하더라도 데이터의 손실 없이 여러 데이터를 동일한 인덱스에 저장할 수 있으며, 해시 테이블의 크기와 상관없이 비교적 일정한 성능을 유지할 수 있다.

 

다만, 체이닝 방식에도 단점은 존재한다. 연결 리스트를 추가로 사용함에 따라 메모리 사용량이 증가하며, 특정 인덱스의 연결 리스트가 너무 길어지면 데이터를 찾는 데 걸리는 시간이 길어져 성능 저하의 원인이 될 수 있다.

 

 

병합 정렬(Merge Sort) 구현

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = [0] * (len(left) + len(right))
    pl, pr = 0, 0
    for i in range(len(result)):
        if pl == len(left):
            result[i] = right[pr]
            pr += 1
        elif pr == len(right):
            result[i] = left[pl]
            pl += 1
        else:
            if left[pl] <= right[pr]:
                result[i] = left[pl]
                pl += 1
            else:
                result[i] = right[pr]
                pr += 1
    return result

 

 

큐 구현

from typing import Any

class FixedQueue:
    def __init__(self, capacity: int) -> None:
        self.no = 0                     # 현재 데이터 개수
        self.front = 0                  # 맨 앞 원소 커서
        self.rear = 0                   # 맨 끝 원소 커서
        self.capacity = capacity        # 큐의 크기
        self.que = [None] * capacity    # 큐의 본체

    def __len__(self) -> int:
        return self.no

    def is_empty(self) -> bool:
        return self.no <= 0

    def is_full(self) -> bool:
        return self.no >= self.capacity

    # 데이터를 큐에 추가
    def enque(self, x: Any) -> None:
        if self.is_full():
            return
        self.que[self.rear] = x
        self.rear = (self.rear + 1) % self.capacity
        self.no += 1

    # 데이터를 큐에서 꺼냄
    def deque(self) -> None:
        if self.is_empty():
            return
        val = self.que[self.front]
        self.front = (self.front + 1) % self.capacity
        self.no -= 1
        return val

 

 

캐시 메모리와 컴퓨터 시스템 성능이 향상

캐시 메모리는 컴퓨터 시스템의 성능을 향상시키는 핵심 요소 중 하나로, 데이터 접근 시 특정 영역을 반복적으로 사용하는 특성인 '지역성(Locality)' 원리를 활용한다. 지역성은 크게 시간적 지역성(Temporal Locality)과 공간적 지역성(Spatial Locality) 두 가지로 나누어진다.

• 시간적 지역성 : 한 번 접근한 데이터는 가까운 미래에 다시 접근할 가능성이 높다는 원리
• 공간적 지역성 : 특정 메모리 주소에 접근한 이후, 그 주변 주소의 데이터에도 곧 접근할 가능성이 높다는 원리

캐시 메모리는 이러한 지역성 원리를 기반으로 자주 사용되는 데이터나, 앞으로 사용할 가능성이 높은 데이터를 미리 저장해 둔다. 덕분에 CPU는 필요한 데이터를 상대적으로 느린 메모리가 아닌 빠른 속도의 캐시 메모리에서 즉시 읽어올 수 있다. 이 때문에 데이터 접근 시간이 크게 줄어들고, 전체적인 컴퓨터 시스템 성능이 크게 향상된다.

 

 

프로세스(Process)와 스레드(Thread)의 차이점

프로세스는 실행 중인 프로그램 그 자체를 뜻하며, 독립적인 메모리 공간과 시스템 자원을 할당받아 사용한다. 반면 스레드는 프로세스 내에서 실행되는 작업 단위로, 같은 프로세스 내에서 생성된 스레드끼리 메모리 공간과 자원을 공유하며 동작한다.

 

따라서 스레드는 프로세스보다 자원을 효율적으로 사용할 수 있고, 데이터 공유와 협력 작업에 용이하여 멀티태스킹과 병렬 처리에 주로 사용된다. 다만, 스레드는 자원을 공유하기 때문에 동기화 문제가 발생할 수 있고, 프로세스는 독립적이므로 상대적으로 안정적이지만 자원 소모가 큰 편이다.