- 집합
- 순서X (해시값에 의해 데이터 저장)
- (1,2,3) == (3,1,2)
- 인덱스 개념 없음 => iterator로 직접 인덱싱
- 원소 중복 불가
hashCode()(해시코드) 와equals()(데이터) 가 true 이면 동일한 객체라고 판단
hash
hashing : 매핑하는 과정
1. hash function 으로 레코드로 계산한 해시 코드를 home address로 변경
- 데이터에 대한 키 값 생성하기 위한 함수
- address 아님 (JVM이 관리하므로 직접 특정 address에 넣는 등의 핸들링 못함)
hash table이라는 가상 기억 공간에서 계산한 home address에 주어진 레코드 저장/검색
- home address는 JVM이 해시코드 값 보고 리턴
해시 충돌
- 다른 두개의 객체에 대해 동일한 해시코드 생성 될 수 있다
- int의 범위가 제한되어 순회하기 때문에 발생
- 해결방법1:
LinkedList,Chaining- 연결 리스트의 길이만큼 for문 돌면서 접근 (equals())
- O(n)
- 해결방법2: 같은 해시코드 값을 가진 객체를 특정 규칙의
Tree로 만듦 (Heap) +Chaining- O(logn) // up and down
- 검색 성능 더 좋다. 현재 자바가 채택
- for + equals() 대신 트리 검색 (O(log2n))
- 해결방법3: Open Addressing
- 충돌 일어난 객체의 해시코드 변경, home address 만들지 않고 해시코드 값을 해시테이블에서 키로 바로 이용하여 저장
- 슬롯 80% 차면 성능 저하
- Python, Ruby
HashSet
- 내부적으로
HashMap이용
- HashSet에 저장할 레코드 -> HashMap의 key (value = dummy)
- -> hash function에 의해 hash code
- -> home address (hash table)
- -> home address에 레코드 저장
/*
HashSet
- 중복, 순서X
- 인덱스 다루는 함수 없음
- for -> Iterator
=> 들어온 순서를 유지하는 LinkedHashSet 만듦
*/
public class HashSetExample {
public static void main(String[] args) {
// 업캐스팅 - 다형성, api 사용
Set<Integer> hashSet = new HashSet<>(3);
// add()
for (int i = 10; i >= 1 ; i--) { // 10 ~ 1 -> 1 ~ 10 (hashCode()를 키 값으로 저장 하기 때문에 순서 유지X)
hashSet.add(i);
}
System.out.println("hashSet = " + hashSet);
System.out.println("hashSet.size() = " + hashSet.size());
System.out.println();
// 원소 중복 불가
// 중복 체크 : 두 원소의 hashCode() => true, equals() => true
// 해시코드만 같으면 충돌 일 수 있으므로 equals()도 체크
for (int i = 10; i >= 1 ; i--) {
hashSet.add(i);
}
System.out.println("hashSet = " + hashSet);
System.out.println("hashSet.size() = " + hashSet.size());
System.out.println();
// addAll() : 합집합
// Set.of() : Set 초기화
System.out.println("hashSet.addAll(Set.of(100, 200)) = "
+ hashSet.addAll(Set.of(100, 200))); // 순서 유지X (해시 코드 순서대로 들어감)
System.out.println("hashSet = " + hashSet); // 내부 toString() 재정의
System.out.println("hashSet.size() = " + hashSet.size());
System.out.println();
// iterator()
// 인덱스 없기 때문에 fori 또는 get(i) 로 접근 불가 (해시 코드 순서대로 저장) => Iterator
// hashSet.get(i);
Iterator<Integer> iterator = hashSet.iterator();
while (iterator.hasNext()) {
System.out.println("iterator.next() = " + iterator.next());
}
System.out.println();
// 인덱스 다루는 함수 없음
// hashSet.add(1, Integer.valueOf(1));
// hashSet.get(i)
// hashSet.indexOf()
// hashSet.lastIndexOf()
// hashSet.subList(1, 2);
// remove(element)
hashSet.remove(1); // 1 이라 작성해도 Object로 들어가지만, 가독성을 위해 아래처럼 작성하는 것이 좋음 != List
hashSet.remove(Integer.valueOf(1)); // 1 이라는 인덱스 아닌 object 삭제
System.out.println("hashSet = " + hashSet);
System.out.println("hashSet.size() = " + hashSet.size());
System.out.println();
// hashCode() :
Iterator<Integer> iterator1 = hashSet.iterator();
while (iterator1.hasNext()) {
Integer i = iterator1.next();
System.out.print(i.hashCode() + ", ");
}
System.out.println();
System.out.println("hashSet.hashCode() = " + hashSet.hashCode()); // 내부 원소 다 더한 값
System.out.println();
// contains(), containsAll() : 원소 유무 확인 (boolean)
System.out.println("hashSet = " + hashSet);
System.out.println("hashSet.contains(10) = " + hashSet.contains(10));
System.out.println("hashSet.containsAll(Set.of(4, 5, 6)) = " + hashSet.containsAll(Set.of(4, 5, 6)));
System.out.println();
// retainAll() : 두 컬렉션 교집합 => 원본 수정
System.out.println("hashSet.retainAll(Set.of(1, 2, 3, 4)) = " + hashSet.retainAll(Set.of(1, 2, 3, 4)));
System.out.println("hashSet = " + hashSet);
System.out.println();
// removeAll() : 컬렉션 원소 모두 삭제 (차집합) => 원본 수정
hashSet.removeAll(Set.of(1, 2, 3));
System.out.println("hashSet = " + hashSet);
System.out.println("hashSet.size() = " + hashSet.size());
System.out.println();
// clear() : 원소 모두 삭제
hashSet.clear();
System.out.println("hashSet = " + hashSet);
System.out.println("hashSet.size() = " + hashSet.size());
System.out.println();
// isEmpty()
System.out.println("hashSet.isEmpty() = " + hashSet.isEmpty());
System.out.println();
// Set (동적 컬렉션) -> Array (정적 객체 배열) : 수정 안 하겠다
Set<String> stringSet = new HashSet<>();
for (int i = 'a'; i <= 'z' ; i++) {
stringSet.add(Character.toString(i)); // 1. Character.toString() : '' -> ""
}
System.out.println("stringSet = " + stringSet);
String[] stringArray = stringSet.toArray(new String[stringSet.size()]); // 2. toArray() : HashSet<String> -> String[]
System.out.println("stringArray = " + Arrays.toString(stringArray)); // Arrays.toString() : 주소 아닌 내용물 출력
// Array -> Set : 수정 하겠다
Set<String> stringSet1 = new HashSet<>(Arrays.asList(stringArray)); // 3. new HashSet<>(Arrays.asList()) : String[] -> HashSet<String>
System.out.println("stringSet1 = " + stringSet1);
}
}LinkedHahsSet
- HashSet + 삽입 순서 유지
- 해쉬 테이블과 연결 리스트가 결합된 형태 (HashSet에 대한 순서도 LinkedList로 따로 저장)
- HashSet과 메서드 동일
public class LinkedHashSetExample {
public static void main(String[] args) {
Set<Integer> linkedHashSet = new LinkedHashSet<>(3);
// add()
for (int i = 10; i >= 1 ; i--) { // 10 ~ 1 -> 10 ~ 1 (순서 유지)
linkedHashSet.add(i);
}
System.out.println("linkedHashSet = " + linkedHashSet);
System.out.println("linkedHashSet.size() = " + linkedHashSet.size());
System.out.println();
...
}TreeSet
- HashSet + 객체의 특정 순서 유지 (Comparable, Comparator)
- HashSet과 메서드 동일
- 속도는 HashSet 보다 느림
- 내부 구현: 레드-블랙 트리
- 트리는 양쪽 높이가 비슷해야 검색 성능이 좋음 (O(logn))
- => 자가 균형 이진 탐색 트리
- 검색/정렬👍, 추가/삭제👎 (tree rebalance 회전)
public class TreeSetExample {
public static void main(String[] args) {
Set<Integer> treeSet = new TreeSet<>(); // Integer 의 크기는 정해져 있음
// Integer가 아닌 객체의 크기의 순서는 어떻게 정해질까 => Comparable, Comparator 의 compareTo()
Set<Pen> penSet = new TreeSet<>();
// Pen 객체에 Comparable, Comparator 상속 안준 경우 => ClassCastException
// => 정렬/add 할때 Comparable 객체로 바꿔야 하는데(내부 구현) 바꿀 수 없다
Set<Pen> penSet1 = new TreeSet<>(new Comparator<Pen>() {
@Override
public int compare(Pen o1, Pen o2) {
return o1.getCompanyName().compareTo(o2.getCompanyName()); // companyName 기준으로 정렬
}
});
// 0001 ~ 0004 -> 0004 ~ 0001 (productNo의 역순)
penSet.add(new Pen("0001", "파카", "red"));
penSet.add(new Pen("0002", "빅", "black"));
penSet.add(new Pen("0003", "파카", "blue"));
penSet.add(new Pen("0004", "제브라", "red"));
System.out.println("penSet = " + penSet);
System.out.println();
...
}
}Set
- 정적인(수정 필요 없는) 데이터 저장 (메서드 사용 불가)
public class SetExample {
public static void main(String[] args) {
//// Set 초기화
// 1. Set.of()
Set<Integer> integerSet = Set.of(1, 2, 3, 4);
System.out.println("integerSet = " + integerSet); // 순서 유지X
// Set<Integer> integerSet1 = Set.of(1, 2, 3, 4, 1, 2, 3, 4); // IllegalArgumentException (원소 중복 불가)
// System.out.println("integerSet1 = " + integerSet1);
// 2. 인터페이스는 new 초기화 불가
// Set<Integer> set = new Set<Integer>();
// 3. stream
Set<Integer> intStreamSet = IntStream.range(1, 11).mapToObj(i -> i).collect(Collectors.toSet());
System.out.println("intStreamSet = " + intStreamSet);
System.out.println();
System.out.println("integerSet.size() => " + integerSet.size());
System.out.println();
//// Set은 인터페이스이기 때문에 객체 생성이나 추가, 삭제, 수정 연산 불가능 (UnsupportedOperationException)
// Set은 인덱스가 없기 떄문에 인덱스가 필요한 메소드 호출 불가
// 원소 추가
// for (int i = 1; i <= 10 ; i++) {
// integerSet.add(i);
// }
// System.out.println(integerSet);
// System.out.println("integerSet.size() => " + integerSet.size());
// System.out.println();
// 원소 접근
// for (int i = 0; i < integerSet.size(); i++) {
// System.out.println("integerSet.get(i) = " + integerSet.get(i));;
// }
// System.out.println();
// 원소 수정
// integerSet.set(1, 200);
// 원하는 인덱스에 원소 추가
// integerSet.add(2, 100);
// integerSet.add(-1, 100); // IndexOutOfBoundsException
// integerSet.add(20, 100); // IndexOutOfBoundsException
// integerSet.add(2, "abc"); // compile error. type mismatch.
// System.out.println(integerSet);
// System.out.println("integerSet.size() => " + integerSet.size());
// System.out.println();
// 컬렉션 일부 반환
// List<Integer> subList = integerSet.subList(1, 5);
// System.out.println("subList = " + subList);
// 반환된 컬렉션 일부를 모두 추가
// integerSet.addAll(Set.of(500, 600));
// System.out.println(integerSet);
// System.out.println("integerSet.size() => " + integerSet.size());
// System.out.println();
// 컬렉션 정렬
// integerSet.sort(new Comparator<Integer>() {
// @Override
// public int compare(Integer o1, Integer o2) {
// return Integer.compare(o1, o2);
// }
// });
// System.out.println(integerSet);
// System.out.println();
// 일부 원소를 찾아 첫번째로 만난 원소의 인덱스 반환
// System.out.println("integerSet.indexOf(100) => " + integerSet.indexOf(100)); // 앞에서 부터 찾음
// System.out.println("integerSet.lastIndexOf(100) => " + integerSet.lastIndexOf(100)); // 뒤에서 부터 찾음
// System.out.println(integerSet);
// System.out.println();
// 일부 원소 포함관계 확인
System.out.println("integerSet.contains(3) => " + integerSet.contains(3));
System.out.println(integerSet);
System.out.println();
// 일부 컬렉션 포함관계 확인
System.out.println("integerSet.containsAll(List.of(3, 4, 5, 6, 7)) => " + integerSet.containsAll(List.of(3, 4, 5, 6, 7)));
System.out.println(integerSet);
System.out.println();
// 현재 컬렉션과 주어진 컬렉션 사이의 교집합 반환
// System.out.println("integerSet.retainAll(List.of(3, 4, 5, 6, 7)) => " + integerSet.retainAll(List.of(3, 4, 5, 6, 7)));
// System.out.println(integerSet);
// System.out.println();
// 현재 컬렉션과 주어진 컬렉션 사이의 차집합 반환
// System.out.println("integerSet.removeAll(List.of(3, 4)) => " + integerSet.removeAll(List.of(3, 4)));
// System.out.println(integerSet);
// System.out.println();
// 컬렉션 원소 삭제
// System.out.println("integerSet.remove(5) = " + integerSet.remove(5)); // IndexOutOfBoundsException
// System.out.println("integerSet.remove(5) = " + integerSet.remove(-1)); // IndexOutOfBoundsException
// System.out.println("integerSet.remove(5) = " + integerSet.remove(20)); // IndexOutOfBoundsException
// 값으로 원소 삭제
// System.out.println("integerSet.remove(Integer.valueOf(5)) = " + integerSet.remove(Integer.valueOf(5)));
// System.out.println(integerSet);
// System.out.println();
//
// 컬렉션 clear
// integerSet.clear();
// System.out.println(integerSet);
// System.out.println("integerSet.size() => " + integerSet.size());
// System.out.println();
// 컬렉션 비어있는지 확인
System.out.println("integerSet.isEmpty() = " + integerSet.isEmpty());
System.out.println();
//// Set (컬렉션) -> Array (객체 배열)
Set<String> stringsSet = new HashSet<>();
for (int i = 'a'; i <= 'z'; i++) {
stringsSet.add(Character.toString(i));
}
System.out.println("stringList = " + stringsSet);
String[] stringArray = stringsSet.toArray(new String[stringsSet.size()]);
System.out.println("stringArray = " + Arrays.toString(stringArray));
// Array (객체 배열) -> Set (컬렉션)
Set<String> stringSet1 = new HashSet<>(Arrays.asList(stringArray));
System.out.println("stringList1 = " + stringSet1);
}
}