[Algorithm] 해시 테이블의 개념, 성질, 해시 함수의 생성 방법 및 충돌의 해결
Hash Table이란? 해시 테이블은 해시 함수를 통해 키가 저장될 자리를 키의 값으로 결정하는 자료구조이다. 특정 키를 검색, 삽입, 삭제하기 위해 사용할 수 있는 자료구조로 리스트, 검색 트리 등을 사용할 수 있는데, 해시 테이블은 여기에 걸리는 시간을 최대한 단축하고자 만들어진 자료구조이다. 검색, 삽입, 삭제 작업에 배열을 이용한다면 평균 Θ(n) 시간이 걸리고, 일반적인 검색 트리를 이용하면 평균 Θ(log n), 최악의 경우 Θ(n) 시간이 걸린다. 그리고 균형 이진 검색 트리를 사용하면 최악의 경우에도 Θ(log n)을 보장 받을 수 있다. 이러한 자료구조도 좋은 성능을 낼 수 있지만, 더한 효율을 내기 위해서 만들어진 것이 해시테이블인 것이다. 해시 테이블의 기본적인 아이디어는, 앞선 자..
