데이터의 검색과 저장이 아주 빠르다.

딕셔너리 와 해쉬 테이블은 같다고 보면된다.
데이터를 다 찾기 위해 다 찾지 않고 원하는 key만 찾아 데이터를 찾음
딕셔너리가 내부적으로는 배열을 사용하다.

class Dict:
    def __init__(self):
        self.items = [None] * 8

fast와 slow가 이 배열 어딘가에 있다면 어떻게 몇번에서 찾아야 하는가?
-> 해쉬 함수를 이용한다.

• 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수
  hash('fast') = 임의의 무작위 숫자가 나옴
  hash('fast')%배열길이 = 배열내 fast라는 key값이 들어가는 위치(index번호)
  딕셔너리[hash(key값)%배열길이] = "value값" ->딕셔너리에 Key:value를 넣는 방법

class Dict:
    def __init__(self):
        self.items = [None] * 8

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index] = value
        return 

    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index]

같은 배열길이로 나누다 보면 index값이 같아 질 때가 있다.
-> 충돌이 일어날 수 있다.

해결
1. 링크드 리스트를 이용 = chaining체이닝

• 링크드 리스트로 뒤 이어 저장 but key도 같이 저장해야함

  class LinkedTuple:
     def __init__(self):
         self.items = list()
  
     def add(self,key,value):
         #같은 key값의 append한다 = 그 뒤에 넣는다.
         self.items.append((key,value))
  
     def get(self,key):
         #items에sms key,value가 있는데 그것을 k,v에 넣는다.
         for k,v in self.items:
             if key == k:
                 return v

링크드 리스트를 만드는 class 설정 add는 처음값의 뒤에 계속 넣는것, get은 찾는것

class LinkedDict:
def init(self):
self.items = [] #[linkedTuple(), *8]을 만든다.
for i in range(8):
self.items.append(LinkedTuple())

def put(self,key,value):
    #index 생성
    index = hash(key) % len(self.items)
    #미리 설정한 add라는 메소드를 이용해서 self.itmes에 넣는다.
    self.items[index].add(key,value)

def get(self,key):
    index = hash(key) % len(self.items)
    return self.items[index].get(key)

체이닝으로 충돌을 방지하는 코드
-> put으로 8개 이상 넘어가면 발생되는것은?

> https://velog.io/@2seunghye/파이썬과-자료구조해쉬-테이블

all_array 전체 학생, present_array 출석학생
전체 학생의 딕셔너리를 만들고
거기서 출석학생을 전부 제거하면 -> 출석 안한 학생만 남음

def get_absent_student(all_array, present_array):
#빈 딕셔너리
student_dict = {}
#학생전체의 이름을 key값으로 value는 True로 딕셔너리에 넣기
for key in all_array:
student_dict[key] = True
#출석학생 이름을 key값으로 있으면 지우기
for key in present_array:
del student_dict[key]
#남은 학생 찾기
for key in student_dict.keys():
return key