[Java] HashSet

HashSet이란

• Set 인터페이스의 구현체
• 중복을 허용하지 않고, 순서를 보장하지 않는 집합 자료구조
• 내부적으로 HashMap을 이용하여 구현됨

HashSet의 내부 동작 원리

HashSet은 내부적으로 HashMap을 이용해서 동작한다. HashSet에 값을 추가하면 → 그 값이 HashMap의 key로 들어가는 형태.

• 해시 함수
  • 데이터를 넣을 때 해시 함수를 통해 해시 값을 계산 -> 이 해 시값을 이용해 데이터 저장 버킷(bucket) 위치 결정

set.add("apple");

//"apple"의 해시코드 계산 -> 특정 버킷에 저장

• 충돌 처리
  • 서로 다른 값이 같은 해시값 가질 가능성 -> 같은 버킷 안 연결 리스트( or 트리 구조)에 이어 저장
• 조회 속도 빠른 이유
  • 배열(int[]나 ArrayList)에서 contains(..) → 처음부터 끝까지 다 검사해야 하니까 O(n)
  • HashSet에서 contains(..) → 해시값으로 바로 버킷 위치를 찾고, 거기서만 비교 → 평균 O(1)

 

특징

1. 중복 불가

HashSet<Integer> set = new HashSet<>();
set.add(1);
set.add(1);
System.out.println(set); // [1]

2. 순서 없음

HashSet<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("cherry");
System.out.println(set); // [banana, cherry, apple] (순서 랜덤)

3.빠른 검색

set.contains("apple"); // true
set.contains("grape"); // false

 

배열이나 리스트에서 contains 사용시 평균 시간 복잡도 O(n) , 버켓 위치를 찾아 검색하기 때문에 O(1)로 훨씬 빠름

주요 메서드

 

• add(E e) : 원소 추가
• remove(E e) : 원소 제거
• contains(Object o) : 포함 여부 확인
• size() : 원소 개수
• isEmpty() : 비었는지 확인
• clear() : 전체 삭제

 

E : 타입을 의미 (제네릭) e : 그 타입의 변수 이름 (실제 값이 들어감)