HASH, HASH SET, HASH MAP 개념 및 차이점

자바에서 `Hash`, `HashSet`, `HashMap`은 데이터 저장과 검색을 효율적으로 처리하기 위해 해싱(Hashing)이라는 기법을 사용하는 자료구조입니다. 각 개념을 아래와 같이 정리할 수 있습니다.

---

 1. Hash

- 정의: 해시(Hash)는 데이터를 고유한 키로 매핑하는 해시 함수(Hash Function)를 사용해 데이터를 빠르게 검색하거나 저장하는 기법입니다.
- 해시 함수: 입력 값(데이터)을 일정한 길이의 고유한 해시 값(Hash Value)으로 변환하는 함수.
- 장점:
  - 데이터 검색 속도와 저장 효율성이 뛰어남 (보통 `O(1)` 시간복잡도).
- 단점:
  - 해시 충돌(Hash Collision)이 발생할 수 있음. (다른 입력값이 동일한 해시 값을 가질 때)
  - 메모리 사용량 증가 가능.

---

 2. HashSet

- 정의: `Set` 인터페이스를 구현한 클래스 중 하나로, 중복을 허용하지 않는 요소를 저장합니다. 내부적으로 `HashMap`을 사용하여 데이터를 관리합니다.
- 특징:
  1. 중복 불허: 동일한 요소는 한 번만 저장됨.
  2. 순서 비보장: 요소들이 저장된 순서를 유지하지 않음.
  3. 빠른 작업 속도: 추가, 삭제, 검색의 평균 시간복잡도는 `O(1)`.

- 구조: 내부적으로 `HashSet`은 `HashMap`을 사용하여 데이터를 저장하며, 저장된 값은 `HashMap`의 키로 사용되고, 값은 `PRESENT`라는 상수로 처리됩니다.

- 예제:

 import java.util.HashSet;

  public class Main {
      public static void main(String[] args) {
          HashSet<String> set = new HashSet<>();
          set.add("Apple");
          set.add("Banana");
          set.add("Apple");  // 중복, 추가되지 않음

          System.out.println(set);  // 출력: [Apple, Banana]
      }
  }

 

 

---

3. HashMap

- 정의: `Map` 인터페이스를 구현한 클래스 중 하나로, 키-값 쌍(Key-Value Pair) 형태로 데이터를 저장합니다.
- 특징:
  1. 키는 고유: 동일한 키를 중복하여 저장할 수 없음.
  2. 값은 중복 가능: 값은 중복 저장 가능.
  3. 순서 비보장: 키-값 쌍의 저장 순서를 유지하지 않음.
  4. Null 허용: 키로 하나의 `null` 값과 다수의 `null` 값을 허용.

- 구조: 
  - 내부적으로 배열 + 연결 리스트 + 트리(자바 8 이후) 구조를 사용.
  - 해시 충돌 발생 시 체이닝 방식으로 데이터를 관리하며, 충돌이 많아질 경우 연결 리스트가 트리 구조로 변경되어 성능 향상을 도모.

- 예제:

  import java.util.HashMap;

  public class Main {
      public static void main(String[] args) {
          HashMap<Integer, String> map = new HashMap<>();
          map.put(1, "Apple");
          map.put(2, "Banana");
          map.put(1, "Cherry");  // 키가 동일하면 값 덮어쓰기

          System.out.println(map);  // 출력: {1=Cherry, 2=Banana}
      }
  }

---

특성	HashSet	HashMap
저장 방식	단일 값 저장	키-값 쌍으로 저장
중복 허용 여부	값 중복 불허	키 중복 불허, 값 중복 가능
Null 허용 여부	하나의 'null' 값 허용 가능	하나의 'null' 키, 다수의 'null' 값 허용
사용 예시	고유한 데이터 저장	키를 기준으로 값을 저장 및 검색

---

4. 자바 8 이후 HashMap 내부 구조 변화

자바 8 이전에는 배열 + 연결 리스트 구조만 사용되었으나, 자바 8부터는 다음과 같은 변화가 있었습니다:
1. 트리화(Treeification):
   - 충돌이 잦아 연결 리스트의 길이가 일정 수준 이상 길어지면, 이를 트리 구조(BST)로 변환하여 검색 속도 향상.
2. 효율성 향상: 
   - 충돌이 적은 경우 `O(1)`.
   - 충돌이 많아도 연결 리스트 대신 트리를 사용하면 최악의 경우 시간복잡도는 `O(log n)`으로 유지.

---

 정리
- Hash: 데이터의 해싱 기법.
- HashSet: 중복을 허용하지 않는 데이터 집합.
- HashMap: 키-값 쌍으로 데이터를 저장하고 검색.