[JAVA] SET(tree, hash)

■ Set : 집합이라는 뜻

 

고유한 특성으로만 모여있어야함
중복된 값이 있을 수 없음

- 데이터 중복을 허용하지 않는다
- 내부적인 중복체크
-  이미 존재하는 데이터를 또 다시 추가하면 false를 반환하고, 데이터는 추가되지 않는다.
-  인덱스 정보를 제공하지 X
-  list 와 비슷한 함수를 사용 가능하지만, 인덱스 정보가 필수로 필요한 set, get 함수는 사용 X
 

Set 인터페이스에 iterator 를 갖고있음
-  그래서 데이터를 접근하기 위해서 Iterator 객체를 사용해야한다.

 

Iterator it = hs1.iterator();

 

hasNext() : 다음 값이 있으면 true, 없으면 false
next() : 다음 값을 가져옴

 

데이터 개수만큼 반복하기
while(it.hasNext()){ // 다음 데이터가 있는지 확인
System.out.println(it.next()); // 다음 데이터 가져오기
}

 

Collection 유형의 객체들은 서로 다른 자료 구조로 쉽게 변경해서 사용할 수 있다.
-  다른 유형의 객체를 생성할 때 생성자에 해당 데이터를 넣어주면 된다.
-  List<Integer> intRndList = new ArrayList<Integer>(다른구조의변수이름);

 

---------------------------------------------------------------------------------------------------------------------------------------------

 

Tree 자료구조
: 하나의 데이터에 두개 이상의 데이터가 매달리는 것
작은 데이터는 왼쪽 큰 데이터는 오른쪽에 둔다
4
2 6
1 3 | 5 7

 

-  데이터 정렬만 잘 한다면 검색속도에 엄청난 장점이 있음

 

TreeSet
- TreeSet은 데이터 저장시에 자동정렬 기능이 들어가 있다.
-  HeadSet : 어떤 기준점보다 작은 수의 집합
-  headSet(기준값) : 기본적으로 '기준값'은 포함시키지 않는다.
-  headSet(기준값, 논리값) : '논리값'이 true이면 '기준값'을 포함시킨다.
-  TailSet : 어떤 기준점보다 큰 수의 집합
-  tailSet(기준값) : 기본적으로 '기준값'을 포함시킨다.
-  tailSet(기준값, 논리값) : 논리값이 false이면 기준값을 포함시키지 않는다.
-  SubSet : 기준값~ 기준값 사이의 값들의 집합
-  subSet(기준값1, 기준값2) : 기준값1 ~ 기준값2 사이의 값을 가져온다. ('기준값1' 포함, '기준값2' 미포함)
-  subSet(기준값1, 논리값1, 기준값2, 논리값2) : 각 기준값 포함 여부를 각 논리값으로 결정한다.

 

---------------------------------------------------------------------------------------------------------------------------------------------

 

해시함수(Hash function)

 

해시함수(Hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑해주는 함수이다.
해시함수에 의해 얻어지는 값은 해시값, 해시코드 등으로 부른다.

단점 : 비교적 메모리를 많이 잡아먹는다.

 

HshSet, HashMap, Hashtable과 같은 객체들을 사용할 경우
추가하는 객체가 서로 같은지를 비교하기 위해 equals()와 hashCode()를 사용한다.
그래서 객체가 서로 같은지 여부를 결정하려면 두 메서드를 적절하게 재정의 해주어야한다.

 

- equals() : 두 객체의 내용(값)이 같은지 비교하는 메서드
- hashCode() : 객체에 대한 해시코드값을 반환하는 메서드 => 해시테이블 생성시 사용됨

 

- equals() 메서드와 hashCode() 메서드 작성에 관련된 규칙(Convention)
1. 두 객체가 같으면 반드시 같은 hashCode를 가져야한다.
2. 두 객체가 같으면 equals()를 호출했을 때 true를 반환해야한다. 즉, 객체 a, b가 같다면 a.equals(b)와 b.equals(a) 둘 다 true이어야 한다.
3. 두 객체의 hashCode()가 같다고 해서 두 객체가 반드시 같은 객체는 아니다. 하지만, 두 객체가 같으면 반드시 hashCode()가 같아야한다.
4. equals()를 재정의해야 한다면 반드시 hashCode()도 재정의 해주어야 한다.
5. hashCode()는 기본적으로 Heap 메모리에 있는 각 객체에 대한 메모리 주소값을 기반으로 한 정수값을 반환한다. 그러므로 클래스에서 hashCode()메서드를 재정의 하지 않으면 절대로 두 객체가 같은 것으로 간주될 수 없다.