인터뷰에서 물어볼 수 있는 내용: Java의 데이터 구조. 1 부

안녕하세요! 어떻게 보아도 기술입시 면접에 합격하지 않고는 개발자가 될 수 없습니다. Java와 관련된 기술은 많지만, 모든 것을 배우는 것은 불가능합니다. 일반적으로 인터뷰에서는 프로젝트에 중요한 일부 프레임워크에 대한 좋은 경험을 가진 개발자를 찾는 경우에만 구체적인 내용을 묻습니다. 그렇다면 당신은 이 프레임워크 주위에서 최고 속도로 쫓기게 될 것입니다. 의심의 여지가 없습니다. 하지만 이제 우리는 모든 Java 개발자가 알아야 할 기반에 대해 이야기하고 있습니다. 모든 것이 시작되는 고전 지식에 대해. 오늘 저는 인터뷰의 기본 주제 중 하나인 Java의 데이터 구조에 대해 다루고 싶습니다 . 그러니 수풀 주위를 두드리는 대신 시작합시다. 인터뷰 중에 이 주제에 관해 질문을 받을 수 있는 질문 목록을 찾아보세요.

1. 데이터 구조에 대해 조금 알려주세요

데이터 구조는 특정 방식으로 구조화된 정보를 포함하는 데이터 저장소입니다. 이러한 구조는 특정 작업의 효율적인 수행을 위해 설계되었습니다. 데이터 구조의 일반적인 예는 다음과 같습니다.

• 배열,
• 스택,
• 대기열,
• 관련 목록,
• 그래프,
• 나무,
• 접두사 나무,
• 해시 테이블.

여기 와 여기 에서 자세한 내용을 확인할 수 있습니다 . 데이터는 프로그램의 핵심 구성 요소이며 구조를 통해 이 데이터를 구체적이고 명확하게 구조화된 형식으로 저장할 수 있습니다. 애플리케이션이 무엇을 하든 이 측면은 항상 존재합니다. 즉, 웹 스토어인 경우 제품에 대한 정보가 저장되고, 소셜 네트워크인 경우 사용자 및 파일에 대한 데이터 등이 저장됩니다.

2. 배열에 대해 무엇을 알고 있나요?

배열은 동일한 유형의 값을 저장하는 컨테이너이며, 그 수는 미리 지정됩니다. 문자열 값으로 배열을 생성하는 예:

String[] strArray = {"Java","is","the","best","language"};

배열을 생성할 때 모든 요소에 메모리가 할당됩니다. 요소에 대해 더 많은 셀이 처음에 지정될수록 더 많은 메모리가 할당됩니다. 특정 수의 셀이 포함된 빈 배열이 생성되면 배열의 모든 요소에 기본값이 할당됩니다. 예를 들어:

int[] arr = new int[10];

따라서 부울 유형 의 요소가 있는 배열의 경우 초기( 기본값 ) 값은 false 이고 , 숫자 값이 - 0이고 char 유형의 요소가 - \u0000 인 배열의 경우입니다 . 클래스 유형(객체) 배열의 경우 - null (빈 문자열이 아님 - “” 그러나 구체적으로 null ). 즉, 위의 예에서 arr 배열의 모든 값은 직접 지정하기 전까지는 0이 됩니다. 컬렉션과 달리 배열은 동적이지 않습니다. 특정 크기의 배열이 선언되면 크기 자체를 변경할 수 없습니다. 배열에 새 요소를 추가하려면 더 큰 새 배열을 만들고 이전 배열의 모든 요소를 ​​여기에 복사해야 합니다(이것이 ArrayList가 작동하는 방식입니다). 모든 사람이 알지 못하고 당신이 아주 잘 잡을 수있는 한 가지 점이 있습니다. Java에는 단순 유형 과 본격적인 객체에 대한 참조라는 두 가지 유형의 변수가 있습니다 . 다음 중 배열은 무엇인가요? 예를 들어, 여기:

int[] arr = new int[10];

모든 것이 간단한 것 같습니다. 이는 10개의 int 요소입니다 . 그렇다면 이것이 단순 유형이라고 말할 수 있습니까? 그것이 어떻든 상관 없습니다. Java에서 배열은 동적으로 생성되고 Object 유형의 변수에 할당될 수 있는 객체입니다. Object 클래스의 모든 메서드는 배열에서 호출될 수 있습니다. 그래서 우리는 다음과 같이 쓸 수도 있습니다:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

콘솔에 출력할 때 다음과 같은 결과를 얻을 수 있습니다. Java 배열에 관한 이 기사 에서 Java 배열의 기능에 대해 자세히 알아보세요 . 지식을 통합하기 위해 이 컬렉션 의 여러 문제를 해결할 수 있습니다 .

3. 컬렉션의 계층 구조를 설명하세요.

컬렉션은 데이터 작업 시 유연성이 필요한 상황에서 사용됩니다. 컬렉션은 요소를 추가하고, 요소를 제거하고, 기타 여러 작업을 수행할 수 있습니다. Java에는 다양한 구현이 있으므로 현재 상황에 적합한 컬렉션을 선택하기만 하면 됩니다. 일반적으로 Collection 인터페이스를 언급할 때 일부 구현 및 Map 과의 관계를 나열하라는 메시지가 표시됩니다 . 글쎄, 알아 보자. 따라서 컬렉션 과 맵은 데이터 구조에 대한 서로 다른 두 계층입니다. Collection 계층구조 의 모습 : Collection 인터페이스는 세 가지 기본 유형의 데이터 구조( Set , List , Queue ) 가 시작되는 기본 메소드 목록이 있는 주요 최상위 링크입니다 . Set<T> 는 각 개체가 고유한 개체 컬렉션을 나타내는 인터페이스입니다. List<T> 는 목록이라고 하는 개체의 순서가 지정된 시퀀스를 나타내는 인터페이스입니다. Queue<T>는 큐(요소의 순차적 저장)로 구성된 구조를 담당하는 인터페이스입니다. 앞서 언급했듯이 Map은 별도의 계층 구조입니다. Map<K, V> 는 요소가 키-값 쌍으로 포함된 사전을 나타내는 인터페이스입니다. 또한 모든 키(K)는 Map 객체 내에서 고유합니다 . 이러한 유형의 컬렉션을 사용하면 객체의 고유 식별자인 키를 알면 요소를 더 쉽게 찾을 수 있습니다.

4. 세트에 대해 무엇을 알고 있나요?

앞서 언급했듯이 이 컬렉션에는 독특한 요소가 많이 포함되어 있습니다. 즉, 동일한 객체가 Java Set 에 두 번 이상 나타날 수 없습니다. 또한 Set by number(인덱스)에서 요소를 추출할 수 없으며 오직 무차별 대입 방식으로만 추출할 수 있다는 점을 지적하고 싶습니다 . 중요한 것은 Set의 구현마다 데이터를 구조화하는 방법이 다르다는 것입니다. 우리는 구체적인 구현을 더 고려할 것입니다. 따라서 Set : HashSet 의 주요 구현은 해시 테이블을 기반으로 하는 집합이며 이는 검색에 도움이 됩니다. 조회 및 삽입 중 성능을 향상시키는 해시 함수를 사용합니다. 요소 수에 관계없이 일반적으로 삽입과 검색(때때로 삭제)은 일정한 시간(O(1))에 가깝게 수행됩니다. 해시 함수에 대해서는 잠시 후에 더 자세히 살펴보겠습니다. 또한 HashSet에는 모든 마법이 일어나는 곳인 HashMap이 포함되어 있다는 점에 주목하고 싶습니다 . 다음은 Java의 HashSet에 대한 자세한 기사입니다 . LinkedHashSet - 이 클래스는 새로운 메소드를 추가하지 않고 HashSet을 확장합니다. LinkedList 와 마찬가지로 이 클래스는 삽입된 순서대로 집합 요소의 연결 목록을 유지 관리합니다. 이를 통해 주어진 Set 구현에서 필요한 순서를 구성할 수 있습니다 . TreeSet 클래스는 저장 요소의 구조를 구성하기 위해 레드-블랙 트리를 기반으로 하는 세트를 생성합니다. 즉, 주어진 집합에서 요소를 오름차순으로 정렬할 수 있습니다. 예를 들어 Integer 와 같은 "상자"의 일부 표준 개체를 사용하는 경우 정수 집합을 오름차순으로 정렬하기 위해 아무 것도 할 필요가 없습니다.

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

그리고 콘솔에는 다음과 같은 출력이 표시됩니다. 즉, 이 세트 에서는 숫자가 정렬된 형태로 저장됩니다. TreeSet 에서 String 요소를 사용하면 정렬되지만 알파벳순으로 정렬됩니다. 그렇다면 표준(사용자 정의) 클래스가 있다면 어떨까요? 이 클래스의 객체는 TreeSet을 어떻게 구성합니까 ? 이 Set 에 임의의 객체를 할당하려고 하면 다음과 같습니다 .

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

TreeSet이 이 유형의 객체를 정렬하는 방법을 모르기 때문에 ClassCastException을 받게 됩니다 . 이 경우 Comparable 인터페이스 와 해당 CompareTo 메서드를 구현하려면 사용자 정의 개체가 필요합니다 .

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

보시다시피, CompareTo 메서드는 int를 반환합니다 .

• 현재(this) 개체가 큰 것으로 간주되면 1이고, 그렇지 않으면 1입니다.
• -1 현재 개체가 인수로 제공된 개체보다 작은 것으로 간주되는 경우;
• 개체가 동일한 경우 0입니다(이 경우에는 사용하지 않음).

이 경우 TreeSet 은 올바르게 작동하고 결과를 표시합니다. 또 다른 방법은 비교기 인터페이스와 해당 비교 메서드를 구현하는 별도의 정렬 클래스를 만드는 것입니다 .

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

이 경우 이를 사용하려면 이 클래스의 객체를 TreeSet 생성자로 설정해야 합니다 .

TreeSet set = new TreeSet<>(new CatComparator());

그런 다음 TreeSet 에 포함된 Cat 클래스의 모든 객체는 Cat Comparator 클래스를 사용하여 정렬됩니다 . 이 기사 에서 Java의 Comparator 및 Comparable 에 대해 자세히 알아볼 수 있습니다 .

5. 큐에 대해 알려주세요

큐는 요소를 순차적으로 저장하는 데이터 구조인 큐로 구성된 구조를 담당하는 인터페이스입니다. 예를 들어, 사람들이 줄을 서서 가장 먼저 입장하는 사람은 다른 사람보다 먼저 도착한 사람이 되고, 마지막 사람은 다른 사람보다 늦게 도착한 사람이 됩니다. 이 방법을 FIFO , 즉 First In First Out 이라고 합니다 . 고유한 대기열 메서드는 첫 번째 또는 마지막 요소 작업에 중점을 둡니다. 예를 들면 다음과 같습니다.

• 추가 및 제공 - 대기열 끝에 요소를 삽입합니다.
• 제거 - 이 대기열의 헤더를 검색하고 제거합니다.
• peek - 대기열 헤더를 검색하지만 제거하지는 않습니다.

2 부