add() 함수
단순히 해당하는 키 값을 넣으면 되지 않나? 했는데...
키 값을 해시값화,
해당하는 빈 버킷 찾기 전에,
이미 같은 값이 있으면 추가 실패... 라고 하더라.
value = self.hash_value(key)
p = self.table[value]
if search(p) != None :
return False
while True :
if p.key != None :
p = p.next
else :
p.key = key
return True정답코드는...
p가 None이 아닌가?
key값이 일치하는가?
일치하지 않는다면 다음 노드로.
=> None까지 도달.
노드를 받은 값으로 생성. 키, 값, 그 노드에 관한 참조.
참조 값에 노드 넣어놓음.
성공했다는 사실 전달.
=> 성공 추가
내가 쓴건 node를 넣은게 아니라 key값만 넣었고,
굳이 search까지 호출해서 전부 스캔한뒤 진행할 필요 없이
노드 하나씩 그 자리에서 확인.
(근데 내 방식이 문제가 된다면 뭐가 문제가 되는걸까? 사실 search 들어갈 자리에 똑같은 식이 들어가 있을 뿐이라.)
(아, 나는 search로 유무를 확인한다음, 다시 next까지 걸어가고 있지만,)
(정답 코드에서는 이미 유무를 확인하고, 없다면 도달한 끝에서 바로 대입하고 있어서 연산 수가 적다.)
while p is not None :
if p.key == key :
return False
p = p.next
temp = Node(key, value, self.table[hash])
self.table[hash] = temp
return True살짝 헷갈리는 건...
맨 뒤에? temp로 넣어야하는건? p여야하지않나?
왜냐하면 p로 기껏 맨끝 p까지 도달했는데,
바로 self.table[hash]를 넣으면 의미...있나?
...
아
큰일났군
"나이" : 29 (키 : 값) 으로 노드를 넣는 거였다. 나는 값이 해시값인줄 알았어...
"나이" : 29를 넣어본다.
"나이", 29, 해시테이블[나이를 나타내는 해시값]
두번째
"나이" : 30을 넣어본다.
"나이", 30, 해시테이블[나이를 나타내는 해시값]
여기서 첫번째에서 다음걸 찾아본다.
주로 다음걸로 갈때
해시테이블[나이를 나타내는 해시값].next를 한다.
해시테이블[나이를 나타내는 해시값].next = next
여기서 갖게되는 next라는게 대체 뭔가?
해시테이블[나이를 나타내는 해시값]이라는 게 next가 되어버린다고 치자.
이때 같은 값을 또 대입해보자.
해시테이블[나이를 나타내는 해시값]2.next = 해시테이블[나이를 나타내는 해시값].next
가 된다.
그럼 결국 내 노드들이 가진 건 이런 구조가 된다.
"나이", 29, 해시테이블[나이를 나타내는 해시값], next : next
"나이2", 30, 해시테이블[나이를 나타내는 해시값], next : 해시테이블[나이를 나타내는 해시값].next
....
그럼 내가 새로운 값을 넣는다고 치자.
"나이", 31.
이건 결국
"나이", 31, 해시테이블[나이를 나타내는 해시값]을 가지게 될 거고.
이미 앞에 next라는 게 앞의 노드로 설정되어있기 때문에,
next가 유동적으로 움직이는 한 따로 설정해줄 필요가 없다.
그래서 add의 논리는 버킷에 중복값만 없다면 그냥 버킷에 키와 값을 넣어준다.
.. 앞부분을 잘못썼군. 수정해두겠다.
remove() 함수
뭐 그래도 이해했으니까..
넣는값!
키를 넣어서 키가 key인 원소 삭제.
출력값! 없음.
조건문!
해당 버킷이 있나요?
버킷에 키가 일치하는 게 있나요?
있다면....
1 버킷이 다른 키 값도 가지고 있다면,
뭐야 이거 어떻게 지워. next만 바꿔주면 되나?
다음 노드의 next를 이 키의 next로 설정? 해주면 되나?
"나이", 29, 해시테이블[나이를 나타내는 해시값], next : next
"나이2", 30, 해시테이블[나이를 나타내는 해시값], next : 해시테이블[나이를 나타내는 해시값].next
"나이3", 31, 해시테이블[나이를 나타내는 해시값], next : 해시테이블[나이를 나타내는 해시값].next.next
"나이4", 32, 해시테이블[나이를 나타내는 해시값], next : 해시테이블[나이를 나타내는 해시값].next.next.next
=>
"나이", 29, 해시테이블[나이를 나타내는 해시값], next : next
"나이3", 31, 해시테이블[나이를 나타내는 해시값], next : 해시테이블[나이를 나타내는 해시값].next
"나이4", 32, 해시테이블[나이를 나타내는 해시값], next : 해시테이블[나이를 나타내는 해시값].next.next.next
안 되는데?
그렇다고 모든 뒤의 next를 지워줄 거야?
- 버킷에 그 키값 뿐이라면, None 반환.
정답 보기
찾은 키가 중간에 위치한 경우: prev_node.next를 current_node.next로 설정하여 중간 노드를 건너뛰도록 합니다.
찾은 키가 첫 번째 노드에 위치한 경우: self.table[hash_value]를 current_node.next로 설정하여 첫 번째 노드를 건너뛰도록 합니다.
키를 찾지 못한 경우: False를 반환합니다.
def remove(self, key):
hash_value = self.hash_function(key)
current_node = self.table[hash_value]
prev_node = None
while current_node is not None and current_node.key != key:
prev_node = current_node
current_node = current_node.next
if current_node is not None:
if prev_node is not None:
# 중간 노드를 삭제하는 경우
prev_node.next = current_node.next
else:
# 첫 번째 노드를 삭제하는 경우
self.table[hash_value] = current_node.next
return True
else:
return False하...
챗지피티 협찬입니다
책에서는 노드가 none이 아닌 동안에는
일치하는 키값을 찾았을 때
찾은 키 값이 첫번째 노드일경우 : 다음 노드를 참조하도록 설정
찾은 키 값이 그 이상번째 노드일 경우 : 앞 노드의 참조가 다음 노드가 되도록 설정
성공.
만약 키값을 아직 못찾았을 때
순서를 다음으로 넘김
결국 다음으로 계속 넘겼는데 none을 반환, 즉 빈 노드면 실패.
p를 포인터처럼 이해하고,
수식을 진짜 문장처럼 읽는게 편하다..
대충 구조를 알았으니 진짜 이해했는지 써보겠다..
하 누구도 나에게 해시테이블 오래 걸리실걸요..^^? 라고 안해줬는데...
p = self.table[hash]
pp = None
while p is not None :
if p.key == key :
if pp is None:
self.table[hash] = p.next
else :
pp.next = p.next
return True
else :
pp = p
p = p.next
return False굿!
코치님은..
이번주차가..
제일 쉬운거라고했는데..
우니?
일어나자...
알고리즘 이해해야지...
dump() 함수
모든 원소를 한꺼번에 통째로 출력.
table[0] 부터 table[capacity] 까지 출력하며,
뒤쪽 노드를 찾아가면가 각 노드의 키와 값을 출력하는 작업을 반복.
함수 이름 dump는 덤프트럭에서 짐이 한 번에 내리는 모습에 비유.
넣는값(테이블)
나오는 값(모든 원소)
조건문
이 해시 테이블이 none이 아닌 동안 반복
=> 출력
.next가 none이 아닌 동안 반복
해시테이블 출력.
다음 노드로 변경.
테이블 다음 값으로 이동.정답코드에서는 범위를 capacity로 설정해주고,
그 범위의 table을 꾸준히 출력했다.
첫번째 문장과 맨 마지막 문장을 for로 범위 설정해서 반복해준 것이다.
오픈 주소법(open addressing)
충돌이 발생했을 떄, 재 해시를 수행하여 빈 버킷을 찾는다.
closed hashing 이라고도 한다. (뭔 오픈과 클로즈를 같은 단어 의미용으로 쓴담.. 뒤에 붙은건 다르지만.)
체인법은 오픈 해싱, 오픈 주소법은 클로즈 해싱.
원소 추가
원래의 값에 1씩 더해줘서 다음 해시를 찾는걸 반복하여 원소를 추가한다.
빈 버킷이 나올떄까지 반복하여, 선형 탐사법(linear probing)이라고도 한다.
원소 삭제
해시를 태그한다고 해서 그 값이 나오지않는다.
위와같은 추가 과정에서 재해시를 반복했으므로 다른 곳에 있을 수 있기 때문이다.
그래서, 각 버킷에 속성을 추가로 부여한다.
- 데이터가 저장되어있음(숫자)
- 비어있음(-)
- 삭제 완료
음...
비어있음 : 해시값이 같은 데이터가 존재하지 않는다.
삭제 완료 : 해시값이 같은 데이터는 다른 버킷에 저장되어있다.
즉 한번 중복을 거쳤었는지 표시하는 속성이라고 생각하면 될듯.
원소 검색
속성이 삭제 완료라면, 재해시해서 찾아봄.
속성이 비어있음이라면, 없으니 실패 처리.
클래스 구성
버킷의 속성
데이터 있음, 비어있음, 삭제 완료로
class status(enum)을 생성. (0, 1, 2 로 부여.)
해시를 구성하는 버킷
init 함수에서 key, value, stat 부여.
set 함수로 필드에 값 설정.
set_status 함수로 속성(버킷 속성, stat) 설정.
오픈 주소법으로 구현하는 해시 클래스
init에서 용량, table 설정.
대신 안에 None이 아니라 Bucket()으로 만들어둔 버킷 클래스를 넣어둔다.
hash_value. 동일
rehash_value 키->해시값 처리한것에 1을 더해서 재해시(용량으로 나누기.)
search_node 검색 시에는
비어있다면 멈추고,(p.stat == Status.EMPTY 같은 수식으로 확인)
값이 있고 일치한다면 돌려주고,
셋 다 아니라면 재해시해서 포인터 이동.
search는
앞에서 key를 넣어 찾은 노드에서,
만약 None이 아니라면 p.value.를 반환
...
대충 속성을 확인한 뒤에 똑같은 방식으로 진행한다.
