개발자라면 꼭 알아야 할 Hash Table의 모든 것! (YouTube 노마드 코더)
- Hash Tables는 Key : Value System을 이용하여 자료를 정리한다. (ex. 사전)
- 배열(array)은 데이터를 찾을 때 Linear Search(선형 검색)을 하기 때문에, 시간 복잡도가 O(n)
- 그러나 Hash Tables은 시간 복잡도가 O(1)
- 같은 프로그램이라도 배열로 작성하기보다, Key에 값을 넣고, Value=True로 하면 시간이 훨씬 많이 단축됨
Hash Tables의 작동 원리는 어떻게 될까?
- Hash Tables 내부에는 array 구조가 있고, 모든 Hash Tables 값들은 그 array에 존재
- Array는 (위에서 적은 것처럼) 선형 검색을 이용하여 index에 접근하지만, Hash Tables은 Hash Function을 이용함
- Hash Function: 저장한 Key를 일정한 규칙에 의해 정수값(고유한 index)으로 바꿔 버림. 그 index에 value를 저장함.
- Collision(해시 충돌): 여러 개의 Key가 같은 index를 가짐
이때의 해결법 중 하나는, 그 index에 또 다른 배열을 넣음
이후 해당 index에서 값을 찾을 때는 선형 방법을 이용하게 됨
=> Hash Tables이 언제나 O(1)의 시간 복잡도를 갖는 것은 아님!
