Hash란?
- 자바 알고리즘을 공부하다 보면 가장 많이 나오는 단어 중 하나가 Hash입니다.
- Hash의 핵심은 KEY와 VALUE 입니다. Key와 Value가 한 쌍으로 존재합니다.
- Key와 Value의 쌍을 Hash Table이라고 부릅니다.
- Key는 Hash에서 매핑할 때 사용하는 인덱스라고 생각하시면 됩니다.
- Key는 절대로 중복되지 않는다는 특징을 가지고 있습니다.
- 만약 같은 Key에 값을 넣으면 이전 값은 사라지고 나중에 들어온 값만 남습니다.
- Value는 Key로 매핑했을 때 나오는 값을 말합니다.
- Hash는 배열의 인덱스와 다르게 순차적으로 저장되는 것이 아니라 전 영역에 고루 분포된다는 특징을 가지고 있습니다.
- 따라서, 배열보다 빠르게 값을 찾을 수 있다는 장점을 가지고 있습니다.
해시테이블(HashTable)이란?
HashMap, HashSet
1. 정의
HashMap
Map 인터페이스의 구현체로, HashTable과 유사한 자료구조로 데이터를 저장한다.
HashSet
Set 인터페이스의 구현체로, 내부적으로 HashMap을 사용하기 때문에 HashTable과 유사한 자료구조로 데이터를 저장한다.
2. 데이터 저장 형태
HashMap
Key-Value 쌍 형태로 데이터를 저장하며, Key와 Value의 mapping을 유지하고 있다.
HashSet
객체 그 자체를 저장한다.
위에서 HashMap을 내부적으로 사용한다고 했는데,
Key 값으로는 삽입되는 객체 그 자체를, Value 값으로는 HashSet 내부 구현 코드에서 미리 선언해둔 dummy 객체를 사용한다.
3. 중복 허용 여부
HashMap
중복 Key 값을 허용하지 않지만, 중복 Value 값은 허용한다.
ex. {'a': 1, 'b': 1, 'c': 2}
HashSet
객체 자체를 데이터로 저장하기 때문에 중복을 허용하지 않는다.
ex. {'a', 'b', 'c'}
4. NULL 허용 여부
HashMap
(중복 Key 값을 허용하지 않기 때문에)
단 하나의 NULL 값을 Key 값으로 가질 수 있고, 여러 NULL 값을 Value 값으로 가질 수 있다.
HashSet
단 하나의 NULL 값을 가질 수 있다.
데이터의 유일함(Uniqueness)을 유지하기 위해 항상 HashMap이 HashSet보다 선호된다.
