Java 개발자 인터뷰의 질문과 답변을 분석합니다. 9부

불꽃! 프로그래머가 되는 것은 쉽지 않습니다. 끊임없이 배워야 하고, 항상 새로운 것을 배워야 합니다. 그러나 다른 사업과 마찬가지로 가장 어려운 일은 시작하고 목표를 향한 첫 걸음을 내딛는 것입니다. 그리고 당신은 이 사이트에 앉아 이 글을 읽고 있으므로 첫 번째 단계를 완료했습니다. 이는 이제 도중에 속도를 늦추거나 끄지 않고 의도적으로 목표를 향해 나아가야 함을 의미합니다. 제가 올바르게 이해했다면 귀하의 목표는 Java 개발자가 되거나 지식을 향상시키는 것입니다. 그렇다면 우리는 250개가 넘는 Java 개발자 인터뷰 질문의 광범위한 목록을 계속해서 분석할 것이기 때문에 귀하는 올바른 위치에 계십니다. 계속하자!

컬렉션

84. 반복자와 그 사용법에 대해 알려주십시오.

컬렉션은 Java 개발자 인터뷰에서 가장 좋아하는 주제 중 하나이며, 컬렉션 계층 구조에 대해 이야기할 때 지원자들은 컬렉션 인터페이스 로 시작한다고 말하는 경우가 많습니다 . 하지만 이는 사실이 아닙니다. 왜냐하면 이 인터페이스 위에 Iterable 이라는 또 다른 인터페이스가 있기 때문입니다 . 이 인터페이스는 현재 컬렉션에 대해 Iterator 객체를 호출할 수 있는 iterator() 메서드를 나타냅니다. 그리고 이 Iterator 객체는 정확히 무엇입니까 ? Iterator는 사용자가 특정 컬렉션의 구현을 알 필요 없이 컬렉션을 통해 이동하고 요소를 반복하는 기능을 제공하는 개체입니다. 즉, 이것은 컬렉션의 특정 위치를 보는 컬렉션의 요소에 대한 일종의 포인터입니다. 반복자에는 다음과 같은 메서드가 있습니다.

• hasNext() - 포인터 뒤에 요소가 있으면 true를 반환합니다(이 메서드를 사용하면 컬렉션의 끝에 도달했는지 확인할 수 있습니다).
• next() - 포인터 뒤의 다음 요소를 반환합니다. 아무 것도 없으면 NoSuchElementException 이 발생합니다 . 즉, 이 방법을 사용하기 전에 hasNext() 를 사용하여 요소가 존재하는지 확인하는 것이 좋습니다 .
• 제거() - next() 메서드를 사용하여 컬렉션에서 받은 마지막 요소를 제거합니다 . Remove ()가 호출되기 전에 next ( )가 호출 된 적이 없으면 예외가 발생합니다 - IllegalStateException ;
• forEachRemaining(<Consumer>) - 컬렉션의 각 요소에 대해 전달된 작업을 수행합니다(Java 8에 표시된 메서드).

다음은 논의된 반복자 메서드를 사용하여 목록을 반복하고 모든 요소를 ​​제거하는 간단한 예입니다.

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

콘솔에 다음이 표시됩니다. 이는 요소 제거가 성공했음을 의미합니다. 반복자가 있으면 모든 요소를 ​​화면에 인쇄하는 메서드를 사용할 수 있습니다.

iterator.forEachRemaining(x -> System.out.print(x));

그러나 그 이후에는 반복자가 전체 목록을 순회하고 일반 반복자에는 역추적을 위한 메서드가 없기 때문에 이후 사용에 적합하지 않게 됩니다. 여기서 우리는 LinkedList , 즉 현대화된 반복자 유형인 ListIterator를 반환하는 listIterator() 메서드에 점진적으로 접근합니다 . 일반(표준) 반복자 메서드 외에도 다음과 같은 추가 메서드가 있습니다.

• add(<Element>) - 목록에 새 요소를 삽입합니다.
• hasPrevious() - 포인터 앞에 요소가 있는 경우(이전 요소가 있는지 여부) true를 반환합니다.
• nextIndex() - 포인터 뒤의 다음 요소 목록에서 인덱스를 반환합니다.
• 이전() - 이전 요소를 반환합니다(포인터까지).
• PreviousIndex() - 이전 요소의 인덱스를 반환합니다.
• set(<Element>) - next() 또는 이전() 메서드 에서 반환된 마지막 요소를 대체합니다 .

보시다시피, 이 반복자의 기능은 훨씬 더 흥미롭습니다. 이를 통해 요소 작업 시 양방향으로 이동할 수 있고 손이 자유로워집니다. 또한 사람들이 반복자에 관해 이야기할 때 때로는 패턴 자체를 의미하기도 합니다. 문제를 피하고 이에 대해 설득력 있게 이야기하려면 Iterator 패턴에 대한 이 기사를 읽어보세요 .

85. Java Collection Framework의 컬렉션 계층 구조는 무엇입니까?

Java에는 두 가지 컬렉션 계층이 있습니다. 첫 번째 계층은 다음과 같은 구조를 가진 컬렉션 계층 자체 입니다 . 이는 차례로 다음 하위 컬렉션으로 나뉩니다.

• Set은 순서가 지정되지 않은 고유한(반복되지 않는) 요소를 포함하는 집합과 같은 데이터 구조를 설명하는 인터페이스입니다 . 인터페이스에는 표준 구현인 TreeSet , HashSet 및 LinkedHashSet 이 있습니다 .
• List 는 순서가 지정된 개체 시퀀스를 저장하는 데이터 구조를 설명하는 인터페이스입니다. 목록 에 포함된 인스턴스는 이 컬렉션의 인덱스에 따라 삽입 및 삭제될 수 있습니다(배열과 유사하지만 동적 크기 조정이 가능함). 인터페이스에는 ArrayList , Vector ( 구식으로 간주되어 실제로 사용되지 않음 ) 및 LinkedList 와 같은 표준 구현이 있습니다 .
• Queue 는 FIFO-First In First Out 규칙 을 따르는 큐 형태로 요소를 저장하는 데이터 구조를 설명하는 인터페이스입니다 . 인터페이스에는 LinkedList (예, Queue 도 구현함 ) 및 PriotityQueue 와 같은 표준 구현이 있습니다 .

컬렉션의 두 번째 계층은 다음과 같은 구조를 갖는 Map 입니다 . 이 컬렉션에는 하위 컬렉션으로 구분되지 않습니다( Map 계층 자체가 하위 컬렉션과 유사하지만 별도로 존재하기 때문입니다). 표준 맵 구현은 Hashtable (더 이상 사용되지 않는 것으로 간주됨), LinkedHashMap 및 TreeMap 입니다 . 실제로 Collection 에 대해 질문하면 일반적으로 두 계층 모두를 의미합니다.

86. ArrayList의 내부 구조는 무엇입니까?

ArrayList 는 배열과 유사하지만 동적으로 확장할 수 있는 기능이 있습니다. 무슨 뜻이에요? 사실 ArrayList는 일반 배열을 기반으로 작동합니다. 즉, 내부 배열에 요소를 저장합니다(기본 크기는 10셀). 내부 배열이 가득 차면 새 배열이 생성되며 크기는 다음 공식에 의해 결정됩니다.

<размерТекущегоМассива> * 3 / 2  + 1

즉, 배열의 크기가 10이면 새 배열의 크기는 10 * 3 / 2 + 1 = 16이 됩니다. 다음으로 첫 번째(이전) 배열의 모든 값은 다음을 사용하여 복사됩니다. 기본 System.arraycopy () 메서드 이며 첫 번째 배열이 삭제됩니다. 실제로 ArrayList의 동적 확장성은 이렇게 구현됩니다 . 가장 많이 사용되는 ArrayList 메소드를 살펴보겠습니다 . 1. add(<Elelement>) - 배열 끝(마지막 빈 셀)에 요소를 추가하고 먼저 이 배열에 공간이 있는지 확인합니다. 없으면 요소가 복사되는 새 배열이 생성됩니다. 이 연산의 로그 복잡도는 O(1)입니다. 비슷한 방법이 있습니다 - add(<Index>,<Elelement>) . 목록(배열)의 끝 부분이 아닌 인수로 제공된 인덱스를 사용하여 특정 셀에 요소를 추가합니다. 이 경우 로그 복잡도는 추가되는 위치에 따라 달라집니다.

• 이것이 대략 목록의 시작 부분이었다면 로그 복잡도는 O(N)에 가까울 것입니다. 왜냐하면 새 요소의 오른쪽에 있는 모든 요소는 한 셀 오른쪽으로 이동해야 하기 때문입니다.
• 요소가 중간에 삽입되면 - O(N/2) 왜냐하면 목록 요소의 절반만 한 셀 오른쪽으로 이동하면 됩니다.

즉, 이 방법의 로그 복잡도는 요소가 삽입되는 위치에 따라 O(N)에서 O(1)까지 다양합니다. 2. set(<Index>,<Elelement>) - 목록의 지정된 위치에 요소를 씁니다. 해당 위치에 이미 요소가 있으면 덮어씁니다. 이 연산의 로그 복잡도는 O(1)입니다. 왜냐하면 이동이 없기 때문입니다. 우리가 기억하는 것처럼 복잡도가 O(1)인 배열의 인덱스로 검색하고 요소를 쓰는 것뿐입니다. 3. 제거(<index>) - 내부 배열의 인덱스로 요소를 제거합니다. 목록 끝에 없는 항목을 삭제할 경우 해당 항목 삭제 후 왼쪽 간격을 좁히려면 해당 항목의 오른쪽에 있는 모든 항목을 한 셀 왼쪽으로 이동해야 합니다. 따라서 요소의 절반을 왼쪽으로 1 이동해야 하기 때문에 요소가 중간에 있는 경우(O(N/2)) 로그 복잡도는 add(<Index>,<Elelement>) 와 동일합니다 . 따라서 처음에 있었다면 - O(N)입니다. 음, 마지막에 O(1)이면 아무것도 움직일 필요가 없습니다. 이 주제를 더 깊이 탐구하고 싶은 분들을 위해 ArrayList 클래스 분석이 포함된 기사에 대한 링크를 남겨두겠습니다 .

87. LinkedList의 내부 구조는 무엇입니까?

ArrayList 에 내부 배열의 요소가 포함되어 있으면 LinkedList는 이중 연결 목록 형식입니다. 즉, 각 요소에는 이전 요소( previous )와 다음 요소( next )에 대한 링크가 포함되어 있습니다. 첫 번째 요소에는 이전 요소(첫 번째 요소)에 대한 링크가 없지만 목록의 헤드로 간주되며 LinkedList에는 해당 요소 에 대한 링크가 직접 있습니다. 실제로 마지막 요소에는 다음 요소가 없으며 목록의 꼬리이므로 LinkedList 자체에 직접 링크가 있습니다 . 따라서 목록의 헤드 또는 테일에 액세스하는 로그 복잡도는 O(1)입니다. ArrayList 에서는 목록이 커지면 내부 배열도 늘어나지만 여기서는 모든 것이 더 간단하게 발생합니다. 요소를 추가하면 몇 개의 링크가 간단히 변경됩니다. 가장 많이 사용되는 LinkedlList 메소드 중 일부를 살펴보겠습니다 . 1. add(<Elelement>) - 목록 끝에 추가합니다. 즉, 마지막 요소(5) 뒤에 새 요소에 대한 링크가 next 로 추가됩니다 . 새 요소에는 이전 요소와 마찬가지로 마지막 요소(5)에 대한 링크가 포함됩니다. 이러한 작업의 로그 복잡도는 O(1)입니다. 왜냐하면 마지막 요소에 대한 링크만 필요하고, 기억하는 것처럼 꼬리에는 LinkedList 의 직접 링크가 있고 이에 액세스하는 로그 복잡도가 최소화되기 때문입니다. 2. add(<Index>,<Elelement>) - 인덱스별로 요소를 추가합니다. 예를 들어 목록 중간에 요소를 추가하면 원하는 위치를 찾을 때까지 머리와 꼬리(양쪽)의 요소가 먼저 반복됩니다. 위 그림에서 세 번째와 네 번째 사이에 요소를 삽입하려는 경우 올바른 위치를 검색할 때 세 번째 요소의 다음 링크가 이미 새 요소를 가리킬 것입니다. 새 링크의 경우 이전 링크가 세 번째 링크를 가리킵니다. 따라서 네 번째 요소( 이전 ) 의 링크는 이미 새 요소를 가리키고 새 요소의 다음 링크는 네 번째 요소를 가리킵니다. 이 방법의 로그 복잡도는 새 요소에 지정된 인덱스에 따라 달라집니다.

• 머리나 꼬리에 가까우면 실제로 요소를 반복할 필요가 없기 때문에 O(1)에 접근합니다.
• 중간에 가까우면 O(N/2) - 필요한 요소를 찾을 때까지 머리와 꼬리의 요소가 동시에 정렬됩니다.

3. set(<Index>,<Elelement>) - 목록의 지정된 위치에 요소를 씁니다. 이 연산의 로그 복잡도는 요소가 머리, 꼬리 또는 중앙에 얼마나 가까운지에 따라 O(1)에서 O(N/2)까지 다양합니다. 4. 제거(<index>) - 목록에서 요소를 제거합니다. 기본적으로 제거되는 요소( previous ) 앞에 오는 요소가 제거되는 요소( next ) 뒤에 오는 요소를 참조하도록 만듭니다. 그 반대의 경우도 마찬가지입니다. 삭제되는 요소 뒤에 오는 요소는 삭제되는 요소 앞에 오는 요소를 참조합니다. 결과는 인덱스로 추가하는 것과 반대되는 프로세스입니다( add(<Index>,<Elelement>) ). LinkedList의 내부 구조에 대해 더 자세히 알고 싶다면 이 기사를 읽어 보시기 바랍니다 .

88. HashMap의 내부 구조는 무엇입니까?

아마도 Java 개발자를 인터뷰할 때 가장 인기 있는 질문 중 하나일 것입니다. HashMap v는 키-값 쌍 으로 작동합니다 . HashMapv 자체 에는 어떻게 저장됩니까 ? HashMap 내부에는 노드 배열이 있습니다.

Node<K,V>[] table

기본적으로 배열의 크기는 16이고 요소로 채워질 때마다 두 배로 늘어납니다( LOAD_FACTOR에 도달하면 특정 비율의 충만도, 기본적으로 0.75 입니다 ). 각 노드는 키, 키, 값의 해시와 다음 요소에 대한 링크를 저장합니다. 실제로 "다음 요소에 대한 링크"는 각 요소에 대한 링크가 포함된 단일 연결 목록을 처리한다는 의미입니다. 다음 것. 즉, HashMap은 단일 연결 목록 배열에 데이터를 저장합니다. 하지만 바로 언급하겠습니다. 테이블 배열의 한 셀 에 두 개 이상의 요소로 구성된 유사한 단일 연결 목록에 대한 링크가 있는 경우 이는 좋지 않습니다. 이 현상을 충돌 이라고 합니다 . 하지만 가장 먼저 해야 할 일이 있습니다. put 메소드를 사용하여 새 쌍이 어떻게 저장되는지 살펴보겠습니다 . 먼저 키의 hachCode()를 가져옵니다. 따라서 해시맵이 올바르게 작동하려면 이 메서드가 키로 재정의되는 클래스를 가져와야 합니다. 그런 다음 이 해시 코드는 내부 메서드인 hash() 에서 사용되어 테이블 배열 의 크기 내에서 숫자를 결정합니다 . 다음으로, 수신된 번호를 이용하여 테이블 배열의 특정 셀에 접근합니다 . 여기에는 두 가지 경우가 있습니다.

1. 셀은 비어 있습니다. 새 Node 값이 셀에 저장됩니다 .
2. 셀이 비어 있지 않습니다. 키 값이 비교됩니다. 동일하면 새 노드 값이 이전 값을 덮어쓰고, 같지 않으면 다음 요소에 액세스하여 해당 키와 비교합니다. 새 값이 이전 값을 덮어쓰거나 노드의 끝에 도달할 때까지 계속됩니다. 단일 연결 목록이며 마지막 요소로 저장됩니다.

키로 요소를 검색하는 경우( get(<key>) 메서드 ) 키의 hashCode를 계산한 다음 hash() 를 사용하여 배열 내 해당 값을 사용 하고 결과 숫자를 사용하여 테이블 배열 의 셀을 찾습니다. , 노드를 열거하고 원하는 노드의 키와 현재 노드의 키를 비교하여 검색이 이미 수행되었습니다. 이상적인 상황에서 Map 의 연산은 배열에 액세스하기 때문에 O(1)의 알고리즘 복잡성을 가지며, 기억하는 것처럼 요소 수에 관계없이 배열에 대한 연산의 복잡성은 O(1)입니다. . 그러나 이것은 이상적입니다. 사용되는 배열 셀이 비어 있지 않고(2) 이미 일부 노드가 있는 경우 알고리즘 복잡성은 선형 O(N)으로 변합니다. 이제 올바른 위치를 찾기 전에 요소를 반복해야 하기 때문입니다. 나는 이것을 언급하지 않을 수 없습니다: Java 8부터 단일 연결 목록 노드에 8개 이상의 요소(충돌)가 있으면 이진 트리로 변합니다. 이 경우 알고리즘 복잡도는 더 이상 O(N)이 아니라 O(log(N))입니다. 이는 또 다른 문제입니다. 그렇지 않습니까? HashMap 은 큰 주제이며 사람들은 인터뷰에서 이에 대해 질문하는 것을 좋아합니다. 그러므로 (이빨에서 튀어 나오도록) 자세히 이해하는 것이 좋습니다. 개인적으로 HashMap 질문 없이 인터뷰를 해본 적이 없습니다 . 이 기사에서 HashMap 에 대해 자세히 알아볼 수 있습니다 . 오늘은 여기까지입니다. 계속하겠습니다...