TIL(25) 21-10-21 : 자료구조 (스택, 큐, 해쉬)

Facts

✅ 스택 3문제

✅ 큐 1문제

✅ 해쉬 3문제

 

 

Findings

1️⃣  스택

• 스택은 넣은 순서를 쌓아두고 있기 때문에 순서가 필요한 경우에 사용한다.
• 스택은 파이썬의 list 를 이용해서 스택으로 사용한다.

stack = []               # 빈 스택 초기화
stack.append(4)   # 스택 push(4)
stack.append(3)   # 스택 push(3)
top = stack.pop()  # 스택 pop
print(top)                # 3!

 

2️⃣  큐

• 큐는 순서대로 처리되어야 하는 경우에 사용한다.
  Ex) 주문이 들어왔을 때 먼저 들어온 순서대로 처리해야 할 때, 혹은 먼저 해야 하는 일들을 저장하고 싶을 때 큐를 사용한다.

 

3️⃣  해쉬 테이블

✔️  What?

F(key) → HashCode →  Index  → Value
(해시함수를 사용하여 키를 해시코드로 매핑하고, 이 해시코드 값으로 인덱스에 접근하여
해당 데이터 값을 접근하는 자료구조다.)

• 해쉬테이블은 "키" 와 "데이터"를 저장함으로써 
• 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용한다.
• 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
• python에서는 dictionary = hash table 같다.

dict = {"fast" : "빠른", "slow": "느린"}

put(key, value) : key 에 value 저장하기
get(key) : key 에 해당하는 value 가져오기

 

✔️  탐색

✔ 평균의 시간복잡도와 최악의 시간복잡도
평균의 시간 복잡도 : O(1)
→ 각각의 Key 값은 해쉬함수에 의해 고유한 Index를 가지게 되어 바로 접근할 수 있음으로,
평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다.
최악의 시간 복잡도: O(N)
→ 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트까지 검색을 해야 하므로,
O(N)까지 시간복잡도가 증가할 수 있다.

 

✔ 해쉬 충돌을 해결하기 위한 방법
아무리 좋은 해시 함수라도 충돌은 발생하게 된다.
충돌을 해결하기 위한 방법은 2가지다.

개별 체이닝
충돌이 발생 시 연결리스트로 연결하는 방식이다.

1. 키의 해시 값을 계산한다.
2. 해시 값을 이용해 배열의 인덱스를 구한다.
3. 같은 인덱스가 있다면 연결 리스트로 연결한다.

오픈 어드레싱
추가적인 메모리를 사용하는 Chaining 방식과 다르게 충돌 발생시 비어있는 해시 테이블의 공간을 활용하는 방법이다.
Chaining 방식과 달리, 모든 원소가 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.

 

✔️  Python의 해시 테이블 구현 방식

해시 테이블로 구현된 파이썬의 자료형은 딕셔너리다.

그렇다면, 파이썬의 해시 테이블은 충돌 시 어떤 방식을 사용할까?

→ 오픈 어드레싱 방식으로 구현되어 있다.

 

🤔 왜? 오픈 어드레싱 방식을 사용할까?

 

체이닝과 선형 탐사방식의 로드 팩터에 따른 성능 비교

오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋다.

체이닝의 경우 연결리스트를 만들어야 하는데, 이를 위해서는 추가 메모리 할당이 필요하고,
추가 메모리 할당은 상대적으로 느린 작업이기 때문이다.

 

그러나, 오픈 어드레싱은 슬롯의 80%이상이 차게 되면 급격한 성능 저하가 일어난다.
또한, 체이닝과 달리 로드팩터 1이상은 저장할 수 없다.
따라서, Python은 오픈 어드레싱 방식을 택해 성능을 높이는 대신,
로드팩터를 작게 잡아 성능 저하 문제를 해결한다.
Python의 경우, 로드팩터는 0.66이다.

 

 

출처

Hash table - Wikipedia

[자료구조] 해시테이블(HashTable)이란?

파이썬 알고리즘 인터뷰 (박상길 저)