Hash Table 자료구조

해시테이블은 키(key)와 값(value)의 한 쌍으로 이루어진 데이터를 저장합니다.
예를 들어 key로 이름, value로 전화번호를 가지는 데이터가 있다고 가정해봅시다.
이 데이터를 배열로 저장한다면 어떻게 될까요?

배열에서 park이라는 key를 찾기 위해 배열탐색을 해야합니다.
인덱스 0부터 차례대로 훑으면서 key가 park인지 아닌지 탐색하겠죠?
이 경우를 선형탐색이라고 하고, 시간복잡도는 O(n)입니다.
만약 100명의 데이터를 저장했고, 찾고자 하는 데이터가 100번째에 저장되어 있었다면
100번 탐색을 해야한다는 뜻입니다.
이러한 데이터를 저장할 때 배열을 이용한다면 값을 찾는데 시간이 좀 걸릴 것 같네요.

이런 불필요한 탐색을 줄이기 위해 우리는 해시 테이블 자료구조를 사용할 수 있습니다!

해시 테이블은 해시 함수를 사용해 키를 해시값으로 바꿔줍니다.
(* 해시 함수는 어떤 값을 복호화가 불가능한 값으로 암호화하는 함수입니다. park을 넣어서 3으로 암호화할 수는 있지만 3을 보고 이게 원래는 park이었구나 생각할 수 없다는 거에요.)
지금은 모든 키가 다른 해시값을 가지는 경우에 대해 설명할게요.
해시값을 인덱스로 사용해 배열에 값을 저장해주면
key와 value가 1:1로 대응하는 데이터를 아까와는 다른 방식으로 저장할 수 있겠네요.
우리가 park을 가지고 해시 테이블에서 park의 전화번호를 알고자 한다면
해시함수로 바로 인덱스를 찾을 수 있습니다!!
해시값이 겹치는 경우가 없기 때문에 인덱스만 알면 값을 알 수 있죠

여기까지만 보고 잠깐 생각해볼게요.
우리가 저장하려는 데이터가 만개, 십만개, 1억개가 된다고 생각해보면 해시값이 완전히 겹치지 않는 해시함수를 만들 수 있을까요??
아마 어려울 것 같아요.
그래서 우리는 해시 테이블이 충돌하는 경우에 대해 다룰 수 있어야 합니다.

해시값이 충돌할 때 리스트를 이용하는 '연쇄법'에 대해 알아봅시다.

Linked List를 이용해서 해시값이 충돌하더라도 데이터를 저장해줄 수 있습니다.