🔎 해시테이블이란?
- key에 data를 저장하는 데이터 구조이다. 이는 파이썬의 딕셔너리 구조와 동일하다.
- key를 hash 함수에 넣고 일정한 길이의 해시 코드를 얻게 된다.
이후, 3으로 나눈 나머지인 0,1,1 이 index가 되며 이를 통해 data 를 되찾을 수 있다.
🔎 장점/단점
-
저장/읽기의 속도가 빠르다. 검색,조회가 빈번한 작업인 경우에 해시테이블을 활용하면 빠르게 데이터를 관리하는 효과를 얻을 수 있다.
-
index가 중복되는 경우 저장시에 충돌이 발생한다는 것이 단점이다.
해시 함수가 10을 나눈 나머지를 구하는 것이라고 가정했을 때, 숫자 28을 10으로 나누면 8이 나머지가 된다. 이를 인덱스가 8번인 해시테이블에 28을 저장하여 관리하는 방식이 해시테이블이다. 하지만 18의 나머지도 8이기 때문에 28과 18 데이터를 저장할때 충돌이 발생하게 된다. 이를 해결하는 방법에는 링크드리스트 자료 구조를 사용하는 체이닝 기법이 있다.
Chaining 방식은 선형탐색으로 빈공간에 버킷에 값을 저장하는게 아닌
한 버킷 공간에 여러 값들을 노드로 연결 시켜주는 기법이다.
class ListNode:
def __init__(self,key=None, value=None):
self.key = key # 키
self.value = value # 값
self.next = None # 다음 노드를 가리키는 포인터- 노드의 생성자 함수를 정의
ListNode 클래스는 각 해시 버킷에서 연결 리스트의 노드 역할을 수행합니다.
처음 노드의 key와 value의 기본값은 None으로 지정
def put(self,key,value):
index = key % self.size # 해시 함수를 통한 인덱스 계산
new_node = ListNode(key,value) # 새로운 노드 생성
item = self.table[index] # 해당 인덱스의 첫 번째 노드 가져오기
if not item: # 해당 인덱스가 비어 있으면
self.table[index] = new_node # 새 노드 추가
return
# 이미 키가 존재하는 경우 값을 업데이트하고 종료
while item:
if item.key == key:
item.value = value # 이미 존재하는 키의 경우 값 업데이트
return
if not item.next: # 다음 노드가 없으면 반복문 종료
break
item = item.next
item.next = new_node # 연결 리스트의 끝에 새 노드 추가key % self.size 를 통해 각 키에 대한 해시값을 계산하고 이를 해시테이블의 크기로 나눈 나머지를 인덱스로 사용합니다.
new_node 라는 key와 value가 할당된 노드를 저장합니다.
해당 버킷에 생성된 노드가 없으면 새로운 노드값을 버킷에 저장하고 return합니다.
하지만, 다른 노드가 존재하고 동일한 key값이 존재한다면 새로운 value값을 넣어주고 return
버킷에 똑같은 key가 존재하지 않는다면 새로운 노드를 연결 리스트의 끝에 연결시켜줍니다.
def get(self,key):
index = key % self.size # 해시 함수를 통한 인덱스 계산
item = self.table[key] # 해당 인덱스의 첫 번째 노드 가져오기
# 해당 인덱스의 연결 리스트를 순회하면서 키를 찾아 값을 반환
while item:
if item.key == key:
return item.value # 키에 해당하는 값을 반환
item = item.next
return None # 키가 없으면 None 반환해싱을 통해 인덱스를 가져오고 해당 인덱스를 통해 버킷에 접근한다.
해당 인덱스의 연결 리스트를 순회하면서 만약 key 값이 같은 노드가 존재한다면
해당 노드의 value를 return한다. 노드를 모두 순회하였지만 같은 key값을 찾지 못했다면 None을 반환한다.
def remove(self,key):
index = key % self.size # 해시 함수를 통해 인덱스 계산
item = self.table[index] # 해당 인덱스의 첫 번째 노드 가져오기
prev = None
# 해당 인덱스의 연결 리스트를 순회하면서 키를 찾아 삭제
while item:
if item.key == key:
if prev:
prev.next = item.next # 이전 노드가 다음 노드를 가리키도록 조정
else:
self.table[index] = item.next # 첫 번째 노드를 다음 노드로 교체
return True
prev = item
item = item.next
return False # 삭제할 키가 없으면 False 반환remove 메서드는 주어진 키에 해당하는 노드를 삭제하는 구조를 가지고 있습니다.
해당 인덱스의 첫 번째 노드를 가져온 후, 삭제할 노드를 찾기 위해 연결 리스트를 순회하면서 주어진 key를 찾습니다. item이란 변수는 현재 순회중인 노드를 가리키며 prev변수는 item 이전의 노드를 가리킵니다.
만약 prev가 None이 아닌 경우 == item이 첫 번째 노드가 아닌 경우:
prev.next 를 item.next로 설정하여 이전 노드가 삭제할 노드의 다음 노드를 가리키도록 합니다.
prev가 None인 경우 == 첫 번째 노드를 삭제할 경우
self.table[index] 를 item.next로 설정하여 첫 번째 녿를 삭제할 노드의 다음 노드로 교체합니다.
삭제 성공 시 True를 반환하고, 삭제할 노드가 없는 경우( item이 None일 경우) False를 반환합니다.
솔직하게 Stack부터 너무 다 추상적이라 뭐가 뭔지 잘 모르겠다 🤕
