Hash (해시)

Hash

• 임의의 크기를 가진 데이터(key)를 고정된 데이터의 크기(value)로 변환시키는 것
• 시간복잡도: O(1) // 해시 값 자체를 index로 사용, 검색과 저장이 빠른 자료구조

---

Direct Addressing 

• key-value 쌍의 데이터를 배열에 저장할 때, key값을 직접적으로 배열의 인덱스로 사용하는 방법
• key값의 최대 크기만큼의 공간을 사용. 크기는 매우 큰데 저장하고자 하는 데이터가 작다면 공간 낭비의 위험
• ex) key값이 3인 데이터가 있다면, 이를 index가 3인 위치에 저장하고 데이터 연결 / 삭제는 NULL 값 넣기

---

Hash Table

• key값을 테이블에 저장할 때 "함수"를 이용해서 계산을 수행한 후, 그 결과값을 index로 사용하여 저장

해시 함수(Hash Function)

• 임의의 길이의 데이터를 입력받아 일정한 길이로 변환시켜주는 함수 
• key값을 해싱을 통해 해시 값 또는 해시코드로 변경하고, 이 해시 값이 저장위치가 된다
• 계산이 복잡하지 않고 키 값에 대해 중복없이 해시값을 고르게 만들어 내는 함수가 좋은 함수

---

Open Addressing

• 모든 데이터(key+데이터)를 테이블에 저장하는 방법
• 데이터를 직접 모두 읽어 오기 때문에 포인터를 사용하지 않아도 됨

---

+) 백준 문제 중 알파벳+제곱 사용했던 거 원리도 추가하기