[공부] 내일배움캠프 알고리즘 3주차 Hash

해쉬(Hash) 란?

• 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조

---

해쉬 테이블

• 해쉬 테이블은 해쉬 함수를 사용하여 색인을 버킷이나 슬롯의 배열로 계산
• 데이터 다루는 기법 중에 하나로, 검색과 저장이 아주 빠르게 진행
• 파이썬의 딕셔너리를 해쉬 테이블과 같다고 봐도 된다

dict = { "name" : "asher" }

• key를 사용하여 데이터를 불러올 수 있으므로 속도가 아주 빠르다 (조회에 유용한 자료구조)
• 딕셔너리는 내부적으로 배열을 이용

---

해쉬 함수(hash function)

• 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수
• 파이썬 내장함수 hash(object)
• hash함수로 반환된 값을, 배열의 길이로 나눈 나머지값에 해당하는 index에 저장

---

put

def put(self, key, value) :

        hash_num = hash(key)
        idx = hash_num % len(self.items)
        self.items[idx] = value

        return

1. 입력받은 key를 hash함수로 연산
2. 저장할 배열의 인덱스는 hash값을 배열의 길이로 나눈 나머지
3. 해당하는 인덱스의 위치에 value 저장

---

get

def get(self, key):

        hash_num = hash(key)
        idx = hash_num % len(self.items)

        return self.items[idx]

1. 입력받은 key를 hash함수로 연산
2. 인덱스는 hash값을 배열의 길이로 나눈 나머지
3. 해당하는 인덱스의 값을 반환

---

충돌(collision)

해쉬 값이 같거나 해쉬 값을 배열의 길이로 나눈 나머지가 같은 숫자일 때 충돌

같은 인덱스로 매핑이 되어 데이터를 덮어 씌워버리는 결과 발생

체이닝(chaining)

• Linked List를 이용하여 연결지어서 해결하는 방식!
• key, value 둘다 저장
  

개방주소법

• 배열의 다음 남는 공간에 넣는 것