[자료구조] 01. hash, hashSet 중복 제거

Hash란?

어떠한 데이터를 어떠한 알고리즘에 의해 일정한 길이의 문자로 바꿈. 한 글자만 바뀌어도 연산의 결과는 전혀 달라짐. 리눅스 암호화 과정에서 ID와 Password를 받을 때에도 해쉬화 된 값으로 비교한다. 해쉬를 가지고 원래의 데이터를 복원하기란 어렵기 때문이다.

또한 검색 속도가 가장 빠른 구조인데, 데이터 저장시 해쉬 값으로 정렬되어 검색할 때 해쉬 값으로 한번에 데이터의 위치를 찾을 수 있기 때문이다. Database에서도 검색시 hash 알고리즘을 사용한다.(해쉬는 중복이 불가능 하지만, 동일한 해쉬가 생성될 경우 링크드 리스트를 사용해 적재한다. )

HashSet 중복제거

hashSet은 hash 알고리즘을 사용한 자료구조이다. hash는 기본적으로 중복이 불가능한데, 같은 값인지가를 판단하려면 아래 2가지 조건 모두를 만족해야 한다.

1) Object Class로부터 상속받은 hashCode() 매서드의 해시값을 비교

public int hashCode() {
	return num;
}

2) Object Class로부터 상속받은 equals() 매서드의 반환값을 비교

public boolean equals(Object obj) {
	SimpleNumber comp = (SimpleNumber)obj;
	if(comp.num==num)
		return true;
	else
		return false;
}

그러나 아래 코드의 경우, 내용물은 같아도 같은 객체 내에서 선언된 같은 hashcode를 가진 값이기 때문에 중복값으로 판단하게 된다. 따라서 위의 두 가지 조건을 적용해 커스터마이징 해야한다.

HashSet<SimpleNumber> hSet = new HashSet<SimpleNumber>();
hSet.add(new SimpleNumber(10));
hSet.add(new SimpleNumber(20));
hSet.add(new SimpleNumber(20));
System.out.println("저장된 데이터 수: "+hSet.size());
Iterator<SimpleNumber> itr = hSet.iterator();
while(itr.hasNext())
	System.out.println(itr.next());