[자료구조] Week 5: 해시 테이블

Day 1: 해시 테이블의 기본 개념

• 강의 내용:
  • 해시 테이블의 정의와 특징
    • 해시 테이블의 개념과 용도
    • 키-값 쌍 저장 구조
  • 해시 함수
    • 해시 함수의 역할과 중요성
    • 좋은 해시 함수의 조건
• 실습:
  • 기본 해시 테이블의 개념 설명 및 예제

# 해시 테이블의 기본 개념 설명
# 해시 테이블은 키-값 쌍으로 데이터를 저장하는 자료구조
# 키를 해시 함수에 입력하여 해시 값을 생성하고, 이 해시 값을 이용하여 값을 저장하거나 검색

# 파이썬 딕셔너리를 사용한 간단한 해시 테이블 예제
hash_table = {}
hash_table["apple"] = 1
hash_table["banana"] = 2
hash_table["cherry"] = 3

print("해시 테이블:", hash_table)
print("키 'banana'의 값:", hash_table["banana"])

 

Day 2: 해시 충돌과 해결 방법

• 강의 내용:
  • 해시 충돌의 개념
    • 해시 충돌이 발생하는 이유
  • 해시 충돌 해결 방법
    • 체이닝 (Chaining)
    • 개방 주소법 (Open Addressing)
• 실습:
  • 체이닝을 사용한 해시 충돌 해결 예제

# 체이닝을 사용한 해시 테이블 구현 예제
class HashTableChaining:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        hash_key = self.hash_function(key)
        key_exists = False
        bucket = self.table[hash_key]
        for i, kv in enumerate(bucket):
            k, v = kv
            if key == k:
                key_exists = True
                break
        if key_exists:
            bucket[i] = (key, value)
        else:
            bucket.append((key, value))

    def search(self, key):
        hash_key = self.hash_function(key)
        bucket = self.table[hash_key]
        for k, v in bucket:
            if key == k:
                return v
        return None

    def display(self):
        for i, bucket in enumerate(self.table):
            print(f"Bucket {i}: {bucket}")

# 체이닝을 사용한 해시 테이블 사용 예제
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
hash_table.insert("date", 4)
hash_table.display()
print("키 'banana'의 값:", hash_table.search("banana"))  # 2

 

Day 3: 개방 주소법을 사용한 해시 테이블

• 강의 내용:
  • 개방 주소법의 개념
    • 선형 탐사 (Linear Probing)
    • 제곱 탐사 (Quadratic Probing)
    • 이중 해싱 (Double Hashing)
  • 개방 주소법을 사용한 해시 테이블 구현
• 실습:
  • 선형 탐사를 사용한 해시 테이블 구현 예제

# 선형 탐사를 사용한 해시 테이블 구현 예제
class HashTableLinearProbing:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        hash_key = self.hash_function(key)
        original_hash_key = hash_key

        while self.table[hash_key] is not None:
            if self.table[hash_key][0] == key:
                break
            hash_key = (hash_key + 1) % self.size
            if hash_key == original_hash_key:
                raise Exception("HashTable is full")

        self.table[hash_key] = (key, value)

    def search(self, key):
        hash_key = self.hash_function(key)
        original_hash_key = hash_key

        while self.table[hash_key] is not None:
            if self.table[hash_key][0] == key:
                return self.table[hash_key][1]
            hash_key = (hash_key + 1) % self.size
            if hash_key == original_hash_key:
                return None

        return None

    def display(self):
        for i, entry in enumerate(self.table):
            if entry is not None:
                print(f"Bucket {i}: {entry}")
            else:
                print(f"Bucket {i}: Empty")

# 선형 탐사를 사용한 해시 테이블 사용 예제
hash_table = HashTableLinearProbing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
hash_table.insert("date", 4)
hash_table.display()
print("키 'banana'의 값:", hash_table.search("banana"))  # 2

 

Day 4: 해시 테이블의 응용

• 강의 내용:
  • 해시 테이블의 응용 사례
    • 캐싱
    • 데이터베이스 인덱싱
    • 집합 연산
  • 해시 테이블을 사용한 알고리즘
    • 중복 요소 찾기
    • 주어진 합계를 만드는 쌍 찾기
• 실습:
  • 해시 테이블을 사용한 중복 요소 찾기 예제

# 해시 테이블을 사용한 중복 요소 찾기
def find_duplicates(arr):
    hash_table = HashTableChaining(len(arr))
    duplicates = []
    for item in arr:
        if hash_table.search(item) is not None:
            duplicates.append(item)
        else:
            hash_table.insert(item, True)
    return duplicates

# 중복 요소 찾기 예제
arr = [1, 2, 3, 4, 5, 2, 3, 6]
print("중복 요소:", find_duplicates(arr))  # 중복 요소: [2, 3]

 

Day 5: 해시 테이블 성능 분석

• 강의 내용:
  • 해시 테이블의 시간 복잡도
    • 삽입, 삭제, 검색의 평균 시간 복잡도
    • 최악의 경우 시간 복잡도
  • 해시 함수의 성능 분석
    • 충돌율 감소를 위한 해시 함수의 선택
• 실습:
  • 다양한 해시 함수 성능 비교 예제

# 해시 함수 성능 비교
def simple_hash(key, size):
    return hash(key) % size

def better_hash(key, size):
    return (hash(key) * 37) % size

size = 10
keys = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape"]

# 성능 비교
simple_hash_table = HashTableChaining(size)
better_hash_table = HashTableChaining(size)

for key in keys:
    simple_hash_table.insert(key, simple_hash(key, size))
    better_hash_table.insert(key, better_hash(key, size))

print("Simple hash table:")
simple_hash_table.display()

print("\nBetter hash table:")
better_hash_table.display()

 

Day 6: 파이썬의 해시 테이블 (딕셔너리)

• 강의 내용:
  • 파이썬 딕셔너리의 특징과 구현
    • 파이썬 딕셔너리의 내부 구조
    • 딕셔너리의 시간 복잡도
  • 딕셔너리를 사용한 해시 테이블 예제
• 실습:
  • 파이썬 딕셔너리를 사용한 다양한 예제 작성

# 파이썬 딕셔너리를 사용한 해시 테이블 예제
phone_book = {
    "Alice": "123-456-7890",
    "Bob": "987-654-3210",
    "Charlie": "555-555-5555"
}

print("전화번호부:", phone_book)
print("Bob의 전화번호:", phone_book["Bob"])

# 딕셔너리의 다양한 메서드 사용 예제
phone_book["David"] = "111-111-1111"
print("전화번호부:", phone_book)

del phone_book["Alice"]
print("Alice 삭제 후 전화번호부:", phone_book)

print("Charlie의 전화번호:", phone_book.get("Charlie", "없음"))

 

Day 7: 종합 연습 및 프로젝트

• 강의 내용:
  • 해시 테이블을 사용한 종합 연습 문제 풀이
    • 다양한 해시 테이블 관련 문제
    • Q&A 세션
  • 미니 프로젝트
    • 해시 테이블을 활용한 간단한 프로그램 구현
    • 예: 간단한 캐시 시스템
• 실습:
  • 종합 연습 문제 풀기
  • 미니 프로젝트 작성 및 발표

# 연습 문제 1: 해시 테이블을 사용한 주어진 합계를 만드는 쌍 찾기
def find_pair_with_sum(arr, target_sum):
    hash_table = {}
    for num in arr:
        if target_sum - num in hash_table:
            return (target_sum - num, num)
        hash_table[num] = True
    return None

arr = [1, 2, 3, 4, 5]
target_sum = 7
print("주어진 합계를 만드는 쌍:", find_pair_with_sum(arr, target_sum))  # (3, 4)

# 미니 프로젝트 예제: 간단한 캐시 시스템
class SimpleCache:
    def __init__(self, capacity):
        self.cache = {}
        self.capacity = capacity
        self.keys = []

    def put(self, key, value):
        if key in self.cache:
            self.keys.remove(key)
        elif len(self.cache) >= self.capacity:
            oldest_key = self.keys.pop(0)
            del self.cache[oldest_key]
        self.cache[key] = value
        self.keys.append(key)

    def get(self, key):
        if key in self.cache:
            self.keys.remove(key)
            self.keys.append(key)
            return self.cache[key]
        return None

    def display(self):
        print("Cache:", self.cache)
        print("Keys:", self.keys)

# 캐시 시스템 사용 예제
cache = SimpleCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
cache.display()
cache.put("d", 4)
cache.display()
print("Get 'b':", cache.get("b"))
cache.display()

 

이 강의는 파이썬의 자료구조 중 해시 테이블을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!