😜 Hash Table 이란?

연관배열 구조를 이용해 key에 value를 저장하는 자료구조
= key-value로 이루어진 자료구조

📍연관배열(associative array) 구조란?

key 1개와 value 1개가 1:1로 연관되어 있는 자료구조
= key를 이용해 value를 도출

😜 Hash Table의 구조

hash table은 Key 키, Hash Function 해시 함수, Hash 해시, Value 값, Bucket(slot) 저장소로 이루어져 있음

key는 hash function을 통해 hash로 변경, hash는 value와 매칭되어 저장소에 저장

key
1. 고유한 값, hash function의 input
2. key값을 그대로 저장소의 index로 사용할 경우 key의 길이만큼의 정보를 저장해야 하는 공간도 마련해야 하므로 고정된 길이의 hash로 변경

hash function
1. key를 hash로 바꿔주는 역할
2. 다양한 길이를 가지고 있는 key를 일정한 길이를 가지는 hash로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와줌
3. 서로 다른 key -> 같은 hash가 되는 경우 = 해쉬 충돌
(해쉬 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는것이 중요함)

value
1. 저장소(버킷, 슬롯)에 최종적으로 저장되는 값
2. key와 매칭되어 저장, 삭제, 검색, 접근이 가능

hash
1. hash function의 결과물, 저장소에서 value와 매칭되어 저장됨

📍정리

Hash = 인덱스, Hash Function = key->hash로 만들어주는 function, Hash Table = hash를 주소로 삼아 데이터 저장하는 자료구조

1. 데이터들이 해시함수에 의하여 분류가 된다
2. 분류된 데이터들은 해시 함수에 의해서 해시 테이블안에 예쁘게 규칙에 의해서 들어가게 된다 => 해싱