해시 테이블은 key, value를 저장하는 데이터 구조로 key값을 가지고 hash function을 통해 해당 value값을 저장 시킬 주소를 알 수 있다. 이렇게 저장, 삭제를 하게 되면 index값을 알 수 있어 바로 해당 value값에 접근 할 수 있어 충돌이 없는 해시 테이블이라 가정을 했을때 어떤 자료든 search하는데 시간복잡도가 O(1)이 될 수 있다.
그럼 json도 key, value를 저장하는 데이터 구조인데 해시 테이블과 뭐가 다를까??
json의 key값은 string만 저장할 수 있는 반면 hash table의 key값은 어떤값이든 저장 할 수 있다.
좋은 HashFunction의 기준은 해시 충돌 확률로 결정되는데, 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가하게 되기 때문이다.
해시함수중에는 암호학적 해시함수(Cryptographic Hash Function)와 비암호학적 해시함수로 구분되곤 한다.
암호학적 해시함수의 종류로는 MD5, SHA계열 해시함수가 있으며 비암호학적 해시함수로는 CRC32등이 있다.
key값을 가지고 hash function을 통해 나온 index가 고루 분포 되면 상관이 없지만 그렇지 않을 경우 충돌이 일어나게 된다. 충돌을 해결하는 대표적인 방법
해결방법은 있지만 둘다 최악의 경우 조회 복잡도가 원소 개수에 따라 시간 복잡도가 O(n)이 될 수 있다.