개발자로 후회없는 삶 살기
[문법] 자바 해시를 사용한 데이터 형식(HashMap, HashSet) 본문
서론
※ 과거에 기록한 내용에서 중요한 부분만 발췌하여 모두가 이해하기 쉽게 다시 서술한다.
- 자바의 데이터 형식
- Arrays, Collections 클래스
본론
- 자바의 데이터 형식
1. List : 데이터의 중복을 허용하는 순서가 있는 데이터 집합
2. Set : 데이터의 중복을 허용하지 않고, 순서가 없는 데이터 집합, List와 Set은 상위에 공통 기능을 가지는 Collection 인터페이스를 가짐
3. Map : 키-벨류 쌍의 데이터 집합, 상위에 Collection 인터페이스가 없음
🚨 컬랙션에서 동기화란?
Arraylist와 Vector, HashTable과 HashMap은 동일한 기능을 제공하는 것처럼 보이나, 동기화 지원 여부라는 차이가 있다.
-> HashTable의 Put
synchronized 키워드가 있는 데 이는 병렬 프로그래밍 시 공유 자원에 대한 동시 접근을 안전하게 관리해준다.
-> HashMap의 Put
synchronized가 존재하지 않아, 동기화를 지원하지 않는다.
HashTable : 병렬 처리를 고려해야 하는 상황에서 사용, 동기화 기능으로 약간의 시간 지연 발생
HashMap : 병렬 처리를 고려하지 않는 상황
위 두 타입을 선택해야 하는 기준은 다음과 같다.
-> Vector의 add
-> ArrayList의 add
List와 Vector에서는 Vector가 동기화를 지원한다.
- List
리스트와 관련된 모든 것을 알아보자
1. 리스트로 만드는 메서드
public static void main(String[] args) {
List<Integer> list1 = List.of(1, 2, 3);
List<Integer> list2 = Arrays.asList(1, 2, 3);
}
요소들을 입력 받아, 리스트를 반환하는 메서드들이 존재한다. 각 메서드마다, 불변성에 차이가 있고 of는 정적 팩토리 메서드명을 따른다.
2. Iterator
자바는 데이터 형식마다 구조가 다르기 때문에 구체적인 타입에 관계없이 일관된 방법으로 요소들을 순회하기 위해 Iterator 인터페이스를 제공한다. 만약 for문으로 순회하면 리스트 타입을 사용하다, set 타입으로 바꾸면 순회하는 코드도 수정해야 하는데 Iterator 타입으로 추상화하여 코드의 변경을 막는다.
-> 예시
public static void main(String[] args) {
List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
Set<Integer> set = new HashSet<>(List.of(1, 2, 3));
Iterator<Integer> setIterator = set.iterator();
while (setIterator.hasNext()) {
System.out.println(setIterator.next());
}
}
Iterator를 사용하면 데이터 집합이 리스트냐 Set이냐에 상관없이 내부 내용물이 Integer인 것에 초점에 맞춰 Iterator 타입으로 통일하여 순회할 수 있다. Iterator는 일회용이라서 한 번 사용 후 다시 만들어야 한다.
-> Map과 Iterator
Iterator는 Collection 타입에 제공되는데 Map은 Collection의 하위 타입이 아니라서 iterator를 사용할 수 없다.
Map에서 Iterator를 사용하려면, Set으로 만들어야 한다.
entryset은 맵의 모든 키-value 쌍을 Set으로 반환한다.
Set의 요소는 Map.Entry 인터페이스 타입이며 Map.Entry는 Map 컬랙션 내부의 키-벨류 쌍 각각을 표현한다.
{하나 : "one", 둘 : "two"}
예를들어 위 예제에서는 Map.Entry(하나, one), Map.Entry(둘, two)라고 볼 수 있다. Map에 add를 하면 Map.Entry 하나가 Map에 저장된다.
getKey()
getValue()
setValue()
Map.Entry는 이러한 메서드를 제공하여 하나의 Map.Entry의 키-벨류에 접근할 수 있다.
Set<String> set2 = map.keySet();
for (String s : set2) {
System.out.println(s);
}
keyset은 맵의 모든 키를 Set으로 반환한다.
Collection<Integer> set3 = map.values();
for (Integer i : set3) {
System.out.println(i);
}
values는 맵의 모든 벨류를 Collection 타입으로 반환한다. 둘 다 키와 벨류를 순회할 수 있다.
- Map
Map은 키-벨류 형태의 컬랙션으로 키는 중복될 수 없지만, 벨류는 중복이 가능하다. 보통 HashMap을 사용하며, HashTable은 HashMap에서 동기화 기능을 넣은 것 뿐이고, TreeMap은 Hash 테이블 구조가 아닌 트리 구조를 가진 Map이다. HashMap은 순서를 유지하지 않으며, LinkedHashMap은 순서를 유지한다.
=> HashMap
앞에 Hash가 붙은 데이터 타입들은 모두 해시 기법을 사용한 것으로, 데이터의 수가 많아도 검색 속도가 O(1)의 시간복잡도를 가진다.
-> 해시 함수란?
가변 크기의 입력을 고정 크기의 값으로 변환하는 함수이다. 해싱 기법에서는 해시 함수를 사용하여 데이터가 저장될 주소를 만들고 이를 해시 코드라 부르며, 해시 코드를 벨류가 저장될 주소로 사용한다. 해시맵은 이러한 방법으로 중복을 제거하고 데이터를 저장한다. 이는 밑에서 중복 제거로 유명한 set 데이터 형식에서 알아본다.
-> 해시테이블이란?
앞 단에는 배열을 둬서 빠르게 찾고, 각 요소에는 연결 리스트를 둬서 변경에 유리하게 한 데이터 구조이다. 배열의 인덱스에 접근하여 연결 리스트에서 데이터를 찾을 수 있다. HashMap은 해시 테이블 형태로 키를 해시 함수에 넣어 해시 코드를 만들고, 이를 배열에 데이터가 저장될 주소, 즉 배열의 인덱스로 사용한다.
- Set
Set과 관련된 모든 것을 알아보자
1. HashSet
일반적으로 순서와 중복이 없는 Set이 필요하면 HashSet을 사용하면 된다. 순서를 유지하고자 하면 LinkedHashSet을 사용한다.
🚨 Set에 해시가 어떻게 사용될까?
Hash가 붙은 데이터 타입은 모두, 해싱 기법을 사용하며, 해시셋은 내부적으로 해시맵으로 동작한다. 해시셋은 해시맵의 장점을 채택한 Set 구조인데, 해시셋이 해시맵으로 어떻게 동작하나 알아보자
-> set에 요소 추가
set에 요소를 추가하면 추가한 요소를 키로, 더미 객체를 벨류로 저장한다. 따라서 해시맵의 요소 추가 방식을 이해하면 set이 중복을 제거하고 요소를 관리하는 방법을 이해할 수 있다.
키 : 저장하려는 요소값
벨류 : 더미객체
해시맵은 키-벨류 형태의 데이터 형식이라 해시테이블 형태로 표현되는 것이 이해되지만, 셋은 요소 하나만 저장하기에 벨류가 무엇일지 의문이 들 수 있다.
사실, 해시셋은 데이터 하나만 저장하지, 키-벨류가 아니기 때문에 벨류에 저장될 데이터가 없기에 더미객체를 벨류로 사용한다.
-> set의 중복 제거
해시맵은 hashCode와 equals 메서드로 저장 위치를 정하고 중복을 제거하는 데이터 형식이다.
1. hashCode로 앞단 배열의 주소를 구하고 저장될 주소로 선택
2. 만약 해당 주소에 이미 요소가 있다면 equals로 실제 동일 값을 가지는 지 검사
set이 이러한 동작 방식을 그대로 사용한다. 자바의 primitive 타입은 기본적으로 중복을 제거하지만,
class Person {
private int age;
private String name;
public Person(int age, String name) {
this.age = age;
this.name = name;
}
}
객체 타입은 동일성과 동등성을 구현하지 않으면 중복되는 데이터를 넣어도 중복이 제거되지 않는다.
만약, 위 상황에서 개발자가 같은 필드값을 가지는 객체를 set에 중복되지 않는 것을 기대했다면, 논리적인 오류로 볼 수 있다. 이를 이해해보자.
동일성만 구현했을 경우, 중복값이 존재한다. 즉, Set은 주소는 같아도 데이터가 같은지 검사하는 과정이 필요하다.
동등성만 구현했을 경우, 중복값이 존재하며, Set은 내용이 같아도 주소가 같은지 검사하는 과정이 필요하다. 사실, 주소 검사를 먼저한다.
둘 다 구현했을 경우 중복값이 사라지며, Set은 동등성과 동일성을 모두 구현해야 중복을 제거한다.
✅ 해시맵에 중복 확인
-> hashCode 메서드를 구현하는 이유
해시함수의 특징은 동일값을 입력하면 항상 동일 출력이 나오는 것이다. 해시 코드 재정의 형태를 보면 같은 나이와 이름을 가지면 매번 동일 출력이 나올 텐데, 이를 통해 동일한 값을 가지면 배열에서 동일한 인덱스를 가지도록 하여 중복이라고 하기 위함이다. hashCode를 재정의하지 않으면 중복이 제거되지 않는 이유는 동일 값이라도 해시코드가 다를 테니 다른 값이기 때문이다.
-> equals 메서드를 구현하는 이유
해시맵에 put을 하면 먼저 hashCode를 구하고 해당 주소에 간다.
그 후 만약 해당 주소에 요소가 있다면 같은 요소인지 검사를 하게 되는 데 이때 동등성을 사용한다.
equals가 재정의 된 것을 보면, 동일 값을 가지면 True를 반환하여 중복임을 알린다. 이렇게 동작하는 해시맵을 사용하여 해시셋은 중복을 제거한다.
equals를 재정의하지 않으면 중복을 제거하지 않는 이유는 재정의 전에는 객체의 힙 주소 비교를 하기 때문에 같은 필드 값을 가지고 있더라도 객체가 다르면 다른 객체로 보기 때문이다. 해시코드와 객체의 힙 주소는 다르며, 해시 코드는 해시맵에서 저장될 인덱스를 주소로 표현하는 것 뿐이고 실제 객체의 주소는 힙 영역의 주소이다.
🚨 해시셋이 해시맵을 사용하는 이유 정리
검색 시 O(1)의 빠른 접근 속도
해시코드를 사용한 빠르고 명확한 저장 방식
이러한 장점을 사용하기 위해 해시셋이 해시맵을 채택했다.
-> 정렬
set은 순서가 없기 때문에 정렬이 불가능하며,
정렬을 하려면 List로 변환해야 하지만, 이 또한 순서를 유지 하지 않기 때문에 순서가 필요한 경우 Set을 사용하면 안 된다.
2. TreeSet
이진탐색트리 구조를 가지는 set이다. 이진탐색트리는 부모보다 작은 요소는 왼쪽, 큰 요소는 오른쪽에 있는 특성이 있다. Set은 순서가 없는 데이터 집합이라고 했는 데, 이진 탐색의 특성에 맞게 순서가 있고 정렬이 된 상태로 존재한다.
장점 : 검색과 정렬 속도가 빠름
단점 : 추가 삭제 속도가 느림
이진탐색 특성에 따라, 검색과 정렬에 유리하지만, HashSet보다 데이터 추가, 삭제에 시간이 더 걸린다.
-> 비교 기준
이진 탐색 트리는 부모보다 큰지, 작은지 비교하는 과정이 필요하여, TreeSet을 생성할 때 정렬 기준을 인자로 받는다. 만약 정렬 기준을 넣지 않으면 요소의 클래스에 Comparable 정렬 기준 클래스를 상속받고, 재정의한 compare 메서드로 비교 기준을 결정한다.
위 코드는 Person 클래스의 나이로 정렬 기준을 주며, TreeSet을 선언하는 법을 보여준다.
- Arrays
Math 클래스가 수학 관련 메서드들을 모아 놓은 클래스라면, Arrays는 배열을 다루는 데 유용한 static 메서드들을 제공한다.
1. toString()
배열을 문자열로 반환하는 메서드로, 배열의 데이터 타입별로 오버로딩 되어있다. 다차원 배열 출력은 deepToString을 사용한다.
2. equals()
배열은 등가 비교 연산자를 제공하지 않는다. 각 요소를 하나 하나 비교하는 과정이 필요하고 이를 메서드로 제공한다. 내용을 비교하여 전부 같아야 True를 반환한다. 다차원 배열 출력은 deepEquals를 사용한다.
3. sort()
배열을 정렬하는 메서드를 제공한다. List는 인터페이스에 sort가 메서드 멤버로 존재하지만 배열은 클래스나 인터페이스가 아니라서 정렬 메서드가 따로 존재한다. 정렬 기준은 이 블로그를 참고하자.
4. 배열 채우기
fill 메서드와 setAll 메서드가 있고, setAll은 람다식으로 배열을 채운다.
5. 검색
이진탐색이니 정렬이 필요하고, 원하는 요소의 인덱스를 출력한다. 없으면 -6을 출력한다.
- Collections
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
Collections.addAll(list, 1, 2, 3, 4);
Collections.fill(list, 9);
Collections.rotate(list, 2); // 오른쪽으로 2칸 회전
Collections.swap(list, 0, 2);
Collections.shuffle(list); // 순서를 무작위로 섞음
Collections.replaceAll(list, 2, 1); // 2를 1로 대체
// 비교 기준 Comparable 재정의 필수
Collections.max(list);
List<Person> people = new ArrayList<>();
Collections.max(people);
}
class Person implements Comparable{}
Collections은 컬랙션을 다루는 데 유용한 static 메서드들을 제공한다. 기본적으로 addAll, fill과 같은 Arrays와 동일한 기능을 하는 메서드를 내장하고 있다.
1. 동기화
List<Object> objects = Collections.synchronizedList(new ArrayList<>());
ArrayList의 경우 기본이 동기화를 하지 않으므로, 항상 동기화 하는 것이 아닌 필요할 경우만 동기화하는 기능을 제공한다. 리스트를 동기화하면 Vector를 사용하는 것과 같다.
2. 변경불가
List<Object> objects = Collections.unmodifiableList(new ArrayList<>());
컬랙션을 수정할 수 없게 읽기 전용으로 만들어준다. 리스트를 인자로 주고 받을 경우 반드시 읽기 전용으로 반환하는 게 좋다.
3. 한 종류의 객체만 저장
List<String> strings = Collections.checkedList(new ArrayList<>(), String.class);
Map<String, Integer> stringIntegerMap = Collections.checkedMap(new HashMap<>(), String.class, Integer.class);
컬랙션은 원래 타입을 지정하지 않으면 여러가지 타입을 다 받을 수 있는데, 컬랙션에서 타입을 지정하여 한 종류의 요소만 받는 컬랙션을 만드는 것이다.
제네릭 타입을 지정하는 것과 같은 효과를 보인다.
참고
'[백엔드] > [Java | 학습기록]' 카테고리의 다른 글
[Core] JVM의 역할과 동작 원리 (0) | 2024.06.19 |
---|---|
[문법] 오류를 핸들링하는 방법 (0) | 2024.06.05 |
[문법] try-with-resources를 사용해야 하는 이유 (0) | 2024.05.29 |
[문법] 자바 입력 데이터 저장 방식 (0) | 2024.05.28 |
[문법] Comparator, Comparable 정렬 원리 (0) | 2024.05.27 |