자료구조_검색 ⑥ 해싱 검색 - 해쉬셋 HashSet

 

 

[1] HashSet 특징

---

(1) HashSet 클래스 

 

• Set 인터페이스를 구현한 클래스와 멤버의 중복 여부를 체크하기 위해 인스턴스의 동일성을 확인해야 함
• 동일성 구현을 위해 필요에 따라 equals()와 hashCode()메서드를 재정의함

 

• 빠른 접근 속도 
• 중복 허용 안됨
• 순서 제공 안됨
• 데이터 저장방식이 HashTable 이용
• HashMap을 이용하여 구현된 형태이다
• 인덱스 위치를 통해 저장과 접근을 하는것이 아닌 key를 이용하고 싶을 경우 사용한다 
• 데이터의 크기가 예상되는 경우 사용한다
• 삽입 삭제가 빈번할경우 사용한다 

 

[2] HashSet 메소드 

---

(1) HashSet 선언하기 

import java.util.HashSet;

HashSet a = new HashSet();

HashSet a = new HashSet(Arrays.asList(1,2,3,4,5);

HashSet<Integer> a = new HashSet();

HashSet<String> set = new HashSet<>();

 

 

 

(2) HashSet 메소드

add(데이터)	데이터 넣기
	a.add(1); a,add("아름")
size()	집합 크기 반환
	a.size();
contains(데이터)	집합 안에 객체가 있다면 true 반환
	a.contains(2);
remove(데이터)	데이터 삭제
	a.remove(1);
retainAll()	교집합 데이터 반환
	a.retainAll(b); return a;
addAll()	합집합 데이터 반환
	a.addAll(b); return a;
removeAll()	차집합 데이터 반환
	a.removeAll(b); return a;
containsAll()	부분집합 ; a 집합안에 b 집합이 있을때 b집합은 a집합의 부분집합이면true 반환
	return a.containsAll(b);

 

[3] HashSet 예시

---

• 멤버 변수를 선언한다 
• 키(회원아이디) , 벨류 (회원이름)
• 키가 동일한경우 같은 멤버이므로 중복되지 않도록 hashCode()와 equals()를 재정의한다 

public class Member {
	
	private int memberId;        //회원 아이디
	private String memberName;   //회원 이름

	public Member(int memberId, String memberName){ //생성자
		this.memberId = memberId;
		this.memberName = memberName;
	}
	
	public int getMemberId() {  //
		return memberId;
	}
	public void setMemberId(int memberId) {
		this.memberId = memberId;
	}
	public String getMemberName() {
		return memberName;
	}
	public void setMemberName(String memberName) {
		this.memberName = memberName;
	}
	
	@Override
	public String toString(){   //toString 메소드 오버로딩
		return memberName + " 회원님의 아이디는 " + memberId + "입니다";
	}
    
    
    @Override
	public int hashCode() {
		return memberId;
	}

	@Override
	public boolean equals(Object obj) {
		if( obj instanceof Member){
			Member member = (Member)obj;
			if( this.memberId == member.memberId )
				return true;
			else 
				return false;
		}
		return false;
	}

}

 

멤버회원을 HashSet 자료구조를 이용하여 멤버를 추가하고 삭제한다 

public class MemberHashSet {
	private HashSet<Member> hashSet;

	public MemberHashSet(){
		hashSet = new HashSet<Member>();
	}
	
	public void addMember(Member member){
		hashSet.add(member);
	}
	
	public boolean removeMember(int memberId){

		Iterator<Member> ir = hashSet.iterator();
		
		while( ir.hasNext()){
			Member member = ir.next();
			int tempId = member.getMemberId();
			if( tempId == memberId){
				hashSet.remove(member);
				return true;
			}
		}
		
		System.out.println(memberId + "가 존재하지 않습니다");
		return false;
	}
	
	public void showAllMember(){
		for(Member member : hashSet){
			System.out.println(member);
		}
		System.out.println();
	}
}

실행클래스 

public class MemberHashSetTest {

	public static void main(String[] args) {

		MemberHashSet memberHashSet = new MemberHashSet();
		
		Member memberLee = new Member(1001, "이순신");
		Member memberKim = new Member(1002, "김유신");
		Member memberKang = new Member(1003, "강감찬");
		
		
		memberHashSet.addMember(memberLee);
		memberHashSet.addMember(memberKim);
		memberHashSet.addMember(memberKang);
		memberHashSet.showAllMember();
		
		Member memberHong = new Member(1003, "홍길동");  //1003 아이디 중복 
		memberHashSet.addMember(memberHong);
		memberHashSet.showAllMember();
	}
}

 

 

 

 

HashSet 을 이용하여 교집합/차집합/합집합 구하기 

---

HashSet 선언하기 

import java.util.HashSet;

HashSet set1 = new HashSet();

 

HashSet 값 넣기 ( 데이터가 중복이 안된다 ) 

 

HashSet set1 = new HashSet();

set1.add(1);   // [1]
set1.add(2);   // [1,2]

 

HashSet 값 지우기 

HashSet set1 = new HashSet();

set1.add(1);   // [1]
set1.add(2);   // [1,2]


set1.remove(o:1);   // [2]

 

HashSet 사이즈 크기 알아보기 

HashSet set1 = new HashSet();

set1.add(1);   // [1]
set1.add(2);   // [1,2]


return set1.size();    // 2

 

HashSet 안의 데이터 중에 2가 들어있는지 참/거짓 말하기 

HashSet set1 = new HashSet();

set1.add(1);   // [1]
set1.add(2);   // [1,2]


return set1.contains(2);  // true

 

 

 

HashSet 으로 교집합/차집합/합집합 구하기

---

HashSet 을 2개 만든다 

배열의 값을 각각 넣어준다 

---> 비교할 집합의 데이터를 만든것이다 

HashSet a = new HashSet(Arrays.asList(1,2,3,4,5));
HashSet b = new HashSet(Arrays.asList(2,4,6,8,10));

 

두 집합의 교집합 찾기 

HashSet a = new HashSet(Arrays.asList(1,2,3,4,5));
HashSet b = new HashSet(Arrays.asList(2,4,6,8,10));

a.retainAll(b)

return a;  // [2,4]

 

두 집합의 합집합 찾기 

HashSet a = new HashSet(Arrays.asList(1,2,3,4,5));
HashSet b = new HashSet(Arrays.asList(2,4,6,8,10));

a.addAll(b)

return a;  // [1,2,3,4,5,6,8,10]

 

두 집합의 차집합 찾기 

HashSet a = new HashSet(Arrays.asList(1,2,3,4,5));
HashSet b = new HashSet(Arrays.asList(2,4,6,8,10));

a.removeAll(b)

return a;  // [1,3,5]

 

 

 

 

HashSet으로 합의법칙 찾기

3의 배수가 될때  또는 4의 배수가 될때 

a,b를 리스트로 만들어서 arr 의 구성요소로 만들어줄거고

arr에 list의 값을 넣어준다 

 

arr에 중복되지 않은 (a,b)의 묶음이 리스트로 정리되어있어

배열의 크기가 곧 경우의 수 이다 

 

HashSet<ArrayList> hSet = new HashSet<>();

for(int a: dice1) {
	for(int b : dice2) {
    	if( (a+b) % 3 == 0 || (a+b) % 4 == 0 ) {
        	ArrayList arr = new ArrayList(Arrays.asList( a, b));
            arr.add(list);
        }
    }
}
return arr.size();