1. 해시 테이블(Hash Table)이란?

Hash table(hash map)이란 해시함수를 사용해서 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조를 말한다. 다시 말해 해시 테이블은 어떤 특정 값을 받아서 해시 함수에 입력하고, 함수의 출력값을 인덱스로 삼아 데이터를 저장한다. 파이썬의 dictionary, 루비의 Hash, 자바의 Map이 해시 테이블의 대표적인 예다.

2. 해시 테이블(Hash Table) vs 해시 맵(Hash Map)

	중복 키에 대한 처리	thread - safe(동기화 보장)	key와 value에 null 허용 여부
해시 테이블	키가 같은 값을 두 번 넣게 되면 초기 값을 유지	synchronized가 걸려있기 때문에 멀티 스레드 환경에서 데이터 조작에 대한 일관성이 보장된다 thread - safe	허용 하지 않는다
해시 맵	키가 같은 값을 두 번 넣게 되면 두 번째 값으로 덮어버린다	thread - safe 하지 않다 하지만 'Collections.synchronizedMap' 처럼 synchronized를 래핑하는 함수를 활용하면 HashMap도 충분히 스레드 세이프하게 동작시킬 수 있다.	허용한다

싱글 쓰레드 환경이면 HashMap을, 멀티 쓰레드 환경이면 HashTable을 사용하는 것이 좋다.(사실 HashTable 대신 ConcurrentHashMap을 쓰는 것이 좋지만, 일단은 다루지 않겠다.) 속도의 경우 synchronized 처리가 없는 해시맵 속도가 압도적으로 빠르다.

3. 해시 테이블 특징

• 기본 연산으로는 search, insert, delete가 있다.
• 순차적으로 데이터를 저장하지 않는다.
• key를 통해서 value를 얻을 수 있다. => 이진탐색트리나 배열에 비해서 속도가 획기적으로 빠름
• 커다란 데이터를 해시해서 짧은 길이로 축약할 수 있기 때문에 데이터를 비교할 때 효율적이다.
• value는 중복 가능하지만 key는 유니크해야 한다.
• 수정 가능하다. (=> mutable)
• 보통 배열로 미리 hash table 사이즈만큼 생성 후에 사용한다.

해시란 단방향 암호화 기법으로 해시 함수를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미한다. 이때 매핑 전 원래 데이터의 값을 key, 매핑 후 데이터의 값을 hash value, 매핑하는 과정을 hashing이라고 한다.

해시 함수를 이용해서 key를 hash value로 매핑하고, 이 hash value를 index로 삼아 데이터의 value를 buckets(혹은 slots)에 저장했다.

4. 해시 테이블의 시간복잡도

해시 테이블은 key-value가 1:1 매핑되어 있기 때문에 검색, 삽입, 삭제 과정에서 모두 평균적으로 O(1)의 시간복잡도를 갖는다. 공간 복잡도는 O(N)인데 여기서 N은 키의 개수다.

시간 복잡도	평균	Worst Case
공간	O(n)	O(n)
탐색	O(1)	O(n)
삽입	O(1)	O(n)
삭제	O(1)	O(n)