[Algorithm] Hash table

Hash Table 이란? (key, value)로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있다는 장점이 있다. 해시 테이블이 빠른 검색 속도를 제공하는 것은 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. Ex) (key, value) = ("John Smith", "521-1234")를 크기가 16인 해시 테이블에 저장하면, 먼저 index = hash_function("John Smith") % 16으로 index를 구해서 array[index] = "521-1234"로 저장한다. 평균 시간 ..