효율적인 자료구조: Set과 Map

Java 코드 최적화

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

공간/시간 복잡도 적용하기

이제 공간 및 시간 복잡도에 대해 알게 되었습니다!

이 지식을 어떻게 적용해야 더 효율적인 코드를 작성할 수 있을까요?

바로 올바른 자료구조를 선택하는 것입니다!

Java 코드 최적화

사용자 관리 시스템

  • 사용자 관리 시스템을 만들고 있습니다

  • 특정 사용자 이름이 존재하는지 확인해야 합니다

  • 리스트 사용 시: 복잡도 $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}
Java 코드 최적화

Set

  • 빠른 조회가 가능한 고유 원소 집합
  • 원소 추가, 삭제, 존재 여부 확인의 평균 시간 복잡도는 $O(1)$

개선된 사용자 관리 시스템 솔루션:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}
Java 코드 최적화

Map

  • 사전처럼 단어(키) -> 정의(값) 형태
  • HashMap: 연산의 평균 시간 복잡도는 $O(1)$
public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}
Java 코드 최적화

Hashcode 메서드

  • 이를 빠르게 만들어주는 것은 hashCode()
  • ArrayList 예제에서는 찾을 사용자 이름의 인덱스를 알 수 없었습니다
  • hashcode() 메서드를 사용하면 객체를 찾을 수 있는 인덱스로 변환할 수 있습니다
  • 예: pavlos.2020 -> 35189

pavlos.2020을 hashcode로 처리하여 35189가 나오는 과정

Java 코드 최적화

원소 인덱싱

  • HashMap과 HashSet은 내부적으로 배열을 사용합니다
  • 원소를 추가할 때:
    • Java가 원소에 대해 hashCode()를 호출해 정수를 얻습니다
    • 이 값에 모듈로 연산을 적용해 버킷 번호를 구합니다

예시:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- that's our bucket!
Java 코드 최적화

충돌

  • 둘 이상의 항목이 같은 버킷에 들어가는 경우
    • 이를 충돌(collision)이라고 합니다
  • 버킷에는 LinkedList를 사용합니다
  • 그래서 평균적으로 $O(1)$이라고 말하는 것입니다
Java 코드 최적화

기억해 둘 점

자료구조 선택은 작업에 맞는 도구를 고르는 것과 같습니다. 망치(ArrayList)는 못에는 좋지만 나사(Set이 더 적합할 수 있는 경우)에는 적합하지 않습니다.

망치, 드라이버, 렌치, 펜치가 나란히 놓인 열린 공구함

Java 코드 최적화

연습해 봅시다!

Java 코드 최적화

Preparing Video For Download...