240403 Java - 컬렉션 프레임워크 3

컬렉션 프레임워크

Hash: 정보를 저장하거나 검색할 때 사용하는 자료 구조 -> Hash Table, Hash Map 

해시코드

• 해시는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖음
• 데이터 삽입, 삭제 시 기존 데이터를 밀어내거나 채우는 작업이 필요 없도록 특별한 알고리즘을 이용하여 데이터와 연관된 고유한 숫자(index)를 만들어 낸 뒤 저장 위치로 사용
• 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 삽입과 삭제 시 데이터의 이동이 없도록 만들어진 구조
• 해시가 내부적으로 사용하는 배열을 Hash Table이라고 하며 그 크기에 따라서 성능 차이가 많이 남
• 키-값 형식으로 값을 저장
• HashSet은 객체를 저장하기 전 먼저 객체의 hashCode() 메소드를 호출해서 해시 코드를 얻어낸 다음 저장되어 있는 객체들의 해시 코드와 비교하여 같은 해시 코드가 있다면 다시 equals() 메소드로 두 객체를 비교해서 true가 나오면 동일한 객체로 판단하고 중복 저장하지 않음
• 일반적으로 객체에 대해 hashCode()와 equals() 메소드를 재정의하여 특정 데이터를 보다 효율적으로 처리하도록 해줘야 함

 

해시 메소드

• 해시는 Hash Table을 이용하여 데이터를 저장
• 특별한 알고리즘을 이용하여 데이터의 고유한 숫자값을 만들어 인덱스로 사용하는데 알고리즘을 구현한 메소드를 Hash Method라고 하며 Hash Method에 의해 반환된 데이터 고유의 숫자값을 Hash Code라고 함
• Ojbect 클래스의 hashCode() 메소드를 이용하여 모든 객체의 Hash Code를 쉽게 구할 수 있음

 

알고리즘

• 계층 구조를 나타내는 자료 구
• 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘
• 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠름

 

이전 탐색의 동작 방식

• 정렬이 되어 있어야
• 리스트의 중간값을 찾음
• 중간값과 검색 값을 비교
• 값을 찾거나 간격이 비어있을 때까지만 반복

 

TreeSet

• Tree로 시작하는 클래스는 데이터를 추가한 결과를 출력하면 결과값이 정렬됨
• 출력 결과값을 정렬하는 클래스
• 정렬을 어떻게 지정하느냐에 따라 검색의 순서가 결정
• 클래스의 객체를 TreeSet 요소로 추가할 때 어떤 기준으로 노드를 비교하여 트리를 형성해야하는지를 구현해야함
• Comparable 인터페이스
  compareTO() 추상 메소드가 포함
  클래스에서 compareTo() 메소드를 오버라이드 시켜서 사용
  this객체와 전달받은 매개 변수를 비교(자신이 큰경우 양수(오름차순), 같은 경우 0, 자신이 작은 경우 음수(내림차순))
• Comparator 인터페이스
  전달되는 2개의 매개변수 비교

package test21;

import java.util.Comparator;

class Student implements Comparable<Student>{
	String name;
	int age;
	
	public Student(String name, int age) {
		this.name = name;
		this.age = age;
	}
	/*
	@Override
	public int compareTo(Student o) {
		
		//자기자신(this) 객체와 전달받은 매개변수(객체) 비교
		if(this.age > o.age) {
			return 1; //오름차순
		} else if(this.age == o.age) {
			return 0;
		} else {
			return -1;// 내림차순
		}
	}
	*/
	//==
	@Override
	public int compareTo(Student o) {
		return (this.age-o.age);
	}
	
	
}

class Student1 implements Comparator<Student1>{
	String name;
	int age;
	
	public Student1(String name, int age) {
		this.name = name;
		this.age = age;
	}
	
	//콜백 메소드 : 프로그래머가 작성하지만 시스템이나 자바 컬렉션 프레임워크가 호출하는 메소드
	@Override
	public int compare(Student1 o1, Student1 o2) {
		return o1.age-o2.age;
	}
	
}


public class TreeSetTest1 {

	public static void main(String[] args) {

		Student a = new Student("ㄱ", 20);
		Student b = new Student("ㄱ", 20);
		Student c = new Student("ㄱ", 21);
		Student d = new Student("ㄱ", 19);
		
		int result = a.compareTo(b);
		System.out.println(result);
		
		result = a.compareTo(c);
		System.out.println(result);
		
		result = a.compareTo(d);
		System.out.println(result);
		
		System.out.println();
		
		Student1 a1 = new Student1("a", 18);
		Student1 b1 = new Student1("a", 18);
		Student1 c1 = new Student1("a", 17);
		Student1 d1 = new Student1("a", 19);
		
		int result1 = a1.compare(a1, b1);
		System.out.println(result1);
		
		result1 = a1.compare(a1, c1);
		System.out.println(result1);
		
		result1 = a1.compare(a1, d1);
		System.out.println(result1);
		
		result1 = a1.compare(c1, d1);
		System.out.println(result1);
	}

}

 

package test21;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

//Tree로 시작하는 클래스는 데이터를 추가한 후 결과를 출력하면 결과값이 정렬
//데이터의 중복은 허용하지 않고 츨력 결과값을 정렬하는 클래스
//정렬 방식을 어떻게 지정하느냐에 따라 오름차순, 내림차순으로 결정됨

//Comparable 인터페이스와 Comparator 인터페이스 -> 자신의 객체와 전달 받은 객체를 비교
//Comparable 인터페이스 > Comparator 인터페이스 사용빈도는 Comparable인터페이스를 더 많이 사용함
//Comparator 인터페이스 : Comparable 인터페이스가 이미 구현되어 있는 경우 사용. 전달되는 매개변수 2개를 비교. 생성자에 Comparator 인터페이스를 구현한 객체를 매개변수로 전달

//콜백(callback) 메소드
//객체가 TreeSet에 요소를 추가할 때 호출
class Descending implements Comparator<String>{

	@Override
	public int compare(String o1, String o2) {
		return o1.compareTo(o2)*-1; //음수로 만들어 내림차순
	}
	
}

class Descending1 implements Comparable<Descending1>{
	String name;
	int age;
	
	public Descending1(String name, int age) {
		this.name = name;
		this.age = age;
	}

	@Override
	public int compareTo(Descending1 o) {
		return this.age-o.age;
	}

	@Override
	public String toString() {
		return "this.name = " + this.name + ", this.age = " + this.age;
	}
	
}

public class TreeSetTest2{
	
	public static void main(String[] args) {
		//String 클래스는 Comparable 인터페이스를 이미 구현해놓음 -> 기본적으로 오름차순 정렬되어 있음
		TreeSet<String> set = new TreeSet<String>();
//		Set<String> set = new TreeSet<String>();
		
		set.add("A");
		set.add("C");
		set.add("D");
		set.add("B");
		
		System.out.println(set);
		System.out.println(set.descendingSet());
		
		System.out.println();
		
		//내림차순 정렬
		//TreeSet 생성자에 Comparator 인터페이스를 구현한 객체를 매개변수로 전달
		TreeSet<String> treeSet = new TreeSet<String>(new Descending());
		treeSet.add("D");
		treeSet.add("B");
		treeSet.add("A");
		treeSet.add("C");
		
		System.out.println(treeSet);
		
		System.out.println();
		
		TreeSet<Descending1> treeSet1 = new TreeSet<Descending1>();
		treeSet1.add(new Descending1("K", 18));
		treeSet1.add(new Descending1("K", 19));
		treeSet1.add(new Descending1("K", 18));
		treeSet1.add(new Descending1("K", 17));
		
		System.out.println(treeSet1);
		
		
	}



}