자료구조) Hash에 대한 이해

📚 해시 자료구조?

• 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조로서,
  검색, 삽입, 삭제 과정에서 최악의 상황이 아닌경우 시간복잡도 O(1)을 가짐으로
  매우 빠르다.

참고) https://ablue-1.tistory.com/68

(출처 : 위키백과)
우선, John Smith를 보게되면 Key값이 02로 들어갔으며, value값은 bucket[2]로서 521-1234 가 들어갔다고 생각하면 된다.

특정 규칙으로 인해 각각 들어가게 되는 Key값이 결정이 나는데,
예를들어) "John Smith"와 "Lisa Smith"이 같은 Key값으로 들어갈 수도 있다는 것이다.
이를 "충돌"이라고 부르게 되는데,
충돌이 일어나지 않는 선에서 시간복잡도가 O(1)인 것이다.

Q) 충돌이 일어나면 어떻게 할 것인가?
A) 1. Chaining : bucket[2] 즉, 같은 키값으로 인해 value의 충돌이 일어나게 된다면, "연결리스트"를 이용해서
이런느낌으로 사용하면 된다.

2. Open addressing : 충돌한 지점의 Index를 넘어서, 빈 공간이 있는지 탐색 후 삽입하는 알고리즘이다.