! index() 함수로 검색하기

리스트 또는 튜플에서의 검색은 각 클래스의 index() 함수로 가능하다.
다음과 같은 형식으로 호출한다. odj.index(x, i, j)
j나 i, j는 생략할 수 있다.

x를 찾아주며, 가장 작은 인덱스를 반환하고, 없으면 ValueError 를 내보낸다.

해시법

검색과 더불어 데이터의 추가, 삭제도 효율적으로 수행할 수 있는 해시법.

정렬된 배열에서 원소 추가 하기(데이터 추가)

1. 이진 검색법으로 들어갈 부분 탐색
2. 삽입 지점 뒤의 원소 전부 한 칸씩 뒤로 이동
3. 삽입 지점에 데이터 추가.

원소 추가에 들어가는 복잡도는 O(n).
데이터 삭제시에도 같다.

해시법(hashing)

'데이터를 저장할 위치 = 인덱스' 를 간단한 연산으로 구한다.
원소의 검색뿐 아니라 추가, 삭제도 효율적으로 수행.

? 해시값(hash value)

키가 5, 6, 14 등이 주어질때,
원소 개수로 키값으로 나누고 나온 나머지를 해시값이라고 한다.

이 값을 인덱스로 해서, 원소를 새로 저장한 배열이 해시 테이블(hash table)이라고 한다.
이제 새로운 값을 넣는다면, 일치하는 해시값을 가진 것이 없다면
이동할 필요 없이 데이터를 넣을 수 있다.

이러한 변환과정을 해시함수(hash function)이라고 한다.

주로 나머지를 구하는 연산, 또는 그 연산을 응용할 때 쓰는 함수이다.
해시 테이블에서 만들어진 원소를 버킷(bucket) 이라고...

... 그럼 해시테이블의 키값을 말하는 건가? 키랑 해시값을 통틀어 버킷이라고 하는건가..
그냥 해시값이 지정된 원소가 들어갈 자리를 버킷이라고 하는 것같다.

예를 들어, 버킷 x[5] 에 원소가 들어가야한다... 라고 하니까.

해시 충돌(hash collision)

해시값이 중복되어도... 보통 키와 해시값은, 키 여러개의 해시 하나여도 일반적으로 된다고는 한다.
이처럼 저장할 버킷이 중복되는 현상을 충돌이라고 한다.

이에 대한 대처법은 두 가지다.

• 체인법
  해시값이 같은 원소를 연결리스트로 관리.
• 오픈 주소법
  빈 버킷을 찾을 때까지 해시를 반복한다.

체인법(chaining)

체인 모양의 연결리스트로 관리한다고 하여 체인법.
오픈 해시법이라고도 한다. (open hashing)

버킷에 가장 앞쪽 노드를 담아두고, 그 뒤에 노드가 줄줄이 이어지는 식.

해당하는 해시값에 데이터가 없으면 None, 같은 해시값에 있는 경우를 table[n] 등으로 표기.

체인법으로 노드 정의 시, 클래스에는 세가지를 지정한다.

• key (키, 검색하는 키워드.) (임의의 자료형)
• value (값, 찾고자 하는 데이터.) (임의의 자료형)
• next (뒤쪽 노드를 참조하는 값.) (Node형)

체인법으로 해시 클래스를 구현하면, 두 가지가 들어간다.

• capacity (해시 테이블의 크기)
• table( 해시 테이블 리스트를 선언.) = [None] * self.capacitiy

? hash_value() 함수로 해시값을 만들어보기.

해시는 인덱스만 충돌하지 않는다면 시간 복잡도는 O(1)이지만,
테이블을 충분히 만들때에만 보장되고,
테이블을 크게 만드는 만큼 메모리 낭비가 생긴다. 이를 시간과 공간의 상충관계(trade-off) 문제가 발생한다고 한다.

그러기 위해서는 해시 함수가 해시 테이블 크기보다 작거나 같은 정수를 고르게 생성해야한다.
그래서 해시 테이블의 크기는 소수를 선언한다고...(왜? 무슨 관계지.)

• key가 int 형인 경우
  아까처럼, capacity 로 나눈 나머지를 해시값으로 한다.
• key가 int 형이 아닌 경우.
  표준 라이브러리로 형 변환 시켜서 해시값을 얻는다.
  int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity

1. sha256 알고리즘 : hashlib 모듈에서 제공하며, RSA의 FIPS 알고리즘을 바탕으로 주어진 바이트 문자열의 해시값을 구하는 해시 알고리즘 생성자.(constructor). md5등 다른 알고리즘도 가능하다.
2. encode() : 바이트 문자열의 인수를 sha256에 전달해야해서, key -> str -> encode 에 전달하여 바이트 문자열을 생성.
3. hexdigest() : sha256 알고리즘이 만든 해시값을 16진수 문자열로 꺼낸다.

key -> str -> encode -> sha256->hexdigest-> int.

키로 원소를 검색하는 search() 함수

어떤 값을 넣었을 떄,
어떤 과정을 거쳐서,
무슨 경우가 나오는지 전체적으로 포괄하고 정리하고 있다.

1. 해시 함수를 사용하여 키를 해시값으로 변환.
2. 해시값을 인덱스로 하는 버킷 확인.
3. 연결리스트를 맨 앞부터 차례로 스캔. 같은 값을 발견해 검색 성공하거나, 발견을 못해 검색 실패.

hash_value 함수에 키 값을 넣은 다음에,

hash = self.hash_value(key)
해시값 33같은게 되었다고 가정.
p = self.table(hash)
p는 해시값 33에 해당하는, 해시테이블의 인덱스를 가리킴.
table[33]이 된것.

근데 노드가 갖는게 키, 밸류, 넥스트 잖아? p는 노드야?
아~ 노드가 있고, 노드가 갖는 값이 밸류겠네.

while True :
if node.value == p :
	 if node.key == x :
     return node.value
     elif node.key == None :
     return -1
     else :
     node.value = node.next

일단 써봤다.
책을 확인해보자.

내가 쓴 건 p와 찾는 value가 일치하는 경우로 썼는데,
사실 찾는 value가 p잖아?

틀렸다... 당연하다.

끊임없이 넘어가면 value가 None을 반환하는 지점이 있으므로,
p가 None인 것을 기점으로 판단,
계속 넘기되 만약 p.key가 주어진 key값과 일치한다면 p.value를 반환하고 있다..
...

... 헷갈려.

p는 대체 뭘로 이루어져있는 거지?
table은 리스트잖아?

[None, None, None] 형식으로 출발.
아무것도 없다면 table[0]은 None.
뭐라도 있다면 table은 노드로 이루어져있음.
[{key : 1, value: 3}, None, None, None] 형식.
나는 key 1을 찾고 싶다.
key 1넣음.
key 1 넣은 걸 3으로 바꿔줌.
value가 3에 해당하는 걸 찾음.
key 1이면 들어갈 버킷이 아예 None이면 실패 띄움.
만약 p.key = key와 일치한다면 p.value를 반환.
안 비었는데, 일치하지 않는다면 p를 다음으로 보냄.

여기서 구성한건
1. None 확인
2. 맞나? 아닌가? 맞으면 성공, 아니면 다음.

내가 구성한건
1. 맞나? 아닌가? None인가? 맞으면 성공, 아니면 다음, None이면 실패 반환.

후자도 가능? 하긴 할텐데
사실 None을 먼저 확인하는게 더 확인 과정이 적긴 하다.
전자를 바로 떠올리려면 어떻게 생각해야하지?

근데 사실 null 인지 아닌지 확인 하는 건 모든 알고리즘의 첫번째 확인 작업이긴 하지.
조건 설계 시 판단 순서를 ...

아니, 조건을 확인할 때에
조건 중에 먼저 확인 되면
다른 건 확인할 필요 없는 걸 미리 추려내는 게 중요할 것 같다.

내 코드의 문제점은,
1. 애초에 key로 검색해야한다는 점.(데이터 값으로 검색하지않는다. 나이 값을 알기 위해 정확한 나이값 29를 넣고 찾아달라고 하지 않는다는거다. 애초에 알고 있으면 찾을 필요가 없으므로!)
2. ..
아 문제 너무 많아
그냥 넘어가겠다

맨 눈으로 쓰기보다, 확실히 확인하는거

1. 넣는 값.
2. 나오려는 값.
3. 조건문.

을 미리 써둬야겠다.
줄글로 한번 써두는 것도 좋고.
너무 잘못쓴게 많아서 애초에 뭘 하려고 했는지 모르겠다.

전체 코드.

while p is not None :
	if p.key == key :
    	return p.value
    p = p.next
    
return None