[자료구조 및 알고리즘] (10) 해시 테이블(Hash table)이란? 예시와 implementation

1. Hash table이란?

Hash table은 data structure의 한 종류이다. Hash table로 할 수 있는 operation에는 크게 세 종류가 있다. (1) Insert: 새로운 데이터를 집어넣는다. (2) Delete: 존재하는 데이터를 뺀다. (3) Lookup: 주어진 데이터가 해시 테이블에 이미 있는지 확인한다.

Hash table은 이 모든 operation을 모두 O(1) 시간 복잡도 안에 할 수 있다 !! -> array나 list에 비해 엄청 큰 어드밴티지임 Hash table 사용의 예시 (1) Remove duplicates 예를 들어 블로그 방문자를 기록하는데, 같은 ip로 접속하면 한 번만 기록되도록 하고 싶다.

그러면 ip 주소를 hash table에 넣으면 된다. 어떤 ip가 접속하면 lookup으로 이미 hash table에 존재하는 ip인지 확인하고, 아닌 경우에만 insert한다. lookup이 O(1) 이기 때문에 n이 크더라도...