on
Java Ch 11 Collection Framework
Java Ch 11 Collection Framework
선생님! 예제들 보면 메서드 만드실 때 public이 붙어 있는데 특별한 이유가 있을까요??
(default)만 해도 가져다 사용하는데는 문제 없어보이는데, public이 붙어야 하는(혹은 붙이면 좋은) 이유가 있는지 궁금합니다!
=> 메서드는 내부에서만 사용되는게 아니면 public입니다
11장 컬렉션 프레임웍(객체 지향 다음으로 중요. 여러번 반복, 빠르게, 전체적으로 중요)
++ 실습을 통해 어떻게 쓰고, 언제 쓰는지를 파악(이를 통해 원리 이해)
● ch 11-1 컬렉션 프레임웍
· 컬렉션(collection)
- 여러 객체(데이터)를 모아놓은 것
· 프레임웍(framework) vs Library: 기능만 쓰는
- 표준화, 정형화된 체계적인 프로그래밍 방식
// 정해진대로만 하면 되니 생산성, 유지보수(다른 사람이 짜도 수정 편리) 용이
· 컬렉션 프레임웍
- 컬렉션 ( 다수의 객체 ) 를 다루기 위한 표준화된 프로그래밍 방식
- 컬렉션을 쉽고 편리하게 다룰 수 있는(저장, 삭제, 검색, 정렬 등) 다양한 클래스 제공
java.util 패키지에 포함. JDK1.2부터 제공
컬렉션 클래스: 다수의 데이터를 저장할 수 있는 클래스 ex) Vecter, ArrayList, Hashset
· 컬렉션 프레임웍의 핵심 인터페이스
다루려는 데이터의 종류를 세 가지로 분류하면, List, Set, Map 이다.
=> 목적에 따라 인터페이스를 고르면 된다.
● ch 11-3 Collection, List, Set, Map
· collection 인터페이스의 메서드 // List와 Set의 두 인터페이스의 공통 부분이 Collection
보통 추가, 검색, 삭제
List와 Set 인터페이스가 공동으로 갖고 있는 것 이다.
· List 인터페이스
ArrayList와 LinkedList가 핵심. Vector는 ArrayList의 old.
· Set인터페이스
HashSet와 TreeSet가 핵심
· Map 인터페이스(Key, Value)
HashMap과 TreeMap이 핵심. //순서가 필요하면 LinkedHashMap을 사용
키와 값 한 쌍을 entry라고 한다.
Collection Values의 경우, Collection타입으로 반환. 이는 순서, 중복 O,X 모두 허용한다는 뜻
● Ch 11-7 ArrayList
· ArrayList // 뒤에 List가 붙은 것은 List 인터페이스를 구현했다는 것.
ArrayList는 기존의 Vector를 개선한 것으로 구현 원리와 기능적으로 동일(다만, ArrayList는 동기화 처리x)
List 인터페이스를 구현하므로, 저장순서가 유지되고 중복 허용
데이터(객체)의 저장공간으로 배열을 사용(배열기반) => 객체를 담기위한 배열로 Object를 사용하기에 모든 종류의 객체 저장 가능(다형성)
· ArrayList의 메서드
생성자
// (collection c) 매개변수로 컬렉션을 주면 그 컬렉션에 저장되어있는 요소들을 저장하는
// initialCapacity 배열의 길이 지정해준다(넉넉하게 설정해줄 것)
추가
// int index는 어디에 저장할지 정해주는 것
삭제
// int index 특정 위치 삭제
검색
// int indexOf() 객체를 정순서로 검색. int lastIndexOf() 객체를 거꾸로 검색
반환
// Object[] toArray() 는 ArrayList의 객체 배열을 반환
// int size() 저장된 객체의 개수 반환
· EX 11_1 예제
ArrayList에는 객체만 저장 가능
autoboxing에 의해 기본형이 참조형으로 자동변환
ex) list1.add(5) => list1.add(new Integer(5)); (컴파일러가 자동적으로 이렇게 변환한다) 원래는 이렇게 써야하는 것!!
.subList(a,b); // a와 b 사이에서 a는 포함, b는 포함하지않는 index 배열 추출( 읽기 전용 )
ex) ArrayList list2 = new ArrayList(list1.subList(1,4)); 는 ArrayList(Collection C)의 예시다.
=> 풀어쓰면, List sub = list1.subList(1,4); ArrayList list2 = new arrayList(sub); 와 같다.
정렬: Collections.sort(list1); // 오름차순 정렬 //Collection은 인터페이스, Collections는 util 클래스
포함?: list1.contansAll(list2); // list1이 list2의 모든 요소를 포함하고 있는가? //list1, list2 모두 배열
추가: list2.add(3, “a”); 같은 것은 중간에 집어넣는 것이기에 자리 이동이 필요 // .set(3.“aa”)은 교체
## 배열에서 int 나 string 이나 출력은 같게 나온다 . 다만, indexOf 같은 걸 하게되면 다르다.
삭제: .remove(index)를 해서 위치에 해당하는 값을 삭제할 수도 있고, .remove(new Integer(1));을 해서 해당하는 값을 삭제할 수도 있다.
// 주의: list1.remove(1); 은 1을 삭제하는 것이 아니라 인덱스가 1 인 객체를 삭제 하는 것이기에 해당하는 값의 타입까지 꼭 !!
// list1.remove(new Integer(1)); 에서 new Integer(1)은 새로운 객체를 만드는 거 아닌가요? 새로운 객체를 만들고 삭제하는 건가요? 이게 어떻게 list1에 이미 있는 값을 삭제하는 게 되는 건지 궁금합니다.
=> 같은걸 삭제하는건데. Integer는 equals가 오버라이딩 되어 있어서 같은 값이면 같은 객체로 보기 때문에 삭제 되는 겁니다.
# for문을 반대로 실행 // for (int I = list2.size()-1; i>=0; I--){ } 을 하면 큰 I부터 대입
if (list1.contanis(list2.get(0)) {list2.remove(i)}; // list2에서 list1에 포함된 객체들을 삭제한다.
### [0,1,2,3,4] 에서 0,1,2,3,4 를 데이터 , 객체 라고 하는구나!!! (무엇이든 담을 수 있기에 객체라고도)
· Ch 11-10 ArrayList에 저장된 객체의 삭제과정
삭제할 때, 한 칸씩 위로 옮기고(배열의 복사), 빈 공간은 null로, 그리고 size도 변경
삽입할 때는 한 칸씩 밑으로 내리고, size 증가(반대로 하는 것이다)
마지막 데이터 삭제 및 삽입 시에는 1의 과정(배열의 복사)가 필요 없다.
· ch 11-11 Java ApI 소스 보기- /j아 설치경로/src.zip 에 있는 java에 있는 util에 클래스 소스들을 볼 수 있다. ex) vector클래스 등
이클립스에서는 클래스 우클릭 open declartion을 클릭. 못 찾았다고하면 Attach Source하고 jdk설치경로 src.zip을 누르면 된다.
● ch 11-12~14 LinkedList (ArrayList와 비교)
· 배열의 장단점. ex) 박스 안에 담긴 상자들이라고 생각.
장점: 배열은 구조가 간단하고 데이터를 읽는데 걸리는 시간(접근시간 짧다)
// 배열은 각 요소가 연속적. 빈 공간 x
// 첫 번째 요소와 마지막 요소를 읽는 시간이 같다.
// 주소를 구하는 방법: 배열의 주소+ 배열 요소 크기(4 byte 등) x index
단점 1. 크기 변경 불가(실행 중에)
// 크기를 변경해야하는 경우 새로운 배열을 생성 후 데이터 복사하고 참조변경해야함.
// 크기 변경을 피하기위해 충분히 큰 배열을 생성하면, 메모리가 낭비.
단점 2. 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
// 데이터 추가, 삭제를 위해 다른 데이터를 옮겨야하기에
// 그러나 순차적인 데이터 추가, 삭제(끝에서 추가, 삭제)는 빠르다.
· LinkedList – 배열의 단점을 보완하기위해 나온 것 ex) 기차들이 연결되어있는 것.
배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(link) // 다음에 있는 것이 무엇인지 알 수 없다.
- 장점: 변경에 유리. 추가나 삭제할 때, 그냥 중간에 비집고 들어가면 된다.
// node는 다음 node로 갈 주소와 데이터를 묶는 것이다.
// 참조변경이란 줄을 연결하는 것을 말한다.
- 단점: LinkedList는 데이터 접근성이 나쁘다. 배열은 연속적이기에 한번에 아무데나 이동할 수 있으나, LinkedList는 자기 다음 node밖에 모르기에 징검다리처럼 이동해야한다. 또한, 이전 요소로 갈 수 없다.
=> 이를 해결하기위해 이중 연결 리스트가 나왔다. node에 이전과 다음 node 주소, 데이터를 갖는다. 앞뒤로 자유자재 움직일 수 있게! (접근성 향상 but 여전히 한번에 건너 뛰는 건 불가)
=> 이중 원형 연결리스트: 맨 처음과 마지막을 연결해준다. ex) 티비 채널 1-> 채널 99로
// 여전히 배열보다는 접근성이 나쁘다.
· ArrayList vs LinkedList – 성능 비교 (소요시간 측정)
자료 구조에서 ArrayList는 배열기반(연속), LinkedList는 연결기반(불연속)이라고 한다.
● ch 11-15~18 Stack과 Queue
· 스택: LIFO(Last in First out) 구조, 마지막에 저장된 것을 제일 먼저 꺼내게 된다. 저장(push)와 추출(pop)의 순서가 반대다. 밑이 막힌 상자 => 배열이 적합(순차적 추가, 순차적 삭제(뒤에서부터..))
· 큐: FIFO 쿠조, 제일 먼저 저장(offer), 제일 먼저 추출(poll). 줄 서기와 같다. => LinkedList가 적합(삭제를 처음부터 하기에)
· 스택과 큐의 메서드
메서드를 사용하고 싶다면, Stack st = new Stack();처럼 객체를 생성하면 된다.
peek는 꺼내는 게 아니라 반환만 하는 것. search는 위에서부터 1,2,3 이다. (2가 1, 1이 2, 0이 3의 위치에 있는 것)
자바에서 Queue는 인터페이스로 정의되어있기에 객체를 생성할 수 없다. Stack은 클래스여서 가능.
예외발생하면 try-catch문을, 예외발생 x면 반환되는 값을 if문을 활용하여 처리. peek는 삭제없이 그냥 읽어오는 것
· 인터페이스를 구현한 클래스 찾기(queue 메서드를 활용할 수 있는 두 가지 방법 중 하나. 다른 하나는 queue 직접 구현)
Java Api에서 찾은 queue // All Known Implementing Class는 queue를 구현한 클래스 목록이다.
LinkedList가 적합하다고 했으니, Queue q = new LinkedList(); 로 선언하면 된다. 물론, queue 대신 LinkedList도 가능하나, Queue라는 리모컨은 구현한 클래스들의 공통부분만을 사용하는 것이기에 이후에 다른 클래스들로 바꿔도 문제 발생 x의 이점. (즉, 새로운 클래스가 바뀔 때 이미 LinkedList 메서드들을 사용했어도 Queue 공통 부분에 해당하는 메서드들은 바꿔주지않아도 문제x)
● ch 11-19~21 Stack 과 Queue 의 활용
· 스택의 활용 예- 수식 계산, 수식괄호 검사, 웹브라우저의 뒤로/앞으로
· 큐의 활용 예 – 최근 사용문서, 인쇄작업 대기목록, 버퍼(buffer)
· EX 11_3
- 수식 괄호검사 예제: ( 가 있으면 Stack에 push, ) 가 나오면 pop을 해준다. 그래서 stack이 비어있으면 “괄호가 일치하다” + (가 더 있으면 stack이 비어있지않아서, )가 더 있으면 예외 발생
· EX 11_4 최근 5개의 명렁어 이력 검색
공백없애주기 trim + 공백인 아닌 경우에만
If (!“”.equals(input)) 은 if(input! = null && !input.equals(“”))를 줄인 것과 같다. 머리를 쓴 것이다.
// 잘 이해가....
해당 타입이 갖고 있는 메서드를 확인하려면 open declartion 하고 ctrl+o을 하면 된다.
## 팁: for문에서 list.size같은 것을 계속 반복해서 호출하는 것은 비효율적. 그래서 final int SIZE = list.size(); 하고 SIZE를 대신 써야한다.
// listliterator를 굳이 쓰지 않아도 된다.
● ch 11-22~24 Iterator, Enumeration, Map과 iterator
· Iterator(new), ListIterator, Enumeration(old)
컬렉션에 저장된 데이터를 접근(읽어오기)하는데 사용되는 인터페이스
boolean hasNext()로 확인하고, Object next()로 다음 요소 읽어온다.
ListIterator는 Iterator의 접근성을 향상시킨 것(단방향이 아니라 양방향. 다음, 이전 요소 접근)
· Iterator
- 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것(컬렉션마다 List, Set, Map 등 읽는 방식이 달라서) ==> Iterator를 쓰면 확인, 읽기 메서드만 쓰면 된다.
ex) List를 쓰다가 Set으로 바꿨으면 저장, 읽어오는 코드를 바꿔야하는 데 Iterator를 쓰면 클래스가 변경되어도 사용법을 따로이할 필요가 없다.
컬렉션에 Iterator()를 호출해서 Iterator를 구현한 객체를 얻어서 사용
=> iterator메서드는 Collection 인터페이스에 정의된 것이기에 List, Set의 경우 원래 가지고 있다.
// ArrayList를 List 타입으로 만들고, list에 있는 iterator 메소드를 호출하여 Iterator 객체 형성
Ex 11_5
// iterator 는 1 회용이라 다 쓰고나면 ( 다 읽어오면 ) 다시 객체를 생성해야한다 .
while (it.hasNext()) { Object obj = it.next(); sop(obj); } for(int I = 0; i 변경을 최소화하는 코드다.
· Collection을 참조변수 타입으로 해놓으면 장점. 코드를 검토할 필요가 없다.
// 처음부터 TreeSet, HashSet 타입을 참조변수 타입으로 설정하면 변경 시, 해당 타입에 없는 메서드를 쓰지않았는지 검토해야만 한다.
· ch 11-24 Map과 Iterator
Map에는 Iterator()가 없다. Collection의 자손이 아니기에
=> keySet(), entrySet() [set으로 반환], values() [collection으로 반환] 를 호출해야한다.
● Ch 11-25~29 Arrays
· Arrays – 배열을 다루기 편리한 메서드(static) 제공
배열의 출력- toString() // “[1,2,3,4,5]”로 출력. // 오버로딩되어있어서 모든 타입을 넣을 수 있다.
2. 배열의 복사 – copyOf(), copyOfRange()
copyOf(배열, 개수) // 개수만큼 새로운 배열을 복사해서 만들어준다. //넘치는 부분은 0으로 채운다.
copyOfRange(배열, 시작, 끝[포함x]) // 범위만큼 새로운 배열을 복사해서 만들어준다.
3. 배열 채우기 – fill(), setAll()
Arrays.fll(arr, 9); // 모든 요소를 전부 9로 채운다. // 특정 값을 채운다.
Arrays.setAll(arr, (i) -> (int)(Math.random()*5)+1); //setAll은 fill와 비슷하나 특정 값 대신 람다식
람다식: (i) -> (int)(Math.random()*5)+1
4. 배열의 정렬과 검색- sort(), binarySearch()
binarySearch()는 이진 탐색(정렬된 배열에만 가능) 그래서 Arrays.sort(arr);처럼 배열을 먼저 정렬해주고 실행해야한다. 그리고 (arr, 2)를 넣으면 arr배열에서 2 값이 어디있는지 index 반환
· 순차 검색 vs 이진 검색(=이분 검색)
- 순차적으로 찾는 것(맨 앞에서부터) 정렬이 필요없지만 찾는 데 시간 걸림.
- 정렬되고나서 반을 계속 잘라가며 찾기. 찾는 데 시간 짧으나 정렬이 필요. (정렬 속도가 관건)
5. 다차원 배열의 출력- deepToString() // 다차원 배열인 경우 이를 사용해야만 한다.
ex) int [][] arr2D = {{11, 12}. {21, 22}}; 이라면, Arrays.deepToString(arr2D)을 사용
6. 다차원 배열의 비교(내용 비교) – deepEquals() //equals()를 쓰면 false로 나온다.
7. 배열을 List로 변환 – asList(Object ... a) // Object이기에 가변(갯수 정함x) 매개변수 // 배열이 매개변수
// List list는 읽기 전용이기에 추가하려면 예외 발생 --> new ArrayList를 만들어줘서...
8. 람다와 스트림(14장) 관련- parallelXXX(), spliterator(), stream()
· 예제 EX 11_6
ch 11-28 향상된 for문
// 향상된 for문은 I를 배열의 각 요소로 설정.
// char [] graph = new char[i]; 는 I 크기의 char 배열을 만든다는 소리다.
// String -> char [] (tocharArray() 사용) // char[] -> String (String(char[]) 사용
// char 배열을 new String(배열)로 하면 괄호와 ‘’ 없이 그냥 문자열처럼 출력 abcde
// Arrays.toString(배열)을 하면 [a, b, c, d, e] 로 출력된다. // [ ] 으로 바뀌고, ‘’없어진다.
// 배열은 {‘a’, ‘b’, ‘c’, ‘d’, ‘e’ } 형태이다.
● Ch 11-30~33 Comparator와 Comparable
· 객체 정렬에 필요한 메서드(정렬기준 제공)을 정의한 인터페이스
Comparable: 기본 정렬기준을 구현하는데 사용, compareTo 메소드 사용
Comparator: 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용. compare() 메소드 사용
## 정렬sort() : 두 대상을 비교하고 자리 바꿈을 반복한다는 의미이다. 정렬할 때 대상 , 기준 필요!
## 정렬기준: 오름차순, 내림차순 등 여러 기준
- compare(), compareTo() : 두 객체의 비교 결과 반환, 같으면 0 오른쪽이 크면 -, 왼쪽이 크면 +
ch 11-30 Integer 클래스에 구현된 comparble
// 주어진 객체를 자신과 비교.
· Ex 11_7
// Arrays.sort() 에 배열만 있는 경우. 정렬에는 대상과 기준 둘 다 필요하지만, 객체 배열에 저장된 객체 타입이 구현한 Comparable(기본 정렬기준)에 의해 정렬된다.
ex) Integer, String [] 등이 이미 Comparable을 구현하고 있어서..
// 기본 정렬기준에서 대문자가 먼저고, 소문자가 그 다음이다. // compareTo 메서드
// Descending으로 Comparator를 구현해주고, 두 객체를 Comparable 타입으로 형변환. 그리고 기본정렬기준을 활용하고 –1을 곱해서 역순으로 만든다. 이게 싫으면 두 객체 순서 바꿔서
· ch 11-32 Integer 와 Comparable
// 정렬에서 두 대상 비교와 자리바꿈을 반복하는 것은 불변하니, 정렬 기준 제공과 같은 가변만 제공해주면 되는 것이다.
// return문에 삼항연산자를 쓰는 이유는 연산보다 성능이 빠르기에
// o1.compareTo(o2)를 쓰면 o1의 값은 this.value;, o2의 값은 anotherInteger.value;에 해당하는 것이다.
static void sort(int [] int Arr) { for(int I = 0; i intArr[j+1] { tmp = intArr[j]; intArr[j] = intArr{j+1}; intArr[j+1] = tmp; } } } } // integer에서 정렬 관련하여 두 대상 비교와 자리 바꿈을 반복하는 코드다. 버블정렬이라 하며, 불변하는 코드라고 생각하면 된다. (Integer가 comparable을 구현한 코드에 있다)
● Ch 11-34 HashSet- 순서 , 중복 x
· HashSet(일반적인 Set의 특성을 가진 클래스)
- Set인터페이스를 구현한 대표적인 컬렉션 클래스
- 순서를 유지하려면, LinkedHashSet 클래스를 사용하면된다.
· TreeSet
- 범위 검색(from~to)과 정렬에 유리한 컬렉션 클래스
- HashSet보다 데이터 추가, 삭제에 시간이 더 걸림.
· HashSet - 주요 메서드
## Collection 클래스들은 공간이 부족하면 스스로 공간을 늘린다. 보통 두 배정도
// float loadFactor는 언제 2배를 늘릴지(0.8이라 적으면, 80% 찼을 때란 의미)
// HashSet(Colletion c) - 생성자를 가지고 있다. 지정된 클래스에 모든 Collection 객체를 저장.
// boolean containsAll(Collection c) : Set이 Collection에 담긴 여러 객체를 모두 포함하는가?
// add, addAll(합집합), remove, removeAll(교집합), retainAll(차집합), clear(모두삭제)
- Set은 순서가 없기 때문에 정렬 불가 -> 리스트로 형변환하여 Collection.sort를 활용하여 정렬
ex) List list = new LinkedList(set); // LinkedList(Collection c) 다형성!! Collections.sort(list); sop(list);
## sop(set.add(objArr[i]))처럼 set의 특성으로 추가가 되고 안 되고가 있으면 true/false 반환된다.
· Hashset - 예제 3
- HashSet은 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인한다. (중복을 허용하지않는 특성)
- boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출
but equals와 hashCode()가 오버라이딩되어 있어야함. 안 그러면 위 비교작업이 제대로 작동하지 않음
ch 11-37 hashset 오버라이딩 필수(확실한 이해가 필요)
// 우리가 만든 클래스를 HashSet에 저장하려면 equals(), hashCode() 모두 오버라이딩되어있어야!
// equal()는 iv를 비교하게, hashCode는 return Object.hash(iv 전부);로 바꿔준다.
=> 객체를 구분하는 것이 iv이기 때문에
// Person tmp = (Person) obj;를 하는 이유는 매개변수를 Person 타입으로 바꿔줘서 name과 age를 비교할 수 있도록... Object는 조상 객체이기에 모든 매개변수 받을 수 있다.
ch 11-37 hashset 오버라이딩 안하면 발생하는 결과
// 오버라이딩이 안 되면 HashSet의 특성인 중복x가 작동x
// Source에서 hashCode()와 equals() generate를 해주고(iv 선택), 일부 수정하면 된다.
=> 수정할 때, 바로 위에 있는 코드들을 작성하면 된다.
· 두 배열 간의 교집합, 합집합, 차집합
- HashSet타입의 교집합 선언 및 배열 생성
- B 배열에서
Iterator it = setB.iterator(); 하고 while(it.hasNext()){ Object tmp = it.next(); //Object tmp를 한 이유는 배열에 뭐든 다 들어갈 수 있으니까 타입을 단정지을 수 없어서 if(setA.contains(tmp)) setKyo.add(tmp); //교집합 배열에 교집합 add } // 교집합의 예시 // 이걸 간단히 한다면, setA.retainAll(setB) 공통된 요소만 남기고 삭제
// 차집합은 A를 읽었는데, B에 해당하는 것이 없으면 추가 =>간단히하면, setA.removeAll(setB)
// 합집합은 A와 B를 각각 읽고 추가하기만 하면 된다. Set의 특성인 중복으로 인해 알아서 합집합.
=> 간단히하면, setA.addAll(setB)
● Ch 11-39~41 TreeSet
· TreeSet - 범위 탐색, 정렬 => HashSet과 달리, 정렬을 따로 해줄 필요가 없다.
- 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리.
- 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음. root-A-B와 C
- 각 요소(node)가 나무 형태로 연결(LinkedList의 변형) // 동그라미 하나가 TreeNode
· 이진 탐색 트리 => TreeSet은 이진 탐색 트리로 되어있는 것!
- 부모다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장(이진 트리의 한 종류) //이진트리는 이러한 조건 x
- 데이터가 많아질수록 추가, 삭제에 시간 더 걸림(비교횟수 증가)
ch 11-40 이진탐색트리
부모 노드 왼쪽, 오른쪽 객체 주소가 TreeNode left, right에 해당하는 것이다.
· TreeSet- 데이터 저장과정 boolean add(Object o) //Object o: 저장할 객체 //중복 x
- hashset은 add(Object o)를 호출하면, equals와 hashcode()를 호출해서 비교
=> TreeSet은 compareTo()를 호출해서 비교
ch 11-41 TreeSet이 저장되는과정
· Ch 11-42 TreeSet- 주요 생성자와 메서드 //Collection 공통 메서드는 빼구
- add()를 하면 비교하면서 저장하는데, 비교기준이 필요하다. 주어지지않으면, comparable(기본 비교기준) 적용
## 꿀팁: 구현해주려고 할 때, 구현해야할 메서드를 자동으로 추가가능!
ex) class TextComp implements Comparator를 치면 Add unimplemented methods가 나온다.
=> 비교 기준 클래스를 만들어주고나서 Set set = new TreeSet(); ()안에 new 비교기준클래스를 던져주기. 비교기준 return 문에 0이라고 되어있으면 계속해서 같은 것이라 인식.
===> 이렇게 TreeSet() 안에 비교기준 클래스를 던져주던가 아니면 저장하려는 객체 클래스가 comparable 을 구현한 것 이어야한다. 어디서 제공하든 비교기준 필요 => Integer,String 등은 문제없네!
- set,subset(from, to); ("b", "d") 라면 b와 d 사이에 첫글자로 시작하는 데이터를 추출 //범위검색 유리
- set.headSet(50), set.tailSet(50) 50보다 작은 값/ 50보다 큰 값(50포함) 추출
=> 이진 탐색 트리에서 보면 50의 왼쪽가지 아래, 50의 왼쪽가지 아래 이외의 값들로 나뉜다.
## 트리 순회
- 이진 트리의 모든 노드를 한번씩 읽는 거슬 트리 순회라고 한다.
// 전위순회(preorder): 부모 먼저 읽고 자식 읽기 //후위순회(Postorder): 부모 나주에 읽기//중위 순회(inorder): 부모를 가운데에 읽기 // 레벨 순회는 각 층(레벨)별로 읽는 것
// 중위 순회하면 오름차순으로 정렬된다. !! // 자식부모자식자식부모자식 하면 오름차순이다.
● Ch 11-46 HashMap
· HashMap과 Hashtable – 순서 x, 중복(키 x, 값 o) ex) 비밀번호
Map 인터페이스 구현. 데이터를 키와 값의 쌍으로 저장
HashMap(동기화x)은 Hashtable(동기화o)의 신 버전.
Map 인터페이스를 구현한 대표적인 컬렉션 클래스
--> 순서를 유지하려면, LinkedHashMap클래스 사용
TreeMap (TreeSet 속성)
범위 검색과 정렬에 유리한 컬렉션 클래스
HashMap보다 데이터 추가, 삭제에 시간이 더 걸림.
· HashMap의 키와 값
해싱(Hashing)기법으로 데이터 저장. 데이터가 많아도 검색이 빠르다.
Map 인터페이스 구현. 데이터를 키와 값의 쌍
//저장: put // 같은 키에 다른 값을 저장하면 덮어쓰기를 해버린다.
// Entry 배열이 HashMap 안에 선언되어있다.
// Object [] key; Object [] value;처럼 해도되지만 객체지향적인 코드로 짜는 게 낫다.
Entry [] table; class Entry { Object key; Object value; }
· 해싱(hashing) ex) 환자정보관리
Key값이 주어지면, 해시함수가 배열의 index(저장위치)를 반환한다. 이를 해쉬코드라고 한다.
ex) 주민번호 앞 2자리 대로 10개의 서랍으로 분류하면 72인 경우, 배열 index가 7인 서랍 위치 반환
해싱은 해쉬함수를 이용하여 저장하고 읽어오는 것이다.
해쉬함수로 해시테이블에 데이터를 저장, 검색
· 해시테이블은 배열과 링크드 리스트가 조합된 형태
배열의 장점인 접근성과 링크드리스트의 장점인 변경 유리가 혼합된 것.
HashMap와 Hashtable, HashSet은 hashcode()를 사용하고, Objects.hash() 로 오버라이딩해서 해시함수를 사용 하면 된다.
· 해시테이블에 저장된 데이터를 가져오는 과정
키로 해시함수를 호출해서 해시코드를 얻는다.
2. 해시코드(해시함수의 반환값)에 대응하는 링크드리스트를 배열에서 찾는다.
3. 링크드리스트에서 키와 일치하는 데이터를 찾는다.
# 해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야한다. 서로 다른 키여도 같은 값의 해시코드를 반환할 수도 있다. ex) 70년대(같은 값의 해시코드)에 있는 75xxxx와 72xxxx
· HashMap – 주요 메서드
// HashMap(Map m)은 Map 타입 객체를 HashMap 타입으로 변환
// putAll(Map m)은 Map에 있는 걸 모두 저장
// Set entrySet()은 Set타입으로 entry를 반환
// Object getOrDefault는 키 값이 없으면 defaultValue로 반환
· 예제 EX 11_16 아이디, 비밀번호 로그인
· 예제 EX 11_17
// while(it.hasNext()) 와 타입 참조변수 = (타입) it.next(); 매우 중요!!
// iterator를 사용하는데 Collection vs Set 의 차이를 알것!
// .max 와 .min을 호출하려면 기준을 알아야하기에 comparable을 구현한 클래스 객체만 가능
// Map.Entry(Map 인터페이스 안에 있는 Entry 인터페이스)
· 예제 Ex 11_18 글자 카운팅
// 기존 값이 없으면 map.put(data[i],1);
// printBar(“-”, value)는 value 만큼 –를 !!
● ch 11-52~56 Collections 컬렉션 클래스 요약
· Collections – 컬렉션을 위한 메서드(static)를 제공 ex) Objects(객체를 다룰 때 유용한 메서드 제공), Arrays(배열), Collections(컬렉션) 와 비슷하다고 보면 된다.
컬렉션 채우기, 복사, 정렬, 검색 – fill(), copy(), sort(), binarySearch() 등
2. 컬렉션의 동기화 – synchronizedXXX() // 필요할 때 동기화하도록 바뀌었다. // XXX는 뒤에 붙는
3. 변경불가(readOnly) 컬렉션 만들기 – unmodifiableXXX() //컬렉션을 수정불가로 만든다.
4. 싱글톤 컬렉션 만들기 –singletonXXX() # 싱글톤 컬렉션은 객체 1개만 저장하는 컬렉션
5. 한 종류의 객체만 저장하는 컬렉션 만들기 – checkedXXX() //원래 add(Object obj)라서 모든 타입이 저장가능한데, 이를 바꾸는 것 // 이를 지네릭스가 하기도 하지만, JDK 1.5부터 나왔기에 checked 잘 안쓴다.
· 예제 Ex 11_19
import static java.util.Collections.* 로 인해 메서드 사용 가능
- addALL(리스트, 가변인자) // 리스트에 가변인자를 채운다.
- rotate(리스트, 숫자) // 오른쪽으로 두 칸씩 이동(반시계방향으로 두 번 회전)
swap(리스트, idx, idx) // 서로 교환
shuffle(리스트) //저장된 요소 위치 임의 변경
sort(리스트, 정렬기준) => binarySearch를 쓸 때 정렬을 먼저 하고!
nCopies(리스트 크기, 2) //리스트 크기만큼의 크기로 배열을 만들고 2로 채운다.
disjoijnt(리스트1, 리스트2) // 공통요소가 없으면 true
copy(리스트1, 리스트2) // 리스트 2를 리스트 1에 덮어쓰기
// 이렇게 공부한 것을 그리며 요약하기!!
from http://ing-til-death.tistory.com/66 by ccl(A) rewrite - 2021-10-05 23:01:21