lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

pythonIntroStep4Chapter3Title

pythonIntroStep4Chapter1Title

pythonIntroStep4Chapter2Title

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(self.size)]

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

    def set(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 get(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 remove(self, key):
        hash_key = self._hash_function(key)
        bucket = self.table[hash_key]
        for i, kv in enumerate(bucket):
            k, v = kv
            if key == k:
                del bucket[i]

# 해시 테이블 사용 예시
hash_table = HashTable()

hash_table.set('apple', '사과')
hash_table.set('banana', '바나나')
hash_table.set('orange', '오렌지')

print("apple 키로 검색:", hash_table.get('apple'))  # apple 키로 검색: 사과
print("banana 키로 검색:", hash_table.get('banana'))  # banana 키로 검색: 바나나

hash_table.remove('banana')
print("banana 키 삭제 후 검색:", hash_table.get('banana'))  # banana 키 삭제 후 검색: None

# 해시 테이블(Hash Table)

`해시 테이블(Hash Table)`은 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 자료구조로, 빠른 데이터 검색, 삽입, 삭제를 할 수 있습니다.

해시 테이블은 사물함과 비슷한 개념으로, 사물함의 번호는 '키(key)'에, 사물함 안의 물건은 '값(value)'에 해당합니다.

해시 테이블에서 '해시 함수'는 주어진 키를 받아 그 키에 해당하는 사물함의 '주소'를 계산합니다. 이 주소는 키가 저장되는 위치를 가리키며, 덕분에 키를 사용하여 매우 빠르게 값을 찾을 수 있습니다.

파이썬에서는 해시 테이블 구조가 '딕셔너리(Dictionary)' 형태로 구현되어 있습니다.

<br />

## 해시 테이블의 작동 원리

- `해싱(Hashing)`: 키를 해시 함수를 통해 해시 코드(Hash Code)로 변환하는 과정을 뜻합니다. 이 해시 코드는 저장될 데이터의 주소를 결정합니다.

- `해시 충돌(Hash Collision)`: 두 개의 다른 키가 같은 사물함 번호(주소)를 가리키는 경우가 발생할 수 있습니다. 충돌은 서로 다른 키가 동일한 해시 코드로 변환되는 경우를 뜻합니다.

- `해시 함수(Hash Function)`: 해시 테이블은 해시 함수를 사용해 키(Key)를 해시 코드로 변환합니다. 이 해시 코드는 저장될 값의 인덱스로 사용됩니다. 좋은 해시 함수는 충돌을 최소화하고, 데이터를 해시 테이블에 고르게 분포시킵니다.

<br />

## 해시 테이블의 구현

```python title="해시 테이블 구현 예시"
hash_table = list([0 for i in range(10)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value

def read_data(data):

    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]

save_data('Key1', 'Value1')

save_data('Key2', 'Value2')

print("Key1:", read_data('Key1')) # Value1

print("Key2:", read_data('Key2')) # Value2
```

<br />

## 해시 테이블의 장점과 단점

### 장점:

해시 테이블의 주요 장점은 다음과 같이 요약할 수 있습니다:

1. `빠른 데이터 접근 및 검색`: 해시 테이블은 평균적인 상황에서 데이터를 추가, 검색, 삭제하는 데 상수 시간(O(1))이 소요됩니다. 이는 키를 사용하여 직접 해당 값에 접근할 수 있기 때문입니다.

2. `효율적인 메모리 사용*` 해시 테이블은 데이터를 효율적으로 저장하며, 필요에 따라 동적으로 크기를 조절할 수 있습니다.

3. `키-값 쌍 데이터 구조`: 키-값 쌍 구조로 인해 데이터를 구조화하고 관리하기 쉽습니다. 이를 통해 데이터를 직관적으로 삽입, 검색, 삭제할 수 있습니다.

### 단점:

1. `충돌(Collision) 발생`: 서로 다른 키가 동일한 해시 값을 가질 때 발생하는 충돌은 해시 테이블의 성능을 저하시킬 수 있습니다. 충돌이 빈번하게 발생하면 해시 테이블의 평균적인 접근, 검색, 삭제 시간이 상수 시간(O(1))에서 최악의 경우 선형 시간(O(n))으로 증가할 수 있습니다.

2. `순서 유지 불가능`: 해시 테이블은 데이터의 순서를 유지하지 않습니다. 즉, 키-값 쌍이 추가된 순서대로 데이터를 검색하거나 반복할 수 없습니다. 이 때문에 데이터의 순서가 중요한 경우에는 해시 테이블이 적합하지 않을 수 있습니다.