ISP: 인터페이스 분리 원칙 (Interface Segregation Principle)
DIP: 의존관계 역전 원칙 (Dependency Inversion Principle)
하나씩 알아보자.
SRP (Single Responsibility Principle)
단일 책임 원칙이라는 뜻의 SRP. 무슨 말일까? 한 클래스는 하나의 책임만 가져야 한다.
하나의 책임이라는 것은 모호하다. 책임의 크기를 말하는게 아니다. 문맥과 상황에 따라서도 다르다.
중요한 기준은 변경이다. 변경이 있을 때 파급 효과가 적으면 단일 책임 원칙을 잘 따른 것.
예를 들어, MVC 패턴에서 V는 View이다. UI와 관련된 책임을 가지는 부분이고 이 곳에선 비즈니스 로직이나 그 외 것들엔 책임을 지게 해선 안된다(안되는게 좋다).
개인적인 생각으로 JSP가 대체 기술이 생긴 이유는 이 단일 책임 원칙이 잘 지켜지지 않기 때문이다.
JSP는 뷰와 로직을 동시에 가지고 있다. 책임이 너무 크고 분산되어 있지 않다. 이를 대체하기 위해 스프링 MVC 패턴이 등장했다.
OCP (Open/Closed Principle)
개방-폐쇄 원칙이라고 하는데 난 확장에는 열려있고 변경에는 닫혀있는 원칙이라고 표현한다.
즉, 기술의 확장이 있어도 코드의 변경이 없어야 한다는 뜻인데 굉장히 알 수 없는 말이다.
무엇을 떠올리면 되냐면 DI를 떠올리면 된다. 클라이언트 코드는 그저 인터페이스만을 의존한다. 인터페이스를 구현한 기술이 10개든 100개든 어떤 기술이 새로 만들어지고 어떤 기술로 갈아끼우던지 클라이언트 코드는 변경할 부분이 없다. 인터페이스를 의존하기 때문이다.
이게 OCP 원칙이고 5가지 원칙 중 가장 중요한 원칙이라고 생각한다. 의존관계의 결정을 나중으로 미루는 것. 그에 따라 확장성과 유지보수에 훨씬 유리해지고 코드의 변경은 최소화하거나 아예 하지 않아도 된다.
LSP (Liskov Substitution Principle)
리스코프 치환 원칙이라고 하는데 제일 어려워 보이지만 제일 쉬운 원칙이다.
프로그램의 객체는 프로그램의 정확성을 깨뜨리지 않으면서 하위 타입의 인스턴스로 바꿀 수 있어야 한다.
"무슨 말이세요?"
그러니까, 쉽게 말해서 자동차라는 인터페이스가 있고 엑셀밟기 라는 메서드를 정의했으면 이 인터페이스를 구현하는 구현체는 엑셀밟기 메서드를 구현할 때 앞으로 가는 기능을 구현해야 하지 뒤로 가는 기능을 구현해선 안된다는 뜻이다. 프로그램이 의도하는 정확성을 지켜야 한다는 뜻이다. 근데 스포츠카와 기본 자동차는 같은 엑셀을 밟더라도 속도의 차이가 현저히 날 수 있다. 그러나 둘 다 엑셀을 밟으면? 앞으로 간다. 이게 포인트.
그 구현하는 방식이 조금씩 다르더라도 정확한 의도대로 구현해야 한다는 원칙.
ISP (Interface Segregation Principle)
인터페이스 분리 원칙. 특정 클라이언트를 위한 인터페이스 여러 개가 범용 인터페이스 하나보다 낫다.
예를 들어, 자동차 인터페이스가 있을 때 이 인터페이스는 운전과 관련된 메서드와 정비와 관련된 메서드 둘 다를 정의할 수 있지만 애시당초에 자동차 인터페이스를 운전 인터페이스, 정비 인터페이스로 분리하는게 더 좋다는 것이다.
왜 더 좋을까?
첫번째는, 저 둘로 분리하게 됐을 때 정비 인터페이스 자체가 변해도 운전자 클라이언트 - 운전 인터페이스 간에는 어떠한 영향도 주지 않는다.
두번째는, 인터페이스가 명확해지고 대체 가능성이 높아진다.
DIP (Dependency Inversion Principle)
의존관계 역전 원칙으로, OCP와 같이 중요한 원칙 중 하나라고 생각한다. 프로그래머는 "추상화에 의존해야지, 구체화에 의존하면 안된다." 의존성 주입은 이 원칙을 따르는 방법 중 하나다.
쉽게 이야기하면, 클라이언트 코드는 구체클래스를 의존하는게 아니라 인터페이스를 의존해서 기술에 변경이 있어도 클라이언트 코드에 수정이 필요없게 설계하라는 뜻이다. 이 말을 한 단어로 DI라고 하는 것이고. 의존관계의 결정을 나중으로 미루는 것이다.
근데 Comparator는 편의 메서드인 reversed()가 있다. 다음과 같이 사용하면 된다.
말 그대로 정렬을 반대로 한것이라고 보면 된다.
package org.example.collection.compare;
import java.util.Arrays;
import java.util.Comparator;
public class SortMain1 {
public static void main(String[] args) {
Integer[] array = {3, 2, 1};
Arrays.sort(array, new AscComparator().reversed());
System.out.println("오름차순 정렬의 리버스(내림차순)= " + Arrays.toString(array));
}
private static class AscComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 < o2 ? -1 : o1 == o2 ? 0 : 1;
}
}
}
실행결과
오름차순 정렬의 리버스(내림차순)= [3, 2, 1]
근데 여기서 의문이 한가지 생긴다. 자바가 제공하는 Integer, String같은 객체를 제외하고 내가 직접 만든 객체(User, Team 등)도 정렬하고 싶을수 있다. 이럴땐 어떻게 할까? 내가 만든 객체이기 때문에 정렬을 할 때 내가 만든 객체의 두 인스턴스 중에 어떤 인스턴스가 더 큰지 알려줄 방법이 있어야 한다. 이때는 내가 만든 객체가 Comparable 인터페이스를 구현하면 된다. 이 인터페이스는 이름 그대로 비교 가능한, 비교할 수 있는 이라는 뜻으로 객체에 비교 기능을 추가해준다.
Comparable을 구현한 클래스
다음과 같은 클래스를 직접 만들었다고 생각해보자.
MyUser
package org.example.collection.compare;
public class MyUser {
private String id;
private int age;
public MyUser(String id, int age) {
this.id = id;
this.age = age;
}
public String getId() {
return id;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return "MyUser{" +
"id='" + id + '\'' +
", age=" + age +
'}';
}
}
이 클래스를 두고 나이 기준으로 정렬을 하고 싶으면 이 클래스가 Comparable을 구현하면 된다.
Comparable을 구현한 MyUser
package org.example.collection.compare;
public class MyUser implements Comparable<MyUser> {
private String id;
private int age;
public MyUser(String id, int age) {
this.id = id;
this.age = age;
}
public String getId() {
return id;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return "MyUser{" +
"id='" + id + '\'' +
", age=" + age +
'}';
}
@Override
public int compareTo(MyUser o) {
// 오름차순
return this.age < o.age ? -1 : this.age > o.age ? 1 : 0;
}
}
그럼 별도의 Comparator없이도 정렬이 가능하다. 내가 정렬 기준을 제시해줬기 때문에.
SortMain2 (Comparable을 구현한 클래스를 정렬할때)
package org.example.collection.compare;
import java.util.Arrays;
import java.util.Comparator;
public class SortMain2 {
public static void main(String[] args) {
MyUser myUser1 = new MyUser("a", 30);
MyUser myUser2 = new MyUser("b", 20);
MyUser myUser3 = new MyUser("c", 10);
MyUser[] users = {myUser1, myUser2, myUser3};
System.out.println("기본 데이터");
System.out.println(Arrays.toString(users));
System.out.println("나이 기준 오름차순 정렬 데이터");
Arrays.sort(users); // MyUser 클래스가 Comparable을 구현한 경우
System.out.println(Arrays.toString(users));
}
}
실행결과
기본 데이터
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
나이 기준 오름차순 정렬 데이터
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]
실행결과를 보니 나이 기준으로 오름차순 정렬이 됐다. 근데 꼭 이렇게 Comparable을 구현해야 할까? 아니다. 그럴 필요 없다. 그냥 두번째 인자에 나만의 Comparator를 던져주면된다.
SortMain2 (Comparable을 구현하지 않고 Comparator를 두번째 인자로 준 경우)
package org.example.collection.compare;
import java.util.Arrays;
import java.util.Comparator;
public class SortMain2 {
public static void main(String[] args) {
MyUser myUser1 = new MyUser("a", 30);
MyUser myUser2 = new MyUser("b", 20);
MyUser myUser3 = new MyUser("c", 10);
MyUser[] users = {myUser1, myUser2, myUser3};
Arrays.sort(users, Comparator.comparing(MyUser::getId)); // Comparable 구현이랑 상관없이, 직접 Comparator를 만든 경우
System.out.println(Arrays.toString(users));
}
}
두번째 인자로 Comparator를 람다 표현식의 익명 내부 클래스로 만들어서 던져줬다. (구현할 인터페이스가 딱 한개의 메서드만 가진 경우 익명 내부 클래스를 람다 표현식으로 작성할 수 있다)
참고로, 저 람다 표현식의 익명 내부 클래스는 이 클래스를 만든거랑 똑같다고 보면 된다.
package org.example.collection.compare;
import java.util.Comparator;
public class IdComparator implements Comparator<MyUser> {
@Override
public int compare(MyUser o1, MyUser o2) {
return o1.getId().compareTo(o2.getId()); //오름차순
}
}
그래서 저 위의 코드를 바꾸면 이렇게 되는거다.
Arrays.sort(users, new IdComparator());
보면 MyUser가 가진 `id`를 기준으로 오름차순 정렬을 한다. 자바에서 문자를 오름차순 정렬하기 편하게 compareTo()를 구현해놨고 그거를 그대로 사용한다고 보면 된다. 그리고 만약 내가 `id`를 기준으로 내림차순 정렬하고 싶으면? 이렇게 쓰면 된다.
Arrays.sort(users, new IdComparator().reversed());
중요
그래서, 중요한건 내가 만든 클래스를 정렬할 때 그 클래스가 Comparable을 구현한 클래스라면 그 클래스의 compareTo() 메서드를 가지고 정렬을 한다. 그게 아니라면 두번째 인자로 Comparator를 던져주어 내 입맛에 맞게 정렬한다. 둘 다 아니라면? 런타임 에러가 발생한다.
List와 정렬
정렬은 배열 뿐만 아니라 순서가 있는 List같은 자료 구조에도 사용할 수 있다.
SortMain3
package org.example.collection.compare;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
public class SortMain3 {
public static void main(String[] args) {
MyUser myUser1 = new MyUser("a", 30);
MyUser myUser2 = new MyUser("b", 20);
MyUser myUser3 = new MyUser("c", 10);
List<MyUser> users = new LinkedList<>();
users.add(myUser1);
users.add(myUser2);
users.add(myUser3);
System.out.println("기본 데이터");
System.out.println(users);
System.out.println("Comparable 기본 정렬");
users.sort(null); // Comparator를 만들어서 넣어주는게 아니고 Comparable 구현한 그대로로 정렬한다는 뜻
System.out.println(users);
System.out.println("Comparator로 정렬");
users.sort(Comparator.comparing(MyUser::getId)); // 첫번째 방법: 람다 익명 내부 클래스
users.sort(new IdComparator()); // 두번째 방법: Comparator를 구현한 클래스
System.out.println(users);
}
}
실행결과
기본 데이터
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
Comparable 기본 정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]
Comparator로 정렬
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
배열과 다르지 않다. Comparable을 구현한 클래스이고 그 정렬 기준 그대로를 사용한다면 List가 자체적으로 가지고 있는 sort()메서드에 아무것도 넣지 않는다는 의미로 `null`을 넣으면 된다.
그게 아니라 내가 원하는 방식의 다른 정렬을 원한다면 Comparator를 직접 만들어 넣으면 된다.
근데 저 방법 말고 다른 방법이 하나 더 있긴한데 이건 권장되지 않고 저 방식대로 사용하면 된다. 알기는 알아야 하니까 작성하자면,
Collections.sort(users);
Collections.sort(users, new IdComparator());
Collections.sort(users, Comparator.comparing(MyUser::getId));
Collections 를 사용해도 된다. 근데 보면 알겠지만 이런 `Warning` 문구를 보여준다.
Tree와 정렬
TreeSet과 같은 이진 탐색 트리 구조는 데이터를 보관할 때 데이터를 정렬하면서 보관한다.
이렇게 생긴 이진 탐색 트리가 있다고 하면, 내가 여기에 6을 넣으려고 하면 아무곳에 넣을 수 있는게 아니라 정렬해서 6의 정확한 위치가 들어가야 한다. 이진 탐색 트리를 만족해야 하니까. (현재 노드를 기준으로 왼쪽은 무조건 더 작게, 오른쪽은 무조건 더 크게)
그 말은 TreeSet, TreeMap같은 자료 구조는 Comparable이나 Comparator가 필수이다.
SortMain4
package org.example.collection.compare;
import java.util.TreeSet;
public class SortMain4 {
public static void main(String[] args) {
MyUser myUser1 = new MyUser("a", 30);
MyUser myUser2 = new MyUser("b", 20);
MyUser myUser3 = new MyUser("c", 10);
TreeSet<MyUser> treeSet = new TreeSet<>();
treeSet.add(myUser1);
treeSet.add(myUser2);
treeSet.add(myUser3);
System.out.println("Comparable 기본 정렬");
System.out.println(treeSet);
}
}
MyUser는 Comparable을 구현한 클래스이다. 그래서 TreeSet의 요소 타입으로 받아들일 수 있다. 그냥 트리에 데이터를 넣는순간 정렬이 된다. 진짜 그런지 실행결과를 보자.
실행결과
Comparable 기본 정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]
알아서 나이의 오름차순(MyUser에서 구현한 정렬방식)으로 찍히는걸 볼 수 있다.
그럼 Comparable을 구현한 클래스가 아니라면 Comparator를 반드시 줘야 하는데 어떻게 주면 될까?
TreeSet<MyUser> treeSet2 = new TreeSet<>(new IdComparator());
이렇게 생성자에 Comparator를 넘겨주면 된다.
그래서 결론은 자바에서 트리 구조는 반드시 Comparable이나 Comparator가 필수라는 사실. 진짜 그런지 궁금한데 한번 해보자.
우선 MyUser가 Comparable을 구현한 클래스가 아니게 바꿨다.
MyUser (Comparable 구현 안 함)
package org.example.collection.compare;
public class MyUser {
private String id;
private int age;
public MyUser(String id, int age) {
this.id = id;
this.age = age;
}
public String getId() {
return id;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return "MyUser{" +
"id='" + id + '\'' +
", age=" + age +
'}';
}
}
그랬더니 벌써부터 경고문구가 보인다.
실행해보면? 런타임 에러가 발생한다.
결론
Integer, String 뿐 아니라 내가 직접 만든 클래스 또한 Array, List, Tree 자료구조에서 모두 내가 원하는 방식으로 정렬을 할 수 있다. 크게 두 가지 방법이 있다.
우선, Iterable, Iterator를 다루기 앞서 자료 구조를 순회한다는 것에 대해 이해해보자.
순회라는 것은 여러 곳을 돌아다닌다는 뜻이다. 자료 구조에서 순회는 자료 구조에 들어있는 데이터를 차례대로 접근해서 처리하는 것을 순회라고 한다. 그런데 다양한 자료구조가 있고, 각각의 자료 구조마다 데이터를 접근하는 방법이 전부 다르다.
예를 들어보자.
배열의 경우 index를 size까지 차례대로 증가하면서 순회해야 하고, 연결 리스트는 node.next를 사용해서 node의 끝이 null일 때까지 순회해야 한다. 이렇듯 각 자료 구조의 순회 방법이 다르다. 근데 자료 구조는 이 뿐만이 아니라 HashSet, LinkedHashSet, TreeSet 등등 다양한 자료구조가 있다. 각각의 자료 구조마다 순회하는 방법이 다 다르기 때문에 자료 구조마다 순회 방법을 배워야 한다. 순회 방법을 알려면 각각의 자료 구조의 내부 구조도 알아야 한다. 결과적으로 너무 많은 것을 알아야 하는 것이다. 그러나 자료 구조를 사용하는 개발자 입장에서는 단순히 자료 구조에 들어있는 모든 데이터에 순서대로 접근해서 출력하거나 계산하고 싶을 뿐이다.
그래서, 자료 구조의 구현과 관계 없이 모든 자료 구조를 동일한 방법으로 순회할 수 있는 일관성 있는 방법이 있다면, 자료 구조를 사용하는 개발자 입장에서는 매우 편리할 것이다.
자바는 이런 문제를 해결하기 위해 Iterable, Iterator 인터페이스를 제공한다.
Iterable: '반복 가능한' 이라는 뜻이다.
public interface Iterable<T> {
Iterator<T> iterator();
}
Iterator: '반복자'라는 뜻이다.
public interface Iterator<E> {
boolean hasNext();
E next();
}
hasNext(): 다음 요소가 있는지 확인한다. 다음 요소가 없으면 `false`를 반환한다.
next(): 다음 요소를 반환한다. 내부에 있는 위치를 다음으로 이동한다.
직접 Iterator, Iterable 만들어보기
Iterator, Iterable을 사용하는 자료 구조를 하나 만들어보자. 둘 다 인터페이스여서 구현체가 필요하다.
MyArray (우리가 종종 사용하는 ArrayList와 비교해서 생각해보기)
package org.example.collection.iterable;
import java.util.Iterator;
public class MyArray implements Iterable<Integer> {
private int[] numbers;
public MyArray(int[] numbers) {
this.numbers = numbers;
}
@Override
public Iterator<Integer> iterator() {
return new MyArrayIterator(numbers);
}
}
MyArrayIterator
package org.example.collection.iterable;
import java.util.Iterator;
public class MyArrayIterator implements Iterator<Integer> {
private int currentIndex = -1;
private int[] targetArr;
public MyArrayIterator(int[] targetArr) {
this.targetArr = targetArr;
}
@Override
public boolean hasNext() {
return currentIndex < targetArr.length - 1;
}
@Override
public Integer next() {
return targetArr[++currentIndex];
}
}
설명
Iterable을 구현하는 구현체는 `iterator`라는 메서드를 재정의해야 한다.
Iterator를 구현하는 구현체는 hasNext(), next() 메서드를 재정의한다.
Iterable을 구현하는 구현체는 내부에 자료 구조를 가지고 있고 그 자료 구조를 iterator에게 넘겨준다.
iterator를 구현하는 구현체는 넘겨받은 자료 구조의 참조값을 가지며 그 참조값을 통해 자료 구조를 순회할 수 있다.
iterator를 구현하는 구현체는 넘겨받는 자료 구조가 Array인지, Tree인지, HashSet인지에 따라 전부 가져야하는 필드가 달라진다. 위의 경우 Array에 대한 iterator이기 때문에 인덱스와 배열을 가진다.
iterator를 구현하는 구현체는 넘겨받는 자료 구조가 Array인 경우, hasNext() 메서드에서 넘겨받은 자료 구조의 사이즈보다 현재 인덱스가 작은지를 비교해서 다음 데이터가 존재하는지 판단한다.
iterator를 구현하는 구현체는 넘겨받는 자료 구조가 Array인 경우, next() 메서드에서 다음 데이터를 반환하기 위해 현재 index + 1을 한 index의 데이터를 반환한다.
직접 만든 iterable, iterator 사용해보기
package org.example.collection.iterable;
import java.util.Iterator;
public class MyArrayMain {
public static void main(String[] args) {
MyArray myArray = new MyArray(new int[]{1, 2, 3, 4});
Iterator<Integer> iterator = myArray.iterator();
System.out.println("iterator 사용");
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
실행결과
iterator 사용
1
2
3
4
향상된 for 문의 비밀
향상된 for문은 정말 많이 사용하는 자료 구조를 순회하는 방법이다. 근데 이게 재밌는 사실이 있다.
MyArrayMain
package org.example.collection.iterable;
public class MyArrayMain {
public static void main(String[] args) {
MyArray myArray = new MyArray(new int[]{1, 2, 3, 4});
for (Integer i : myArray) {
System.out.println("i = " + i);
}
}
}
실행결과
i = 1
i = 2
i = 3
i = 4
당연히 잘 된다. 근데 만약에 MyArray 클래스에서 Iterable을 구현하지 않으면 어떻게 될까?
package org.example.collection.iterable;
public class MyArray {
private int[] numbers;
public MyArray(int[] numbers) {
this.numbers = numbers;
}
}
이렇게 Iterable을 구현하겠다는 키워드와 iterator() 메서드를 재정의한 것을 빼버렸다.
컴파일 오류가 난다. 에러 메시지는 다음과 같다.
required: array or java.lang.Iterable
그렇다. 향상된 for문을 사용하려면 배열 그 자체이거나 Iterable을 구현해야 한다. 그러니까 돌려서 말하면 모든 향상된 for문을 사용할 수 있었던 자료구조는 다 Iterable을 구현한 구현체고 `iterator()` 메서드가 반환하는 Iterator가 있다는 사실이다.
그래서 향상된 for문은 컴파일이 되면 다음과 같은 모양으로 변경이 된다.
컴파일 전
for (Integer i : myArray) {
System.out.println("i = " + i);
}
컴파일 후
while (iterator.hasNext()) {
System.out.println("i = " + iterator.next());
}
향상된 for문이 워낙 깔끔하고 사용하기 좋다 보니 저렇게 사용을 많이 하지만 이러한 과정이 있다는 사실을 알아두면 좋을 것 같다.
자바가 제공하는 Iterable, Iterator
이제 Iterable, Iterator가 뭔지 알게됐다. 위에서 말했지만 각 자료 구조마다 순회하는 방식이 다르니까 Iterator의 생김새도 달라진다고 했다. 근데 결정적인건 그걸 사용하는 개발자 입장에서는 알 필요가 없다는 것이다. 이렇게 순회 가능한 자료 구조에 대해 Iterable, Iterator를 구현해서 내부 구조에 대해 깊이 있게 알지 못해도 순회할 수 있는 디자인 패턴을 Iterator패턴이라고 한다.
위 그림에서 알 수 있듯 Collection 인터페이스는 Iterable 인터페이스를 상속한다. 그렇기 때문에 Collection 하위에 있는 모든 구현체는 향상된 for문을 사용할 수 있고 그 말은 각각이 전부 iterator() 메서드를 재정의했다는 말이다.
근데, Map은 보니까 아예 동떨어져 있다. Map을 향상된 for문으로 돌릴 수 없는 이유가 여기에 있다. Map은 순회의 개념이 아니라 Key-Value 쌍을 저장하는 자료구조이기 때문에 그렇다. 이렇게 공부를 하고 나니까 뭔가 전체적인 그림이 눈에 들어오기 시작했다.
그럼 개발할 때 종종 사용했던 ArrayList, HashSet 같은 녀석들의 iterator를 한번 사용해보자.
JavaIterableMain
package org.example.collection.iterable;
import java.util.*;
public class JavaIterableMain {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> iterator = list.iterator();
printAll(iterator);
forEach(list);
Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(3);
Iterator<Integer> iterator1 = set.iterator();
printAll(iterator1);
forEach(set);
}
private static void forEach(Iterable<Integer> iterable) {
System.out.println("iterable = " + iterable.getClass());
for (Integer i : iterable) {
System.out.println(i);
}
}
private static void printAll(Iterator<Integer> iterator) {
System.out.println("iterator = " + iterator.getClass());
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
실행결과
iterator = class java.util.ArrayList$Itr
1
2
3
iterable = class java.util.ArrayList
1
2
3
iterator = class java.util.HashMap$KeyIterator
1
2
3
iterable = class java.util.HashSet
1
2
3
이게 또 자바의 다형성에서 얻는 이점이다. 내부적으로 어떤 iterator가 들어오던 상관없이 Iterator를 구현한 구현체라면 같은 메서드를 사용할 수 있다. 그래서 실행 결과를 보면 하나는 ArrayList의 iterator, 하나는 HashMap의 KeyIterator다. Set은 내부적으로 Map을 사용한다고 했다. Map의 Key가 해시 기반의 셋 자료 구조라서 그렇다.
그리고 또 향상된 for문 역시 Iterable을 구현한 구현체면 사용할 수 있다. 그래서 어떤 구현체이든 상관없이 Iterable을 구현했다면 향상된 for문을 사용할 수 있는것이다. 이게 바로 다형성이 주는 강력한 이점이라고 할 수 있다.
이제 Deque라는 자료구조를 알아보자. 왜 Stack, Queue를 Deque로 사용할 수 있을까?
우선, Deque는 "Double Ended Queue"의 약자로 이름에서 알 수 있듯 양쪽 끝에서 요소를 추가하거나 제거할 수 있다. 그래서 큐와 스택의 기능을 모두 포함하고 있어 매우 유연한 자료구조이다. 보통 '덱'이라고 많이 불린다.
Deque의 구조
Queue에서는 전통적으로 넣을 때 `offer` 라는 단어를 사용하고 꺼낼 때 `poll`이라는 단어를 사용한다.
이 Deque가 결국 DE`Queue`이기 때문에 역시 같은 단어를 사용한다. 근데 Stack의 기능도 가질 수 있기 때문에 Stack에서 전통적으로 넣을 때 `push`라는 단어를 사용하고 꺼낼 때 `pop`이라는 단어를 사용하는데 이 메서드또한 Deque는 지원한다.
`offerFirst()`: 앞에 추가한다.
`offerLast()`: 뒤에 추가한다.
`pollFirst()`: 앞에서 꺼낸다.
`pollLast()`: 뒤에서 꺼낸다.
결국 이 Deque로 Stack, Queue를 모두 해결할 수 있기 때문에 이 자료구조를 사용하면 된다. 그리고 또한 Deque의 대표적인 구현체로 `ArrayDeque`와 `LinkedList`가 있는데 이 `ArrayDeque`가 성능상으로도 훨씬 유리하기 때문에 그냥 ArrayDeque를 Stack이나 Queue자료구조를 사용해야 할 때 사용하면 된다.
키는 맵 내에서 유일하다는 것은 중복이 불가능하단 얘기고 이 말이 꼭 Set과 유사하다. 맞다. Map의 키는 Set으로 이루어져 있다. 그래서 Map의 모든 키 목록을 조회하는 keySet()을 호출하면 중복을 허용하지 않는 자료 구조인 Set을 반환한다.
Set<String> keySet = yourMap.keySet();
그리고 Map의 구현체는 대표적으로 HashMap, LinkedHashMap, TreeMap이 있다. "어? 이거도 어디서 많이 봤는데요?" 맞다. Set을 만들때 봐왔다. 사실 자바에서 HashSet은 HashMap 을 가져다가 사용한다. 그래서 Map은 직접 구현해 볼 필요가 없다. 이미 Set을 하면서 해봤다.
그리고 `값`은 중복이 될 수 있는데 순서를 유지하지 않는다고 한다는 것은 Set도 List도 아니란 얘기다. Set은 중복이 불가능하고 List는 순서를 유지하니까. 그래서 Map의 모든 값을 조회하는 values()를 호출하면 단순히 값의 모음이라는 의미의 상위 인터페이스인 Collection으로 반환한다.
그래서 Map에서 중요한건 Map은 `키`가 중복이 불가능한 유일한 값만이 들어있다는 얘기다. 그리고 맵 역시 해시 알고리즘을 사용하는데 그 말은 Map에서 키로 사용하는 객체는 반드시 equals()와 hashCode()를 재정의해야 한다는 것이다.
Set은 중복된 값을 방지할 수 있는 좋은 자료구조이다. 그리고 해당 값이 있는지 빠르게 찾아낼 수 있는 방법을 가지고 있다.
어떻게 중복을 방지하고 값의 존재 유무를 빠르게 알아낼 수 있는지 직접 구현해 보면서 알아보자.
우선 가장 첫 번째 고민거리로, 배열이란 것을 생각해 볼 때 배열의 조회는 O(1)의 시간복잡도를 가진다. 인덱스로 한 번에 해당 메모리에 접근해서 값을 꺼내올 수 있으니 말이다. 그럼 배열에서 탐색은 O(n)의 시간복잡도를 가진다. 왜냐하면 원하는 값이 어디 있는지 모르니까 하나씩 순회하면서 찾아야 하니 말이다.
이 말을 반대로 생각해 보면 배열에서 탐색을 O(1)의 시간복잡도로 갖게 하려면 저장하려는 값과 인덱스값이 일치하면 되지 않을까?
저장하려는 값과 인덱스 값을 일치시켜 탐색을 O(1)의 시간 복잡도로
인덱스를 통해 찾아가는 건 O(1)이니까 원하는 값과 인덱스가 일치하면 원하는 값을 탐색하는 것도 O(1)으로 해결할 수 있게 된다.
굉장히 좋은 생각 같지만 만약에 데이터가 (1, 2, 5, 8, 90) 5개인 경우를 생각해 보면 데이터는 고작 5개지만 배열의 크기는 91이어야 한다. 인덱스 90을 수용하려면 91개의 공간이 필요하기 때문에. 그래서 탐색 성능은 높아지지만 메모리의 낭비가 심해진다.
메모리 낭비를 나머지 연산으로 해결
이것을 효율적으로 해결하는 방법은 정해진 사이즈에서 적당한 자리를 찾을 수 있도록 나머지 연산을 사용하는 것이다.
이렇게 나머지 연산으로 얻어낸 결과를 해시라고 하자. (이후에 해시코드라는 것으로 이 비슷한 알고리즘을 구현해 낼 거라서 그렇다.)
1, 2, 5, 8, 90 5개의 데이터를 보관하기 위해서 10개의 공간을 가지는 배열을 만들었다고 가정해 보자.
그럼 그 10개라는 공간으로 각 데이터를 나눈 나머지를 구해보는 것이다.
1 % 10 = 1
2 % 10 = 2
5 % 10 = 5
8 % 10 = 8
99 % 10 = 9
이렇게 나머지 연산을 통해 적절한 자리를 찾게 해서 배열의 사이즈로 인한 메모리 낭비도 줄이고 탐색할 때 시간도 최대한으로 끌어올릴 수 있을 것 같다. 결국 탐색을 위해서 필요한 연산은 나머지 연산 하나이고 그 나머지 연산의 결과로 얻어낸 인덱스를 바로 찾아가면 내가 원하는 값을 찾을 수 있으니까 말이다.
근데 여기에는 치명적인 단점이 있다. 나머지 연산에 충돌이 일어난다는 것. 9 % 10 = 9, 99 % 10 = 9 이다.
이 경우에는 어떻게 하면 좋을까? 그러니까 상황을 생각해 보면 데이터 9가 이미 들어가 있는 상태이고, 데이터 99를 추가적으로 넣으려고 했더니 나머지 연산의 결과가 똑같이 9가 나와서 인덱스 9번으로 갔더니 이미 데이터가 있는 상황이다. 이 경우엔 그냥 그 자리에 같이 넣어버리면 된다. 다음 그림처럼 말이다.
그럼 이 상태에서 99를 탐색할 땐 어떻게 할까?
99를 탐색하겠다고 해시값을 구하면 결과는 9다.
인덱스 9번을 갔더니 값이 여러 개가 존재한다.
하나씩 비교해서 찾아낸다.
이렇게 해시값과 Set이라는 자료 구조를 통해 연산 시 시간 복잡도는 어떻게 될까?
탐색
시간복잡도는 평균적으로 O(1), 최악의 경우 O(n).
해시 충돌이 일어나지 않는다면, 찾고자 하는 값으로 해시값을 구하기 O(1), 해당 해시값에 저장된 값 꺼내기 O(1).
모든 값이 전부 다 해시 충돌이 일어나서 하나의 인덱스에만 데이터가 들어간 경우 해시값 구하기 O(1), 해당 인덱스에서 원하는 값 찾아내기 O(n).
추가
시간복잡도는 평균적으로 O(1), 최악의 경우 O(n).
해시 충돌이 일어나지 않는다면, 추가하려는 값으로 해시값 구하기 O(1), 해당 해시값을 인덱스로 데이터 넣기 O(1).
해시 충돌이 빈번하게 일어나는 경우, 추가하려는 값으로 해시값 구하기 O(1), 해당 해시값을 인덱스로 하여 해당 메모리에 데이터를 넣기 위해 기존에 같은 데이터가 있는지 확인하는 탐색작업 O(n), 데이터 넣기 O(1)
그래서 결론은 일반적으로 O(1)으로 생각하면 된다.
그럼 이런 내용을 토대로 한번 직접 HashSet을 구현해보자.
MyHashSetV1
package org.example.collection.set;
import java.util.Arrays;
import java.util.LinkedList;
public class MyHashSetV1 {
static final int DEFAULT_INITIAL_CAPACITY = 16;
LinkedList<Integer>[] buckets;
private int size;
private int capacity = DEFAULT_INITIAL_CAPACITY;
public MyHashSetV1() {
initBuckets(capacity);
}
public MyHashSetV1(int capacity) {
this.capacity = capacity;
initBuckets(capacity);
}
private void initBuckets(int capacity) {
buckets = new LinkedList[capacity];
for (int i = 0; i < capacity; i++) {
buckets[i] = new LinkedList<>();
}
}
public boolean add(int value) {
int hashIndex = hashIndex(value);
LinkedList<Integer> bucket = buckets[hashIndex];
if (bucket.contains(value)) {
return false;
}
bucket.add(value);
size++;
return true;
}
public boolean contains(int searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<Integer> bucket = buckets[hashIndex];
return bucket.contains(searchValue);
}
public boolean remove(int value) {
int hashIndex = hashIndex(value);
LinkedList<Integer> bucket = buckets[hashIndex];
boolean removed = bucket.remove(Integer.valueOf(value));
if (removed) {
size--;
return true;
}
return false;
}
public int getSize() {
return size;
}
@Override
public String toString() {
return "MyHashSetV1{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
", capacity=" + capacity +
'}';
}
private int hashIndex(int value) {
return value % capacity;
}
}
우선, Set에서 자료를 담을 자료구조는 LinkedList의 배열을 선택한다. LinkedList<Integer>[] buckets;
그리고 기본 크기는 16으로 설정했는데 이는 원하는 값을 생성자에서 받을 수도 있고 그대로 사용할 수도 있다.
생성자로부터 이 HashSet의 객체가 만들어지면, 각 인덱스별 LinkedList를 초기화한다.
add(int value): 데이터를 저장하는 메서드. 해시값을 구하고 그 해시값을 인덱스로 배열의 위치를 결정한다. 그리고 그 위치에 저장된 LinkedList안에 저장하고자 하는 데이터가 있는지 판단한다. Set의 특성상 있다면 저장하지 않고 없다면 저장한다.
contains(int searchValue): 찾고자 하는 값이 존재하는지 판단하는 메서드. 해시값을 구하고 그 해시값을 인덱스로 배열의 위치를 결정한다. 그 위치에 저장된 LinkedList안에 찾고자 하는 데이터가 존재하는지 확인한다.
remove(int value): 데이터를 지우는 메서드. 해시값을 구하고 그 해시값을 인덱스로 배열의 위치를 결정한다. 그 위치에 저장된 LinkedList안에 지우고자 하는 데이터를 찾아 (있다면) 지운다.
getSize(): 저장된 전체 데이터의 개수를 반환한다.
hashIndex(int value): 해시값을 구해내는 프라이빗 메서드. 주어진 값을 배열의 크기로 나머지 연산을 통해 해시값을 구한다.
모든 메서드가 전부 해시값을 구하고 그 해시값을 기반으로 데이터를 찾고, 저장하고, 삭제한다. 즉,가장 핵심이 되는 건 해시값이다.
해시값의 충돌 가능성을 인정하고 충돌이 날 경우 그 공간에 같이 데이터를 보관한다. 그리고 충돌의 확률은 배열의 크기에 따라 조정이 되기 때문에 적당한 충돌 관리를 잘한다면 이렇게 데이터를 잘 저장할 수 있다.
근데, 한 가지 의문이 생긴다. 지금의 구조로는 해시값은 나머지 연산을 통해 숫자를 뱉어낸다. 나머지 연산을 하기 위해선 항의 타입이 무조건 숫자여야 한다. 이것이 지금 구조에서 가장 큰 문제가 된다. 이것을 해결하기 위해 탄생한 게 자바의 hashCode().
자바의 hashCode()
해시 인덱스를 사용하는 해시 자료 구조는 추가, 검색, 삭제의 성능이 O(1)으로 매우 빠르다. 그래서 많은 곳에서 사용된다. 근데 해시 자료 구조를 사용하려면 앞에서 본 것처럼 정수로 된 숫자 값인 해시 코드가 필요한데, 자바에서는 int, Integer 뿐만 아니라 String, char, Double, Boolean 등 수많은 타입이 있다. 그뿐 아니라 개발자가 직접 정의한 Member, User와 같은 사용자 정의 타입도 있다. 이 모든 타입을 해시 자료 구조에 저장하려면 모든 객체가 숫자 해시 코드를 제공할 수 있어야 한다.
모든 타입이 숫자 해시 코드를 제공한다. 모든 타입의 부모 = Object. 그래서 Object가 hashCode()를 가지고 있는 것이다.
hashCode() 특징은 다음과 같다.
equals() 메서드처럼 재정의해야 한다.
왜냐하면, 기본으로 제공되는 hashCode()는 참조값으로 해시값을 구하기 때문에 인스턴스가 다르면 다른 해시값을 반환해 버린다. IDE의 도움을 받아 hashCode() 재정의 하는 것은 너무 간단하다.
equals()와 hashCode()는 같이 재정의해야 한다.
결국 해시 기반 자료 구조에서 사용되는 가장 중요한 값인 해시값이 같다는 것은 논리적으로 같음을 의미한다. 그래서 equals()에서 논리적으로 같음을 판단하는 기준이 되는 모든 것들을 hashCode()에도 적용해줘야 한다. equals()만 재정의하고 hashCode()를 재정의하지 않으면 hashCode()는 Object가 기본으로 가지고 있는 hashCode()를 사용하는데 이때 사용하는 기준이 참조값뿐이기 때문에 equals()가 동일하다고 판단했음에도 hashCode()가 달라지는 문제가 생긴다. 그 결과 해시 기반 구조를 사용하는데 equals()만 재정의하고 hashCode()는 재정의하지 않는다면 논리적으로 같은 객체임에도 다른 해시값을 반환해 버려서 검색, 추가, 삭제 모든 연산에 문제가 생긴다. 물론 이 객체에 대해 해시 기반 자료 구조를 사용 안 하면 equals()만 재정의해도 크게 문제는 없다.
equals()가 같다고 판단한 두 객체는 hashCode() 값이 무조건 같아야 하고 그 반대는 성립되지 않는다.
equals()가 같다고 판단한 두 객체는 논리적으로 같음을 의미한다. 그 얘기는 해시 기반 자료구조에서 자료를 저장할 때 이 두 객체는 무조건 같다는 판단이 나와야 한다. 근데 반대는? 해시 충돌이 일어났을 때 두 값이 같지 않아도 충돌은 일어날 수 있다.
이제 hashCode()에 대해서는 어느 정도 알아봤고 이 hashCode()를 사용해서 Set이라는 자료구조를 만들어 내보자.
MyHashSetV2
package org.example.collection.set;
import java.util.Arrays;
import java.util.LinkedList;
public class MyHashSetV2 {
static final int DEFAULT_INITIAL_CAPACITY = 16;
private LinkedList<Object>[] buckets;
private int size;
private int capacity = DEFAULT_INITIAL_CAPACITY;
public MyHashSetV2() {
initBuckets(capacity);
}
public MyHashSetV2(int capacity) {
this.capacity = capacity;
initBuckets(capacity);
}
private void initBuckets(int capacity) {
buckets = new LinkedList[capacity];
for (int i = 0; i < capacity; i++) {
buckets[i] = new LinkedList<>();
}
}
public boolean add(Object value) {
int hashIndex = hashIndex(value);
LinkedList<Object> bucket = buckets[hashIndex];
if (bucket.contains(value)) {
return false;
}
bucket.add(value);
size++;
return true;
}
public boolean contains(Object searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<Object> bucket = buckets[hashIndex];
return bucket.contains(searchValue);
}
public boolean remove(Object value) {
int hashIndex = hashIndex(value);
LinkedList<Object> bucket = buckets[hashIndex];
boolean removed = bucket.remove(value);
if (removed) {
size--;
return true;
}
return false;
}
public int getSize() {
return size;
}
@Override
public String toString() {
return "MyHashSetV2{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
", capacity=" + capacity +
'}';
}
private int hashIndex(Object value) {
return Math.abs(value.hashCode()) % capacity;
}
}
가장 핵심적으로 바뀌는 부분은 hashIndex(Object value) 메서드이다. 기존에는 저장하고자 하는 모든 데이터를 정수형으로만 취급했기 때문에 상관이 없었지만 정수형뿐만 아니라 모든 타입으로도 이 Set이라는 자료구조는 자료를 담을 수 있어야 한다. 그런데 그때 해시값을 구하는 메서드가 hashCode()가 되는 것이다.
근데 자세히 보면, Math.abs(value.hashCode()) % capacity; 이렇게 되어 있다. 이 이유는 hashCode()는 음수가 나올 수 있기 때문이다. 하지만, 배열에서는 음수값인 인덱스는 없으니까 절댓값을 사용해야 한다.
그럼 이제 대표적으로 add() 메서드를 주의 깊게 봐보자.
public boolean add(Object value) {
int hashIndex = hashIndex(value);
LinkedList<Object> bucket = buckets[hashIndex];
if (bucket.contains(value)) {
return false;
}
bucket.add(value);
size++;
return true;
}
int hashIndex = hashIndex(value); : 먼저 넣고자 하는 값의 해시값을 구한다.
LinkedList<Object> bucket = buckets[hashIndex]; : 그 해시값으로 배열의 특정 인덱스를 선택하게 된다. 그래서 해당 인덱스로 가보면 LinkedList가 있다.
if (bucket.contains(value)) : 그 LinkedList에서 내가 추가하고자 하는 값이 있는지를 확인한다. 이 contains() 메서드 내부적으로 equals()를 사용할 거다.
이미 있다면 추가하지 않고 `false`를 반환하고 없다면 추가한 후 사이즈를 하나 증가한 후 `true`를 반환한다.
결론은 해시 기반 자료 구조를 사용하려면 반드시 hashCode(), equals() 동시에 재정의해야 한다. hashCode()는 해당 객체에 대한 해시코드를 반환한다. 근데 그 해시코드를 만들어내는 기준들이 equals()가 논리적으로 동등하다고 판단하는 모든 기준들과 일치해야 한다. 그래야 인스턴스가 달라도 논리적으로 같으면 같은 해시코드를 내뱉을 것이고 그래야 이미 그 데이터가 자료구조에 저장이 되어 있는지 판단할 수 있다. 그리고 여기서 판단은? equals() 메서드로 하게 된다. 그렇기 때문에 해시 기반 자료 구조에서 검색, 추가, 삭제와 같은 작업을 정상적으로 수행하려면 hashCode(), equals() 둘 다 오버라이딩 해야 한다는 것.
참고로, String, Boolean, Double 이런 래퍼 클래스는 자바가 미리 equals()와 hashCode()를 우리 대신 다 구현해놨다.
이제 모든 타입을 받아줄 수 있는 HashSet을 직접 만들어 봤다. 만들어 놓고 나니 왜 hashCode()와 equals()를 IDE의 도움을 받아 만들 때 같이 만들어지는지 알게 됐고, 어떻게 해서 해시값을 활용해서 데이터를 저장하고 검색하는지 알게 됐다. 여기에 하나 더, 이렇게 해시값을 이용하면 굉장히 성능이 좋은 자료구조가 된다는 것도.
equals()와 hashCode()를 제대로 구현하지 않았을 때 발생하는 문제 확인해보기
말만 하면 이해가 잘 안되니 직접 이 문제의 상황을 만들어서 어떤 문제가 발생하는지 확인해보자. 경우의 수는 3가지다.
둘 다 구현 안했을 때
equals()만 구현했을 때
hashCode()만 구현했을 때
둘 다 구현 안했을 때
MemberNoHashNoEq
package org.example.collection.set.member;
public class MemberNoHashNoEq {
private String id;
public MemberNoHashNoEq(String id) {
this.id = id;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
@Override
public String toString() {
return "MemberNoHashNoEq{" +
"id='" + id + '\'' +
'}';
}
}
이 클래스는 둘 다 구현하지 않은 케이스이다. 한번 어떻게 되는지 보자.
HashAndEqualsMain1
package org.example.collection.set.member;
import org.example.collection.set.MyHashSetV2;
public class HashAndEqualsMain1 {
public static void main(String[] args) {
MyHashSetV2 set = new MyHashSetV2(10);
MemberNoHashNoEq m1 = new MemberNoHashNoEq("A");
MemberNoHashNoEq m2 = new MemberNoHashNoEq("A");
System.out.println("m1.hashCode() = " + m1.hashCode());
System.out.println("m2.hashCode() = " + m2.hashCode());
System.out.println("m1.equals(m2) = " + m1.equals(m2));
// 중복으로 등록이 된다.
set.add(m1);
set.add(m2);
System.out.println("set = " + set);
MemberNoHashNoEq searchValue = new MemberNoHashNoEq("A");
System.out.println("searchValue.hashCode() = " + searchValue.hashCode());
// 검색에 실패한다.
boolean ifContains = set.contains(searchValue);
System.out.println("set.contains(" + searchValue + ") = " + ifContains);
}
}
Member라는 객체를 만들 때 약속하기를 ID가 같은 객체를 논리적으로 동등한 것으로 판단하기로 했다. 그러나 equals(), hashCode()를 둘 다 구현하지 않았다. 그러고 해시 기반 자료 구조에 저장을 한다면 중복으로 저장된다. Set은 중복으로 저장될 수 없다. 첫번째 문제가 발생한 것.
그리고 문제는 끝나지 않았다. 검색에도 실패한다. 논리적으로 같음에도 hashCode()를 재정의하지 않았기에 다른 해시 코드 결과를 뱉어내고 뱉어낸 해시코드로 해시값을 구해 인덱스로 찾아가도 내가 찾고자하는 객체는 없다. 정말 운이 좋아서 해시 코드 값이 나머지 연산시 동일한 값으로 나왔다고 해도 검색에 실패한다. 왜냐? equals()를 재정의하지 않았으니까.
hashCode()만 구현했을 때
이번엔 equals()를 구현하지 않고 hashCode()만 구현했을 때를 보자.
MemberOnlyHashCode
package org.example.collection.set.member;
import java.util.Objects;
public class MemberOnlyHashCode {
private String id;
public MemberOnlyHashCode(String id) {
this.id = id;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
@Override
public int hashCode() {
return Objects.hashCode(getId());
}
@Override
public String toString() {
return "MemberOnlyHashCode{" +
"id='" + id + '\'' +
'}';
}
}
HashAndEqualsMain2
package org.example.collection.set.member;
import org.example.collection.set.MyHashSetV2;
public class HashAndEqualsMain2 {
public static void main(String[] args) {
MyHashSetV2 set = new MyHashSetV2(10);
MemberOnlyHashCode m1 = new MemberOnlyHashCode("A");
MemberOnlyHashCode m2 = new MemberOnlyHashCode("A");
System.out.println("m1.hashCode() = " + m1.hashCode());
System.out.println("m2.hashCode() = " + m2.hashCode());
System.out.println("m1.equals(m2) = " + m1.equals(m2));
// 중복으로 등록이 된다.
set.add(m1);
set.add(m2);
System.out.println("set = " + set);
MemberOnlyHashCode searchValue = new MemberOnlyHashCode("A");
System.out.println("searchValue.hashCode() = " + searchValue.hashCode());
// 검색에 실패한다.
boolean ifContains = set.contains(searchValue);
System.out.println("set.contains(" + searchValue + ") = " + ifContains);
}
}
이젠 해시코드는 구현했기 때문에 논리적으로 같은 기준이라면 같은 해시코드를 반환한다. 그래서 결과를 보면 m1, m2의 해시코드가 동일하다. 그러니까 당연히 해시값을 통해 구해낸 인덱스는 같은 곳이지만 둘 다 들어간다. 왜냐? equals()를 구현하지 않았기 때문에 Object가 가지고 있는 `==`비교를 하게 된다. 당연히 논리적으로 같아도 참조값은 다르기 때문에 두 객체를 동일하다고 판단하지 않고 둘 다 넣어버리는 것이다. 검색도 마찬가지로 안된다. 역시나 equals()를 구현하지 않았으니까.
equals()만 구현했을 때
마찬가지로 문제가 될 것이다.
MemberOnlyEq
package org.example.collection.set.member;
import java.util.Objects;
public class MemberOnlyEq {
private String id;
public MemberOnlyEq(String id) {
this.id = id;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MemberOnlyEq that = (MemberOnlyEq) o;
return Objects.equals(getId(), that.getId());
}
@Override
public String toString() {
return "MemberNoHashNoEq{" +
"id='" + id + '\'' +
'}';
}
}
HashAndEqualsMain3
package org.example.collection.set.member;
import org.example.collection.set.MyHashSetV2;
public class HashAndEqualsMain3 {
public static void main(String[] args) {
MyHashSetV2 set = new MyHashSetV2(10);
MemberOnlyEq m1 = new MemberOnlyEq("A");
MemberOnlyEq m2 = new MemberOnlyEq("A");
System.out.println("m1.hashCode() = " + m1.hashCode());
System.out.println("m2.hashCode() = " + m2.hashCode());
System.out.println("m1.equals(m2) = " + m1.equals(m2));
// 중복으로 등록이 된다.
set.add(m1);
set.add(m2);
System.out.println("set = " + set);
MemberOnlyEq searchValue = new MemberOnlyEq("A");
System.out.println("searchValue.hashCode() = " + searchValue.hashCode());
// 검색에 실패한다.
boolean ifContains = set.contains(searchValue);
System.out.println("set.contains(" + searchValue + ") = " + ifContains);
}
}
실행 결과를 보면 equals()를 구현했으니 두 객체는 동등하다고 나오지만, 해시코드가 다른 값을 뱉는다. 그 말은 해시값이 달라지고 그 말은 인덱스가 서로 다르기 때문에 equals() 비교자체를 하지 않고 둘 다 넣어버리게 된다. 결국 이 상황도 중복으로 데이터가 저장되고 검색도 안되는 문제가 여전히 생긴다.
결론, 해시 자료구조를 사용한다면 둘 다 꼭 재정의하자.
이제 마지막으로 남은 제네릭을 사용해서 HashSet을 완성시켜보자.
Set 인터페이스
package org.example.collection.set;
public interface MySet<E> {
boolean add(E element);
boolean remove(E element);
boolean contains(E element);
int size();
}
Set 구현 클래스
package org.example.collection.set;
import java.util.Arrays;
import java.util.LinkedList;
public class MyHashSet<E> implements MySet<E>{
private final int DEFAULT_CAPACITY = 16;
private LinkedList<E>[] buckets;
private int size;
private int capacity = DEFAULT_CAPACITY;
public MyHashSet() {
initBucket();
}
public MyHashSet(int capacity) {
this.capacity = capacity;
initBucket();
}
private void initBucket() {
buckets = new LinkedList[capacity];
for (int i = 0; i < capacity; i++) {
buckets[i] = new LinkedList<>();
}
}
private int hash(E element) {
return Math.abs(element.hashCode()) % capacity;
}
@Override
public boolean add(E element) {
int hashIndex = hash(element);
LinkedList<E> bucket = buckets[hashIndex];
if (bucket.contains(element)) {
return false;
}
bucket.add(element);
size++;
return true;
}
@Override
public boolean remove(E element) {
int hashIndex = hash(element);
LinkedList<E> bucket = buckets[hashIndex];
boolean removed = bucket.remove(element);
if (removed) {
size--;
return true;
}
return false;
}
@Override
public boolean contains(E element) {
int hashIndex = hash(element);
LinkedList<E> bucket = buckets[hashIndex];
return bucket.contains(element);
}
@Override
public int size() {
return size;
}
@Override
public String toString() {
return "MyHashSet{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
", capacity=" + capacity +
'}';
}
}
제네릭까지 마무리지어서 완전한 Set을 직접 구현해봤다. 앞으로는 절대 직접 구현할 일 없고 자바가 잘 만들어둔 좋은 Set을 사용하면 된다. 그래도 어떤 동작원리로 어떻게 자료를 저장하는지 직접 구현해보는 게 굉장히 뜻깊은 시간이라고 생각한다.
자바가 제공하는 Set
자바가 제공하는 Set은 크게 3가지가 있다.
HashSet
LinkedHashSet
TreeSet
HashSet은 직접 구현한 Set과 거의 동일하고 추가적인 기능이나 성능 최적화가 훨씬 잘 되어 있는 정도다.
LinkedHashSet은 HashSet이긴 한데 데이터끼리 전과 후를 알고 있다. 말 그대로 `Linked`HashSet인데, 이렇게 만든 이유는 Set은 순서가 보장되지 않는데 이 LinkedHashSet은 순서를 보장해준다.
TreeSet은 Binary Search Tree 구조로 저장되는 Set이다.
그래서 TreeSet을 사용할 경우엔 데이터의 정렬 기준에 맞게 조회한다. 3, 1, 2 이렇게 데이터가 들어가 있으면 1, 2, 3 순서로 조회가 된다는 뜻이다.
보통은 HashSet을 가장 많이 사용하고 Set의 근본 목적인 '중복값을 허용하지 않는다'에 초점을 두기 때문에 순서가 반드시 보장되어야 한다면 Array, List, LinkedHashSet을 사용하는 것이 일반적이다.
ArrayList, LinkedList를 직접 구현해봤더니 공통적으로 사용되는 메서드가 있고 이를 추상화한게 List라는 인터페이스라는 것을 깨달았다. 그래서 항상 사용하길 다음과 같이 사용했구나를 알게됐다.
List<String> list = new ArrayList<>();
한번 List도 직접 인터페이스를 만들고 지금까지 만든 ArrayList, LinkedList를 구현체로 변경해보자.
MyList
package org.example.collection.list;
public interface MyList<E> {
int size();
void add(E e);
void add(int index, E e);
E get(int index);
E set(int index, E e);
E remove(int index);
int indexOf(E e);
}
자바에서 제공하는 List라는 인터페이스를 직접 만들어봤다. 이제 지금까지 직접 만들어본 ArrayList와 LinkedList가 이 인터페이스를 구현하게 만들거다.
MyArrayList
package org.example.collection.list;
import java.util.Arrays;
public class MyArrayList<E> implements MyList<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size;
public MyArrayList() {
this.elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayList(int capacity) {
this.elementData = new Object[capacity];
}
@Override
public int size() {
return size;
}
@Override
public void add(E o) {
if (size == elementData.length) {
elementData = Arrays.copyOf(elementData, elementData.length * 2);
}
elementData[size++] = o;
}
@Override
public void add(int index, E o) {
if (size == elementData.length) {
elementData = Arrays.copyOf(elementData, elementData.length * 2);
}
for (int i = size - 1; i > index; i--) {
elementData[i] = elementData[i - 1];
}
elementData[size++] = o;
}
@SuppressWarnings("unchecked")
@Override
public E remove(int index) {
E oldValue = (E) elementData[index];
for (int i = index; i < size; i++) {
elementData[i] = elementData[i + 1];
}
elementData[size--] = null;
return oldValue;
}
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
return (E) elementData[index];
}
@Override
public E set(int index, E element) {
E oldValue = get(index);
elementData[index] = element;
return oldValue;
}
@Override
public int indexOf(E o) {
for (int i = 0; i < size; i++) {
if (elementData[i].equals(o)) {
return i;
}
}
return -1;
}
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) +
" size = " + size +
", capacity = " + elementData.length;
}
}
MyLinkedList
package org.example.collection.list;
public class MyLinkedList<E> implements MyList<E> {
private Node<E> first;
private int size;
@Override
public int size() {
return size;
}
@Override
public void add(E item) {
Node<E> newNode = new Node<>(item);
if (size == 0) {
first = newNode;
} else {
Node<E> lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
@Override
public void add(int index, E item) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
Node<E> newNode = new Node<>(item);
if (index == 0) {
newNode.next = first;
first = newNode;
} else {
Node<E> prevNode = getNode(index - 1);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
size++;
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> currentNode = getNode(index);
return currentNode.item;
}
@Override
public E set(int index, E item) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> oldNode = getNode(index);
E oldItem = oldNode.item;
oldNode.item = item;
return oldItem;
}
public E remove() {
if (size == 0) {
return null;
}
Node<E> prevLastNode = getNode(size - 2);
E removedItem = prevLastNode.next.item;
prevLastNode.next.item = null;
prevLastNode.next = null;
size--;
return removedItem;
}
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
E oldValue;
if (index == 0) {
Node<E> newFirst = first.next;
oldValue = first.item;
first.item = null;
first = newFirst;
} else {
Node<E> prevNode = getNode(index - 1);
Node<E> removeNode = getNode(index);
oldValue = removeNode.item;
prevNode.next = removeNode.next;
removeNode.next = null;
removeNode.item = null;
}
size--;
return oldValue;
}
@Override
public int indexOf(E item) {
Node<E> x = first;
for (int i = 0; i < size; i++) {
if (x.item.equals(item)) {
return i;
}
x = x.next;
}
return -1;
}
private Node<E> getNode(int index) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node<E> x = first;
builder.append("[");
while (x != null) {
builder.append(x.item);
if (x.next != null) {
builder.append(", ");
}
x = x.next;
}
builder.append("]");
return builder.toString();
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
private static class Node<E> {
E item;
Node<E> next;
public Node(E item) {
this.item = item;
}
@Override
public String toString() {
return item.toString();
}
}
}
이렇게 구현체와 인터페이스를 만들면 어떤 이점이 있을까?
예를 들어, 어떤 Batch 작업을 하는 클래스가 있다고 해보자. 이 클래스는 무수히 많은 데이터를 한번에 어떤 작업을 처리하기 위해 존재하는 클래스인데 그 때 내부적으로 List를 사용한다. 다음 코드를 보자.
BatchProcessor
package org.example.collection.list;
public class BatchProcessor {
private final MyList<Integer> list;
public BatchProcessor(MyList<Integer> list) {
this.list = list;
}
public void process(int size) {
long start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(0, i);
}
long end = System.currentTimeMillis();
System.out.println("크기: " + size + ", 계산 시간: " + (end - start) + "ms");
}
}
이 BatchProcessor라는 클래스는 MyList 타입을 주입받는다. 이렇게 설계해두면 좋은 점이 있다.
의존관계 주입을 통해 의존관계의 결정을 내부에서 하는게 아니라 이후로 미룬다.
이후로 미룬다는 것은 기술(구현체)이 변경되어도 클라이언트 코드는 수정할게 없다.
클라이언트 코드가 수정할게 없다는것은 유지보수성이 좋아진다.
예를 들어, 이 BatchProcessor로 process() 메서드를 실행할 때 내가 주입한 구현체가 ArrayList 였다고 해보자. 다음과 같이 코드를 작성하고 실행을 할 거다.
BatchProcessorMain
package org.example.collection.list;
public class BatchProcessorMain {
public static void main(String[] args) {
MyArrayList<Integer> integerArrayList = new MyArrayList<>();
BatchProcessor batchProcessor = new BatchProcessor(integerArrayList);
batchProcessor.process(100_000);
}
}
근데, 실행해보니 속도가 너무 느리다. 왜냐하면 이 배치 작업은 자료구조의 맨 앞에 데이터를 새로 추가한다. 그러면 ArrayList는 맨 앞에 데이터를 추가하는 작업이 O(n)의 시간복잡도를 가지는데, 주어진 사이즈 개수만큼 루프를 돌리는것 또한 O(n)이다. 즉, O(n^2)의 시간 복잡도를 가지게 되는것이다.
실행결과
크기: 100000, 계산 시간: 15258ms
그래서 자료구조를 이해한다면 맨 앞에 데이터를 계속 추가할 때 유리한 자료구조는 LinkedList 라는 것을 안다. 그럼 어떤것도 변경할 필요없이 주입을 LinkedList로 해주면 끝난다. 왜냐? 다형성과 의존관계 주입 때문이다.
BatchProcessorMain
package org.example.collection.list;
public class BatchProcessorMain {
public static void main(String[] args) {
MyLinkedList<Integer> integerLinkedList = new MyLinkedList<>();
BatchProcessor batchProcessor = new BatchProcessor(integerLinkedList);
batchProcessor.process(100_000);
}
}
실행결과
크기: 100000, 계산 시간: 11ms
속도의 차이가 어마어마하다. 성능은 어마어마하게 증가했지만 클라이언트 코드(BatchProcessor)의 변경은 전혀 없다.
이게 다형성과 의존관계 주입(DI)를 사용할 때 유지보수성의 극대화다.
의존관계 주입에서 핵심은 의존성의 결정을 나중으로 미루는 것에 있다. 유지보수 좋은 코드의 핵심은 기술이 변경되어도 클라이언트 코드의 변경이 없거나 최소화 되는것에 있다. 이 두개가 만나서 이런 시너지를 낼 수 있는것.
이 내용을 좀 더 깊이 알려면 다음 내용을 이해해야 한다.
컴파일 타임 의존관계 / 런타임 의존관계
컴파일 타임: 코드 컴파일 시점을 뜻한다.
런타임: 프로그램 실행 시점을 뜻한다.
컴파일 타임 의존관계라는 건 위에서 말한 의존관계 결정을 나중으로 미루는것과 관련이 있다. 즉, 컴파일 시점에는 다음 코드는 어떤 구현체가 들어올지 알 수가 없다. 그저 추상적인 것(MyList<Integer>)에 의존할 뿐이다.
package org.example.collection.list;
public class BatchProcessor {
private final MyList<Integer> list;
public BatchProcessor(MyList<Integer> list) {
this.list = list;
}
public void process(int size) {
long start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(0, i);
}
long end = System.currentTimeMillis();
System.out.println("크기: " + size + ", 계산 시간: " + (end - start) + "ms");
}
}
근데 이 코드가 실행되는 시점인 런타임 시점에서는 코드가 실행하면서 의존관계가 정해진다. 다음 실행하는 코드를 보자.
package org.example.collection.list;
public class BatchProcessorMain {
public static void main(String[] args) {
MyLinkedList<Integer> integerLinkedList = new MyLinkedList<>();
BatchProcessor batchProcessor = new BatchProcessor(integerLinkedList);
batchProcessor.process(100_000);
}
}
BatchProcessor 클래스에 MyLinkedList 타입의 리스트가 주입된다. 인스턴스가 생성되는 순간에 의존관계가 정해지는 것이다.
그러니까 BatchProcessor <-> MyLinkedList는 이 순간에 서로 의존관계가 된다. 그렇다는건 런타임 의존관계는 계속해서 변경될 수 있다는 의미이다. 저 인스턴스를 생성하는 코드 바로 다음라인에 BatchProcessor에게 LinkedList가 아니라 ArrayList를 주면? 그때부터는 ArrayList <-> BatchProcessor가 서로 의존관계가 된다.
"이 말이 곧 의존관계 결정을 나중으로 미루는 것으로 인해 클라이언트 코드는 의존관계가 변경이 되어도 코드의 변경이 필요없음을 의미한다".
와 이 말 너무 중요한거 같다. 의존관계 결정을 나중으로 미루면(추상화를 통해) 구현 기술이 변경되어도 클라이언트 코드에는 수정이 필요가 없다. 이게 자바의 객체 지향의 핵심(추상화, 다형성)아닐까?
알고보니, 아무 생각없이 사용했던 List, ArrayList가 이런 심오한 내용을 품고 있었다는게 재밌는거 같다.
이전 포스팅에서 ArrayList를 직접 구현해봤다. 이 ArrayList는 내부에서 배열을 가지고 사용하는 자료구조이다.
ArrayList를 사용해서 얻는 장점은 다음과 같다.
조회가 순식간이라는 것. 인덱스를 통해 바로 그 값을 알아낼 수 있다. 조회는 O(1)의 시간복잡도를 가진다.
그냥 배열만 사용하면 사이즈가 꽉 차면 더이상 자료를 담을 수 없지만 ArrayList를 사용해서 사이즈가 꽉차면 더 큰 사이즈를 가지는 새로운 배열을 만들어서 계속 저장할 수 있다.
그러나 단점으로는 다음과 같다.
데이터를 맨앞에 추가하거나 삭제할 때 기존 데이터를 모두 한칸씩 뒤로 밀거나 앞으로 당겨야한다. 이는 O(n)의 시간복잡도를 가진다.
데이터를 중간에 추가하거나 삭제할 때도 중간 인덱스를 기점으로 이후 데이터는 모두 한칸씩 뒤로 밀거나 앞으로 당겨야한다. 이는 O(n)의 시간복잡도를 가진다.
사이즈가 꽉 차면 더 큰 배열로 새로 만드는데 그 때 남는 메모리가 생기고 이는 곧 메모리의 낭비로 이어진다.
이러한 단점들을 극복해주는 LinkedList가 있다. (사실 그렇게 어떤 드라마틱하게 단점을 극복하지는 않는다고 본다. 그 이유는 마지막에 한번 내 생각을 말해보겠다)
LinkedList는 자신이 보관하는 자료와 자신의 다음 자료에 대한 정보를 가지고 있다. 즉 데이터끼리 연결이 되어 있어서 `Linked`List라고 불린다.
이를 한번 직접 구현해보고, 어떤 장점이 있고 어떤 단점이 있는지 직접 느껴보자. 확실히 직접 구현해보니 보이는게 더 많아진다.
LinkedList에서 관리할 Node 클래스
Node
package org.example.collection.link;
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node x = this;
sb.append("[");
while (x != null) {
sb.append(x.item);
if (x.next != null) {
sb.append("->");
}
x = x.next;
}
sb.append("]");
return sb.toString();
}
}
간단하게 Node 클래스는 자기가 보관할 데이터인 `item`과 다음 Node에 대한 정보를 가지는 `next`라는 필드를 가지고 있다.
근데 필드에 보면 접근 제어자를 지정하지 않았다. 이러면 default가 기본인데 왜 이렇게 했냐면 사실 Node는 추후에 중첩 클래스로 만들것이다. Node는 밖에서 쓰일 일이 없기 때문이다.
CustomLinkedList
package org.example.collection.link;
public class CustomLinkedList {
private Node first;
private int size;
public int size() {
return size;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node x = first;
builder.append("[");
while (x != null) {
builder.append(x.item);
if (x.next != null) {
builder.append(", ");
}
x = x.next;
}
builder.append("]");
return builder.toString();
}
private static class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
@Override
public String toString() {
return item.toString();
}
}
}
그래서 위 코드와 같이 Node라는 클래스를 LinkedList 내부에 중첩 클래스로 만든다. 이 상태에서 하나씩 중요 메서드들을 추가해보자.
가장 중요한 메서드 중 하나는 역시나 `add()`메서드다.
public void add(Object item) {
Node newNode = new Node(item);
if (size == 0) {
first = newNode;
} else {
Node lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
public void add(int index, Object item) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
Node newNode = new Node(item);
if (index == 0) {
newNode.next = first;
first = newNode;
} else {
Node prevNode = getNode(index - 1);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
size++;
}
private Node getNode(int index) {
Node x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
private Node getLastNode() {
Node x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
우선, `add(Object item)`은 가장 마지막에 노드를 하나 추가하는 메서드이다. 현재 사이즈가 0인 경우엔 리스트의 첫번째 노드가 되면 되고 그게 아닌 경우 마지막 노드를 가져와서 그 노드의 다음 노드로 추가하면 된다.
두번째 `add(int index, Object item)`은 원하는 인덱스에 추가하는 경우다. 이 경우는 인덱스가 0인 경우와 그렇지 않은 경우가 나뉘어진다. 0이 아닌 경우는 추가하고자하는 인덱스의 바로 전 노드를 알아내야 한다. 추가하고자 하는 노드의 `next`가 index 노드가 되어야하고 `index - 1` 노드가 index의 노드를 알고 있기 때문이다.
그리고 그 과정에서 사용할 편의 메서드 `getNode(int index)`, `getLastNode()`를 만들었다.
list = [A, B, C, D]
list.size() = 4
list = [A, B, E, C, D]
list.size() = 5
list = [F, A, B, E, C, D]
list.size() = 6
item = A
list = [F, AA, B, E, C, D]
removed = D
list = [F, AA, B, E, C]
removed2 = AA
list = [F, B, E, C]
removed3 = F
list = [B, E, C]
이제 마지막으로 `indexOf()`를 구현해보자.
public int indexOf(Object item) {
Node x = first;
for (int i = 0; i < size; i++) {
if (x.item.equals(item)) {
return i;
}
x = x.next;
}
return -1;
}
어느정도 구현해야 할 중요한 메서드들은 구현이 완료됐다. 이렇게 만들고 나니 LinkedList의 장단점이 하나씩 보이기 시작하는데 그 전에 모든 타입에 대해 허용하고 있으니 제네릭으로 바꿔주자.
제네릭을 도입한 CustomLinkedList
CustomLinkedList
package org.example.collection.link;
public class CustomLinkedList<E> {
private Node<E> first;
private int size;
public int size() {
return size;
}
public void add(E item) {
Node<E> newNode = new Node<>(item);
if (size == 0) {
first = newNode;
} else {
Node<E> lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
public void add(int index, E item) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
Node<E> newNode = new Node<>(item);
if (index == 0) {
newNode.next = first;
first = newNode;
} else {
Node<E> prevNode = getNode(index - 1);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
size++;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> currentNode = getNode(index);
return currentNode.item;
}
public E set(int index, E item) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> oldNode = getNode(index);
E oldItem = oldNode.item;
oldNode.item = item;
return oldItem;
}
public E remove() {
if (size == 0) {
return null;
}
Node<E> prevLastNode = getNode(size - 2);
E removedItem = prevLastNode.next.item;
prevLastNode.next.item = null;
prevLastNode.next = null;
size--;
return removedItem;
}
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
E oldValue;
if (index == 0) {
Node<E> newFirst = first.next;
oldValue = first.item;
first.item = null;
first = newFirst;
} else {
Node<E> prevNode = getNode(index - 1);
Node<E> removeNode = getNode(index);
oldValue = removeNode.item;
prevNode.next = removeNode.next;
removeNode.next = null;
removeNode.item = null;
}
size--;
return oldValue;
}
public int indexOf(E item) {
Node<E> x = first;
for (int i = 0; i < size; i++) {
if (x.item.equals(item)) {
return i;
}
x = x.next;
}
return -1;
}
private Node<E> getNode(int index) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node<E> x = first;
builder.append("[");
while (x != null) {
builder.append(x.item);
if (x.next != null) {
builder.append(", ");
}
x = x.next;
}
builder.append("]");
return builder.toString();
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
private static class Node<E> {
E item;
Node<E> next;
public Node(E item) {
this.item = item;
}
@Override
public String toString() {
return item.toString();
}
}
}
제네릭까지 도입해서 타입 안정성도 확보했다. 이제 내 결론을 내려고 한다.
결론
ArrayList와 LinkedList는 이런 차이가 있다.
연산
ArrayList
LinkedList (Custom)
조회
O(1)
O(n)
탐색
O(n)
O(n)
맨 앞 추가(삭제)
O(n)
O(1)
중간 추가(삭제)
O(n)
O(n)
마지막 추가(삭제)
O(1)
O(n)
사이즈 조정
메모리 낭비 있을 수 있음
메모리 낭비 없음 (표면적으론)
조회: ArrayList가 더 유리하다. 배열은 인덱스로 바로 알아낼 수 있으니까. 그러나 LinkedList는 첫번째부터 계속 하나씩 찾아나가야 한다.
탐색: 둘 다 처음부터 끝까지 하나씩 찾아나간다.
맨 앞에 추가 또는 삭제: LinkedList가 더 유리하다. 배열은 추가하거나 삭제하려면 모든 자료를 한칸씩 뒤로 밀거나 앞으로 당겨야 한다. 반면 LinkedList는 연결 정보만 바꿔주면 된다.
중간 추가 또는 삭제: 배열은 추가하는 작업 자체는 O(1)이지만 중간지점부터 마지막까지 한칸씩 밀거나 당겨야한다. LinkedList는 추가, 삭제 작업 모두 O(1)으로 끝낼 수 있지만 중간까지 찾아나가는 작업이 O(n)이다.
마지막 추가 또는 삭제: 이건 지금 만든 CustomLinkedList 기준 ArrayList가 더 유리하다. 근데 자바가 만들어놓은 LinkedList는 첫번째 노드뿐만 아니라 마지막 노드도 가지고 있다. 그래서 자바가 만들어놓은 LinkedList는 O(1)이 될 수 있다.
사이즈는 LinkedList는 남는 메모리는 존재하지 않는다. 하나씩 다음 노드를 저장만 해 놓으면 되니까. 근데, 다음 노드를 저장하는 공간에 대한 메모리가 사용된다. 그러니까 어떻게 보면.. 메모리가 사용 측면에서 더 효율적이지 않을 수도 있을것같다.
그래서 결론은 더 유리하고 덜 유리한 자료구조 관계가 아니라 그때 그때 더 유리하게 작용될 수 있는 자료구조를 직접 선택해 나가야 한다는 것이다. (근데 대부분의 경우 ArrayList가 더 유리하다. 다만, 맨 앞에 자료가 추가(삭제)가 되는 경우가 많으면 LinkedList를 고려해보자.)
이제 보니까 ArrayList도 LinkedList도 메서드 시그니쳐가 거의 똑같거나 아예 똑같다. 그러면 자바는 이걸 어떻게 하더라? 추상화한다. 그래서 지금까지 사용했던 리스트에 대한 타입이 List<T>인 이유가 여기에 있는것 같다. 아래와 같이 사용하곤 했다.
지금까지 그저 사용하기만 했던 ArrayList를 직접 구현해 보고 어떤 원리로 동작하는지 자세히 이해해 보자.
단계별로 밟아나가면서 점차 완성시켜 보자.
ArrayList는 본인의 데이터를 결국 배열이라는 자료 구조로 관리하고 사용한다. 그래서 말 그대로 'Array'List이다.
CustomArrayList
package org.example.collection.array;
public class CustomArrayList {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elements;
private int size;
public CustomArrayList() {
elements = new Object[DEFAULT_CAPACITY];
}
public CustomArrayList(int capacity) {
elements = new Object[capacity];
}
public int size() {
return size;
}
}
기본틀을 만들자. 지금까지 사용해 왔던 ArrayList는 어떤 타입이든 받아들일 수 있었다. 그것은 결국 모든 타입을 다 허용해 주는 Object 타입의 배열을 사용한다는 것을 의미한다. 그래서 다음과 같이 필드를 선언한다.
private Object[] elements;
그리고 또 한 가지 가장 많이 사용되는 메서드 중 하나인 size()는 별 게 아니다. 그저 자신이 가지고 있는 size라는 필드를 반환할 뿐이다.
private int size;
...
public int size() {
return size;
}
그다음 배열은 항상 고정된 사이즈가 있다. 그 고정된 사이즈를 기존에 ArrayList를 사용하면서 사이즈를 직접 명시한적은 거의 없다. 일반적으로 다음과 같이 사용했을 것이다.
List<String> strings = new ArrayList<>();
이렇게 사용해도 상관없는 이유는 이 클래스는 DEFAULT_CAPACITY라는 상수를 가지고 있기 때문이다.
private static final int DEFAULT_CAPACITY = 5;
그래서 생성자로는 이렇게 명시하지 않으면 기본 사이즈로 배열을 생성하고 명시하는 값을 집어넣으면 그 사이즈로 배열의 사이즈를 초기화한다.
public CustomArrayList() {
elements = new Object[DEFAULT_CAPACITY];
}
public CustomArrayList(int capacity) {
elements = new Object[capacity];
}
이게 ArrayList의 초기 틀이다. 생각보다 간단하다. 그다음 이 ArrayList에서 가장 많이 사용했던 메서드가 뭔가? `add()`다.
public void add(Object element) {
elements[size++] = element;
}
완전한 소스는 아니지만 이게 가장 핵심이다. 추가한 후 본인의 사이즈를 하나 증가시키는.
근데, 이제 만약 배열이 꽉 찬 상태에서 추가를 하려고 하면? 배열은 그렇게 할 수 없다. 근데 우리가 사용했던 ArrayList는 잘만 됐다. 그 이유가 여기에 있다.
public void add(Object element) {
if (size == elements.length) {
elements = Arrays.copyOf(elements, size * 2);
}
elements[size++] = element;
}
배열의 사이즈가 꽉 찼다면, 더 큰 배열을 새로 만들어서 그 배열로 바꿔치기 하는 것이다. copyOf() 메서드는 기존 배열을 그대로 카피하는데 사이즈를 전달받은 크기로 만들어버리는 메서드이다. 그렇게 새로 만들어진 배열의 참조값을 elements에 할당해서 elements가 새로운 참조값을 참조하도록 한다. 그러고 난 후 그 배열에 새로운 값을 추가한다. 그럼 기존에 참조하고 있던 배열은? `GC` 대상이 된다.
그리고 사이즈를 늘려서 새로운 배열을 만드는 저 코드는 이곳저곳 많이 사용되니까 메서드로 뽑아낸다.
package org.example.collection.array;
public class CustomArrayListMain {
public static void main(String[] args) {
CustomArrayList list = new CustomArrayList();
list.add(1);
list.add(2);
list.add(3);
System.out.println("list = " + list);
}
}
실행결과
list = [1, 2, 3]
이쁘게 값을 세 개 넣고 가지고 있는 것을 찍어내는 것까지 해봤다. 이제 넣었으면 지우기도 해야한다. 지워보자.
ArrayList의 대표적인 remove() 메서드는 이렇게 인덱스로, 특정값으로 지우는 두 가지가 있다.
removeAll(), removeFirst(), removeLast()는 생략하도록 한다.
public Object remove(int index) {
if (index < 0 || index >= size) {
return null;
}
Object removed = get(index);
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return removed;
}
public boolean remove(Object element) {
Object removedItem = null;
int removedIndex = -1;
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
removedItem = elements[i];
removedIndex = i;
break;
}
}
if (removedItem == null) {
return false;
}
for (int i = removedIndex; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return true;
}
두 메서드 다 지우고 나서 지운 요소의 인덱스가 비어있지 않도록 한칸씩 앞으로 밀어야한다. 그 코드가 다음 코드.
for (int i = removedIndex; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
이제 indexOf(Object element) 메서드를 구현해보자. 이 메서드는 주어진 요소가 몇번째 인덱스에 해당하는지 확인하는 메서드.
public int indexOf(Object element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
return i;
}
}
return -1;
}
여기까지의 최종 코드
CustomArrayList
package org.example.collection.array;
import java.util.Arrays;
public class CustomArrayList {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elements;
private int size;
public CustomArrayList() {
elements = new Object[DEFAULT_CAPACITY];
}
public CustomArrayList(int capacity) {
elements = new Object[capacity];
}
public int size() {
return size;
}
public void add(Object element) {
if (size == elements.length) {
grow();
}
elements[size++] = element;
}
public void add(int index, Object element) {
if (size == elements.length) {
grow();
}
for (int i = size - 1; i > index ; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
}
public Object remove(int index) {
if (index < 0 || index >= size) {
return null;
}
Object removed = get(index);
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return removed;
}
public boolean remove(Object element) {
Object removedItem = null;
int removedIndex = -1;
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
removedItem = elements[i];
removedIndex = i;
break;
}
}
if (removedItem == null) {
return false;
}
for (int i = removedIndex; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return true;
}
public int indexOf(Object element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
return i;
}
}
return -1;
}
public Object get(int index) {
return elements[index];
}
public Object set(int index, Object element) {
Object oldValue = get(index);
elements[index] = element;
return oldValue;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elements, size));
}
private void grow() {
elements = Arrays.copyOf(elements, size * 2);
}
}
이제 실행해서 테스트를 해보자.
CustomArrayListMain
package org.example.collection.array;
public class CustomArrayListMain {
public static void main(String[] args) {
CustomArrayList list = new CustomArrayList();
list.add("Hello");
list.add("Java");
list.add("I Love");
list.add("U");
System.out.println("list = " + list);
Object remove = list.remove(2);
System.out.println("remove = " + remove);
System.out.println("list = " + list);
boolean isDeleted = list.remove("Java");
System.out.println("isDeleted = " + isDeleted);
System.out.println("list = " + list);
int u = list.indexOf("U");
System.out.println("u = " + u);
}
}
실행결과
list = [Hello, Java, I Love, U]
remove = I Love
list = [Hello, Java, U]
isDeleted = true
list = [Hello, U]
u = 1
근데 지금 문제가 있는데, 가장 큰 문제는 이 CustomArrayList는 받는 요소의 타입이 Object라는 점이다. 모든 타입이 다 가능하기 때문에 꺼내올 때 그것을 어떤 타입으로 다운 캐스팅해야 할지 확신할 수 없다. 근데 기존에 종종 사용하는 ArrayList는 제네릭을 사용하니까 이 CustomArrayList도 제네릭을 사용해보자.
제네릭 타입 도입하기
CustomArrayList
package org.example.collection.array;
import java.util.Arrays;
public class CustomArrayList<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elements;
private int size;
public CustomArrayList() {
elements = new Object[DEFAULT_CAPACITY];
}
public CustomArrayList(int capacity) {
elements = new Object[capacity];
}
public int size() {
return size;
}
public void add(E element) {
if (size == elements.length) {
grow();
}
elements[size++] = element;
}
public void add(int index, E element) {
if (size == elements.length) {
grow();
}
for (int i = size - 1; i > index ; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
}
public E remove(int index) {
if (index < 0 || index >= size) {
return null;
}
E removed = get(index);
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return removed;
}
@SuppressWarnings("unchecked")
public boolean remove(E element) {
E removedItem = null;
int removedIndex = -1;
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
removedItem = (E) elements[i];
removedIndex = i;
break;
}
}
if (removedItem == null) {
return false;
}
for (int i = removedIndex; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return true;
}
public int indexOf(E element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
return i;
}
}
return -1;
}
@SuppressWarnings("unchecked")
public E get(int index) {
return (E) elements[index];
}
public E set(int index, E element) {
E oldValue = get(index);
elements[index] = element;
return oldValue;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elements, size));
}
private void grow() {
elements = Arrays.copyOf(elements, size * 2);
}
}
코드를 보면 필드로 가진 배열 elements는 여전히 Object타입의 배열이다. 왜 그럴까? 제네릭의 타입 이레이저 때문에 new T[]같은게 불가능하기 때문이다. 결국 컴파일하고 나면 .class 파일은 제네릭이 없어지고 그 자리에 전부 Object로만 남게되는걸 말하는데 그럼 new T는 언제나 new Object가 될 것이므로 제네릭을 사용하는 경우 자바 자체적으로new, instanceof 키워드는 사용할 수가 없다.
대신, 해당 배열에 넣고 빼고 어떤 요소에 대한 작업이든 다 제네릭의 타입 매개변수를 사용하면 문제를 일으키지 않고 정확히 원하는 타입으로 넣고 뺄 수 있어진다. 그 결과 이 CustomArrayList를 가져다가 사용하는 쪽은 이제 타입 안정성을 보장받을 수 있게 된다.
결론
이렇게 직접 ArrayList를 구현해보니, 안에서 어떤 식으로 동작하는지 완벽하게 이해할 수 있었다. 어떻게 사이즈를 동적으로 계속해서 늘릴수 있는지와 지우거나 중간에 추가할 때 어떻게 기존 배열을 다시 정돈해주는지 등을.
근데, 이 ArrayList는 단점이 있다.
사이즈를 늘리고 나서 더이상 사용하지 않으면 불필요하게 메모리를 낭비한다.
삽입, 삭제를 중간이나 첫번째에 하는 경우 뒤로 밀거나 앞으로 밀 때 O(n)만큼의 시간이 소요된다.
이 연산이 배열이 왜 단 한번의 연산으로 조회가 가능한지를 설명한다. 아 그래서 배열은 크기와 타입을 정해주는구나?를 역으로도 생각할 수 있게 된다. 그래서 배열은 굉장히 좋은 자료구조 중 하나이다.
조회뿐 아니라 삽입, 삭제도 단 한번의 연산으로 가능하다.
삽입: arr[3] = 10
삭제: arr[3] = 0
딱 원하는 인덱스에 원하는 값을 추가하면 되고, 딱 원하는 인덱스를 찾아 값을 날리면 된다. 그래서 배열에서는 조회, 삽입, 삭제가 O(1)의 시간복잡도를 가진다. O(1)은 데이터가 아무리 많아도 1억개, 10억개, 1조개라도 단 한번의 연산이면 된다는 것을 의미한다.
근데 탐색은 O(n)이다. 왜냐하면 원하는 값을 찾기 위해선 처음부터 마지막까지 하나씩 순회를 해야만 내가 원하는 값을 찾아낼 수 있기 때문이다 배열의 크기가 N이면 연산도 N번만큼 필요하다.
물론, 저 위 그림을 예시로 배열에서 1을 찾고 싶다고 하면 0번 인덱스가 1이기 때문에 1번의 연산으로 찾는게 가능하지만 만약 30을 찾는다고 하면 0번 인덱스부터 4번 인덱스까지 갈 동안 찾지 못했기 때문에 배열의 크기만큼 연산이 이루어진다. 그리고 만약 마지막 인덱스에 원하는 값이 있어도 N번의 연산을 수행할것이다. 그래서 O(n)이 된다.
근데 여기서 말하는 O(1)이니 O(n), 이것들이 다 뭘까?
Big O 표기법
알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 처리해야 하는 데이터 양에 따라 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다. 정확한 실행 시간을 계산하는 게 아니고 데이터 양의 증가에 따른 성능의 변화 추세를 말한다.
O(1) - 상수 시간을 말하고 데이터의 크기에 상관없이 일정하게 단 한번의 연산으로 처리된다.
O(n) - 선형 시간을 말하고 입력 데이터의 크기에 비례하여 실행시간이 증가한다.
O(n^2) - 제곱 시간을 말하고 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다. 예를 들면 이중 루프를 사용할 때이다.
O(log n) - 로그 시간을 말하고 알고리즘의 실행 시간이 데이터 크기의 로그에 빌례하여 증가한다.
O(n log n) - 선형 로그 시간을 말하고 대다수의 효율적인 정렬 알고리즘이 이렇다.
Big O 표기법은 데이터 양 증가에 따른 성능의 변화 추세를 비교하는데 사용한다. 쉽게 이야기해서 정확한 성능을 측정하는 것이 목표가 아니라 매우 큰 데이터가 들어왔을 때의 대략적인 추세를 비교하는 게 목적이다. 따라서 데이터가 매우 많이 들어오면 추세를 보는데 상수는 의미가 없어진다. 이런 이유로 Big O 표기법에서는 상수를 제거한다. 예를 들어 O(2n)이나 O(n+2), O(n/2) 모두 다 O(n)으로 표시한다.
Big O 표기법은 별도의 이야기가 없으면 보통 최악의 상황을 가정해서 표기한다. 최적, 평균, 최악의 경우로 나누어 표기하는 경우도 있다.
위 예시에서 배열을 가지고 얘기를 했는데 조회나 삽입, 삭제는 언제나 O(1)이다. 데이터가 아무리 많아도 단 한번의 수행으로 끝나니까.
탐색의 경우는 O(n)이다. 운이 좋으면 첫번째 인덱스가 원하는 값이 나올수도 있지만 최악의 경우는 가장 마지막 인덱스이거나 아예 없는 경우이기 때문에 N개의 요소를 다 확인한다.
