HashSet이란?

개요

알고리즘을 공부를 위해 다시 한 번 정리해보고자 한다.

Set이란?

데이터 자료구조 중 하나로 특정한 값들을 저장하는 추상자료형(interface)이다.

Set은 비선형 구조이기 때문에 '순서'의 개념과 '인덱스'가 존재하지 않는다.

값들은 순서가 존재하지 않으며, 중복되지 않는다.

이는 수학에서 집합을 컴퓨터 구현한 것이다.

다른 모음(Collection)타입에서 특정원소를 검색하는 것이 주 업무인 반면, 집합은 대상 원소가 집합에 소속되어 있는지 여부를 검사한다.

 

Set의 특성

데이터를 비순차적으로 저장할 수 있는 순열 자료구조

삽입(insert)한 데이터가 순서대로 저장되지 않는다.

수정 가능하다.

중복해서 삽입이 불가능하다.(중복값이 들어오면 하나의 값만 저장한다.)

FastLookup이 필요할 때 주로 쓰임

 

FastLookup : 데이터 구조나 알고리즘에서 어떤 항목을 빠르게 찾을 수 있는 능력

 

HashSet이란?

Set인터페이스를 구현한 클래스 중 하나로, 해시 테이블을 기반으로한 데이터 구조이다.

Set의 성질을 그대로 상속받는다.

 

해시테이블 : 데이터를 저장하고 검색하는데 뛰어난 성능을 제공하는 자료구조

HashSet예시

public class Car {
	private final String name;

	public Car(String name) {
		this.name = name;
	}
    
	@Override
	public String toString() {
		return this.name;
	}
}
----------------------------------------------------------
public class Main {
    public static void main(String[] args) {
    	Set<Car> set = new HashSet<>();
    	
        Car car1 = new Car("car1");
        Car car2 = new Car("car2");
        Car car3 = new Car("car3");
        
        set.add(car1); //set에 추가
        set.add(car2);
        set.add(car3);
        
        set.add(car1); //중복값 추가
        set.add(car3); //중복값 추가
        
        System.out.println(set);
        
    }
}

결과값
[car3, car1, car2]

결과값을 보면 중복값을 줬던 car1, car2가 한번씩 들어간 걸 볼 수 있으며,

출력값이 car3 - car1 - car2 순서로 순차적으로 저장이 되지 않는다는 것을 확인할 수 있다.

Set의 중복제거 방법

만약 이미 명시된 요소가 없다면, 명시된 요소를 현재 set에 추가한다.

좀 더 구체적으로, 만약 해당 set이 Object.equals(e,e2)를 통해 e2 요소를 포함하지 않으면 명시된 e요소를 set에 추가한다.

만약 해당 Set이 이미 포함하고 있는 경우라면, 호출을 그만두고 set은 바뀌지 않으며, false를 리턴한다.

 

--추가

Set의 구현체 HashSet과 같은 hash를 사용하는 Collection(HashSet, HashMap, HashTable)은 논리적으로 같은지 비교할 때 위와 같은 과정을 거친다.
equals메서드를 실행하기 전에 HashCode로 먼저 같은지 확인한 후 equals를 실행하게 된다.

때문에 equals메서드를 재정의 하려면 hashCode메서드도 같이 재정의해야한다.

 

---

참고자료

https://tecoble.techcourse.co.kr/post/2020-07-29-equals-and-hashCode/

https://crazykim2.tistory.com/474

https://velog.io/@acacia__u/hashSet