CodeGym /행동 /Python SELF KO /해시 테이블 작동 원리

해시 테이블 작동 원리

Python SELF KO

레벨 54 , 레슨 1

사용 가능

6.1 해시 테이블 정의 및 구조

해시 테이블은 데이터 구조로서, 배열이나 리스트에서 인덱스를 계산하기 위해 해시 함수를 사용하여 요소를 빠르게 찾고, 삽입하고, 삭제할 수 있도록 해줍니다. 해시 테이블은 일반적으로 사전 또는 연관 배열을 구현하는 데 사용됩니다.

해시 테이블의 중요한 측면

배열 – 해시 테이블의 기본 구성 요소로, 요소나 요소 리스트에 대한 포인터를 저장합니다.

해시 함수: 사전 키를 배열 인덱스로 변환하는 함수입니다.

충돌: 두 개의 다른 키가 동일한 해시 값을 가지는 상황. 충돌을 해결하기 위해 체이닝(chaining) 또는 오픈 어드레싱(open addressing)과 같은 다양한 방법이 사용됩니다.

사전 예시:


{
   "apple": 101,
   "banana": 102,
   "cherry": 103
}

해시 테이블 구조 예시:

인덱스	값
0	None
1	[('apple', 101)]
2	None
3	[('banana', 102)]
4	None
5	None
6	None
7	[('cherry', 103)]
8	None
9	None

6.2 해시 테이블의 기본 연산

해시 테이블의 기본 연산: 삽입, 검색, 삭제

1. 삽입 (Insertion): 해시 테이블에 새로운 요소(키-값 쌍)를 추가하는 과정입니다.

삽입 단계:

해시 함수를 사용하여 키의 해시 값을 계산합니다.
해시 값을 기반으로 배열에서 인덱스를 찾습니다.
해당 인덱스에 이미 요소가 있다면(충돌), 리스트에 요소를 추가하거나(체이닝의 경우) 다음 사용 가능한 인덱스를 찾습니다(오픈 어드레싱의 경우).

체이닝을 사용한 해시 테이블에 삽입 예시:


class HashTable:
    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):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

# 사용 예시:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. 검색 (Search): 해시 테이블에서 주어진 키에 대한 값을 찾는 과정입니다.

검색 단계:

해시 함수를 사용하여 키의 해시 값을 계산합니다.
해시 값을 기반으로 배열에서 인덱스를 찾습니다.
리스트에서 키의 존재 유무를 확인하거나(체이닝의 경우) 인덱스를 확인합니다(오픈 어드레싱의 경우).

체이닝을 사용한 해시 테이블에서 검색 예시:


class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

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

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

# 사용 예시:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # 출력: 2
print(hash_table.search("grape"))   # 출력: None

3. 삭제 (Deletion): 해시 테이블에서 요소(키-값 쌍)를 삭제하는 과정입니다.

삭제 단계:

해시 함수를 사용하여 키의 해시 값을 계산합니다.
해시 값을 기반으로 배열에서 인덱스를 찾습니다.
리스트에서 요소를 삭제하거나(체이닝의 경우) 인덱스의 값을 None으로 설정합니다(오픈 어드레싱의 경우).

체이닝을 사용한 해시 테이블에서 삭제 예시:


class HashTable:
    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):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

    def delete(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return

# 사용 예시:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # 출력: None

6.3 해시 테이블의 시간 복잡도

해시 테이블에서의 연산의 시간 복잡도

삽입 (Insertion):

평균 경우: O(1)
최악의 경우: O(n) (충돌이 많거나 모든 요소가 같은 위치에 할당된 경우)

검색 (Search):

평균 경우: O(1)
최악의 경우: O(n) (충돌이 많거나 모든 요소가 같은 위치에 할당된 경우)

삭제 (Deletion):

평균 경우: O(1)
최악의 경우: O(n) (충돌이 많거나 모든 요소가 같은 위치에 할당된 경우)

설명:

평균 경우: 평균적으로 해시 함수가 요소를 테이블에 고르게 분배하고, 각 요소가 고유한 셀에 위치하여, 접근 시간이 O(1)이 됩니다.

최악의 경우: 모든 요소가 한 셀에 할당되거나 충돌이 많을 때. 그래서 해시 테이블이 연결 리스트로 변하고, 연산의 시간 복잡도가 O(n)이 됩니다.

6.4 해시 테이블의 사용 예시

1. 사전(연관 배열) 구현

해시 테이블은 키-값 쌍을 저장하고 키에 대한 빠른 접근을 제공하는 사전 구현에 자주 사용됩니다.

예시:


# 사전 생성
dictionary = {}

# 요소 삽입
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# 요소 검색
print(dictionary["banana"])  # 출력: 2

# 요소 삭제
del dictionary["cherry"]

# 키 존재 여부 확인
if "apple" in dictionary:
    print("키 'apple'은 사전에 존재함")  # 출력: 키 'apple'은 사전에 존재함

이제 너는 Python의 사전과 그것이 어떻게 동작하는지 조금 더 알게 되었어.

2. 계산 결과 캐싱

해시 테이블은 비용이 많이 드는 계산의 결과를 캐싱하여 후속 요청을 더 빠르게 만드는 데 사용됩니다.

예시:


# 결과를 저장할 캐시
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # 비용이 많이 드는 계산의 예
    cache[x] = result
    return result

# 캐시 사용
print(expensive_computation(10))  # 출력: 100 (계산 및 캐싱)
print(expensive_computation(10))  # 출력: 100 (캐시에서)

3. 텍스트에서 단어 빈도수 세기

해시 테이블은 텍스트에서 각 단어의 출현 횟수를 세는 데 사용됩니다.

예시:


from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# 결과 출력
for word, count in word_count.items():
    print(f"단어 '{word}'는 {count}번 발견됨")

4. 리스트에서 중복 찾기

해시 테이블은 리스트에서 중복을 효율적으로 찾는 데 사용됩니다.


def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 사용 예시
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # 출력: [2, 4]

이전 이전 레슨

다음 다음 레슨

코멘트

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION