[Java] Hash Set

🔎Hash Set

Hash Set은 Java Collections Framework의 일부로, 중복되지 않는 요소를 저장하는 데 사용되는 데이터 구조이다.

Hash table

이 Hash Set은 Hash table을 사용하여 구현한다.
여기서 Hash table이란, 효율적인 검색과 삽입 연산을 위해 설계된 자료구조로, key-value 쌍의 데이터를 저장하는 데 사용된다.

작동 방식

Hash table에 데이터가 저장되는 과정은,key값을 Hash function에 input으로 넣으면 output으로 정수 형태의 Hash가 나오는데, 이 Hash는 배열의 capacity만큼 모듈러 연산을 거친 값을 인덱스 값으로 사용해서 적절한 위치에 데이터를 넣는다.

Hash table은 이렇게 데이터의 크기에 상관없이 데이터를 넣고 빼고 찾는 과정을 상수 시간 내에 처리할 수 있다는 점에서 효율적이다.

정리하자면, Hash table은 일반적으로 테이블의 크기에 상관없이 key를 통해 상수 시간에 빠르게 데이터에 접근 가능한 특징이 있다.
그리고 Hash Set은 바로 이 Hash table을 사용하여 구현하기 때문에 크기에 상관없이 데이터 조회가 빠르다는 특징이 있다.

충돌 처리

만약 해당 인덱스에 이미 다른 요소가 존재한다면 충돌이 발생한다.
이를 처리하기 위한 방법으로는 아직까지도 많은 연구가 이루어지고 있다고 한다.

알려진 방법으로는 chaining, Linear Probing, Resizing 등이 있다.

---

🔎Hash Set 주요 특징

위에서 살펴본 Hash table과 Hash Set의 특징을 모아보자면 아래와 같다.

• 중복 허용 안 함
  Hash Set은 중복된 요소를 허용하지 않는다. 즉, 동일한 요소를 추가하려고 하면 기존 요소가 유지되고 추가되지 않는다.

• 순서 없음
  Hash Set에 저장된 요소는 순서가 보장되지 않는다. 즉, 요소를 추가한 순서와는 관계 없이 저장된다. 따라서 인덱스를 통해 요소에 접근할 수 없다.

• null 값 허용
  Hash Set은 하나의 null 값을 허용한다. 여러 개의 null 값을 추가하려고 하면 하나만 저장된다.

• 빠른 성능
  Hash Set은 Hash table을 기반으로 하므로, 요소의 추가, 삭제, 검색 작업이 평균적으로 $O(1)$의 시간 복잡도를 가진다. 하지만 충돌이 발생할 경우 성능이 저하될 수 있다.

---

Hash Set 사용 예제

Set<String> sample = new HashSet<>();
sample.add("나루토");
sample.add("사스케");
sample.add("나루토");

System.out.println(sample.size()); // 2
System.out.println(sample.contains("나루토")); // true
System.out.println(sampel.contains("사쿠라")); // false

Hash Set 인스턴스를 하나 만들고, sample이라는 Hash Set 객체에 문자열을 하나씩 넣어본다.

"나루토"는 2번 삽입되었고, Hash Set은 중복을 허용하지 않기 때문에, size()함수를 호출했을 때 2가 출력되고, contains()함수를 통해 Hash Set 안에 "나루토"랑 "사쿠라"라는 문자열이 있는 지 확인해 보면, 각각 True와 False로 출력되는 것을 확인해볼 수 있다.

---

🖥️Reference
유튜브 채널 "쉬운코드" - hash set