[Hash] Changing 방식 vs Open Addressing 방식

▷ Hash (해시)

Hash 이전에 자료구조의 근간이 되던 것은 DAT이다. 
DAT(Direct Address Table) -> Hash

DAT는 리스트 안에 있는 값을 새로운 리스트의 인덱스로 활용하는 방법이다. 
인덱스를 담을 bucket을 만드는 것
그런데 이러한 DAT의 단점은, 마이너스 인덱스를 사용할 수 없다는 것이다
(파이썬은 괜찮지만, 자바나 C에서는 어렵다)
또, 원하는 값이 문자열일 경우 인덱스로 활용할 수가 없다.

이것을 극복해서 만든 것이 바로 Hash이다. 
먼저, HASH 함수를 하나 만들고, 여기에 키 값을 하나씩 넣어준다. 
그리고 키를 매개변수로 받아주면 된다. 

1. Changing 방식
링크드 리스트로 연결시키는 것
리턴에 해당하는 곳에 주렁주렁 달아준다.

2. Open addressing 방식
요즘 나온 것들
한 칸에 하나만 저장하는 것
빈 메모리를 활용해서 저장한다 (리니어, 쿼드레틱, 더블해시)