해시 테이블 [ 크래프톤 정글 13일차 ]

jinsung·2025년 5월 25일

크래프톤 정글

크래프톤 정글 9기

목록 보기

11/59

해시테이블은 해시 브라운 감자가 올려져 있는 테이블을 일컫는 말이다.

뻥이다.

1. 왜 해시테이블이 필요했을까?

우선 해시테이블이 뭔지 어떻게 사용하는지 설명하기에 앞서서

해시테이블 << 요놈 왜 등장함???

이거부터 제대로 짚고 가자!

하나부터 열까지 핵심만 딱딱 알려줄게!( 지피티체 ㅋㅋ )

1-1. 데이터의 저장과 조회

프로그래밍에서 데이터를 저장하고 조회하는 기본적인 방법은 배열이나 리스트였어요.

근데 배열이나 리스트에는 다음과 같은 문제점이 존재해요.

문제 1. 검색속도가 느림!

리스트에서 특정 값을 찾기 위해서는 일반적으로 선형탐색을 해야해요.

예를 들어

const array = [1,2,3,4,5,6,7,8,10]

for (let i = 0; i<array.length; i++){
	if (array[i] === 10) return true
}

// 10 하나 찾으려고 배열하나하나를 전부 탐색해야함...

10을 찾으려면 하나하나 전부 확인해야함...!!

엥 검색속도 O(N)인거 실화냐

if (데이터가 1억개라면?): oh my god!!

문제 2. 데이터의 삽입/삭제 비용

배열이나 리스트에서 중간에 데이터를 삽입하려면 중간에 넣기 위해서 요소들을 하나씩 이동시켜야됨...

이 과정에서 시간과 메모리 비용이 추가로 발생!!

그래서 해시테이블이 등장했다!

검색,삽입,삭제 연산을 평균적으로 O(1) 시간에 처리할 수 있음

키-값 구조를 사용하여 직관적이고 빠른 데이터 접근 가능

2. 해시테이블의 작동원리

2-1. 해시 함수 (Hash Fucntion)

주어진 키를 인덱스로 변환하는 함수야!
예를 들어, 숫자 1을 넣으면 특정 인덱스 값으로 변환하고 문자열 "apple" 도 특정 정수 값으로 변환해줘
이 해시 값은 배부 배열의 인덱스로 사용되는거야

def simple_hash(key):
	return sum(ord(char) for char in key) % TABLE_SIZE

# 문자를 정수값으로 변환한뒤 해시테이블 크기만큼의 나머지로 계산하기!

이렇게 키값을 정수로 바꿔준뒤 그걸 인덱스로 사용해버리는거야.

그럼 나중에 이 해쉬함수로 연산만하면 키값에 해당하는 인덱스가 나오는거지

그래서 검색 연산이 O(1) 이되는거야!

!!! 아니 근데 님아, 문자열 "apple" 이랑 "banana" 넣었는데
둘다 해쉬 함수 인덱스 값으로 "우연히" "같은 인덱스값"이 나오면 어떻게함?
그럼 인덱스 겹치는거잖음 값 다른건데;;

니는 내(해쉬테이블만든사람)가 빙다리 핫바지로 보이냐, 다 준비해놨다 이거야

2-1. 해쉬충돌처리

만약에 다른 값인데 저장할 인덱스가 같은 값으로 나올수도 있는거잖아?

이걸 해쉬충돌 이라고 하는데, 다 똑똑이들이 해결방법을 준비해놓긴 했어. 완벽하진 않지만.

- 방법 1. 체이닝(Chaining): 같은 인덱스에 여러 개의 값을 리스트로 저장

연결리스트알지? 그것처럼 만약에 같은 인덱스에 동시에 들어오면 연결리스트로 여러 개의 값을 인덱스에 넣어두는거야!

그래서 혹시라도 인덱스에 이미 값이 있다면 여러개로 넣어둬서 그 안의 배열에서 찾으면 돼!

- 방법 2. 오픈 어드레싱

인덱스 겹쳤어??

그럼 안겹치는 거 나올때까지 i++ 하는거야그냥 ㅋㅋㅋㅋㅋ

이동하면서 빈자리가 나올때까지 찾아!

3. 그래서 해시테이블 어디서 써?

python 에서의 해시 테이블 활용

파이썬은 해시 테이블을 굉장히 적극적으로 사용하고 있는 언어야.

특히 딕셔너리(dictionary) 와 집합 (set) 이 대표적인 예야

my_dict = {
    "name": "Alice",
    "age": 25,
    "job": "Engineer"
}

# 검색
print(my_dict["name"])  # O(1)

# 삽입
my_dict["city"] = "Seoul"  # O(1)

# 삭제
del my_dict["job"]  # O(1)

딕셔너리는 파이썬에서 많이 사용해봤지?

구조도 키-값 쌍으로 이루어져있고

검색 ,삽입,삭제 모두 O(1) 야 얘는 그냥 해시테이블 그 자체임 ㅋㅋㅋ

my_set = set()
my_set.add("apple")
my_set.add("banana")
my_set.add("apple")  # 중복 무시

print("banana" in my_set)  # True (검색 O(1))

list = [1,2,3,4,2,3,4,1,2,3,]
set_list = set(list)

print(set_list)

# {1,2,3,4}