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

PART 1 이제 모든 Java 개발자가 알아야 할 기본 사항에 대해 이야기하겠습니다. 모든 것이 시작되는 고전 지식에 대해. 오늘 저는 인터뷰의 기본 주제 중 하나인 Java의 데이터 구조에 대해 다루고 싶습니다 . 그러니 수풀 주위를 두드리는 대신 시작합시다. 인터뷰 중에 이 주제에 관해 질문을 받을 수 있는 계속되는 질문 목록을 확인하세요.

6. 리스트에 대해 알려주세요

리스트는 리스트라고 불리는 객체의 순서화된 구조를 나타내는 인터페이스입니다. 이 구조의 "트릭"은 List 에 포함된 요소를 인덱스, 즉 List 의 내부 식별자로 삽입, 수정 또는 삭제할 수 있다는 것입니다 . 즉, 인덱스는 "목록의 처음부터 몇 개의 요소가 있는지"를 의미합니다. 첫 번째 List 요소의 인덱스는 0이고, 두 번째 요소의 인덱스는 1입니다. 따라서 다섯 번째 요소는 목록의 시작 부분에서 4개의 요소만큼 떨어져 있습니다. 위에서 언급한 것처럼 항목이 목록에 추가되는 순서가 중요합니다. 이것이 바로 데이터 구조를 리스트 라고 부르는 이유입니다 . 인덱스별로 요소를 작업하는 것을 목표로 하는 이 구조의 고유한 메서드를 나열합니다.

• get - 지정된 위치의 요소를 (인덱스 값으로) 반환합니다.
• 제거 - 지정된 위치의 요소를 제거합니다.
• set - 지정된 위치의 요소를 메서드에 지정된 요소로 바꿉니다.

주요 구현은 ArrayList 및 LinkedList 입니다 . 나중에 그들에 대해 더 자세히 이야기하겠습니다. Vector 는 스레드로부터 안전한 목록이므로 이 클래스의 각 메서드는 동기화됩니다. 그러나 일부 목록 작업을 보호하려면 전체 작업 순서를 동기화해야 한다는 점을 명심하세요. 그리고 개별 작업을 동기화하는 것은 덜 안전하고 훨씬 느립니다. 물론 잠금이 필요하지 않은 경우에도 Vector 에는 잠금 오버헤드가 있습니다. 따라서 이 클래스는 이제 더 이상 사용되지 않는 것으로 간주되어 사용되지 않습니다. 그런데 ArrayList는 Vector 와 유사 하지만 잠금을 사용하지 않으므로 모든 곳에서 사용됩니다. Stack은 하나의 기본 생성자와 Vector 클래스 의 모든 메서드 및 자체 메서드 몇 개를 포함하는 Vector 클래스 의 하위 클래스입니다 . 이에 대해서는 나중에 설명하겠습니다. 예를 들어 프로세스를 문서가 포함된 폴더 스택으로 상상할 수 있습니다. 하나의 폴더를 스택 맨 위에 배치하면 맨 위부터 시작하여 역순으로만 폴더를 가져올 수 있습니다. 실제로 이것은 LIFO 유형의 메커니즘입니다 . 즉, Last In First Out(후입선출) 방식 으로 , 마지막에 온 사람이 먼저 나가게 됩니다. 스택은 자체 메서드를 구현합니다.

• push - 전달된 요소를 스택의 맨 위에 추가합니다.
• peek - 스택의 맨 위에 있는 요소를 반환합니다.
• pop - 스택의 맨 위에 있는 요소도 반환하지만 제거합니다.
• 비어 있음 - 스택이 비어 있는지 확인합니다. - true 인지 아닌지 확인합니다 . - false
• 검색 - 스택에서 특정 요소를 검색합니다. 요소가 발견되면 스택 상단을 기준으로 하는 해당 시퀀스 번호가 반환됩니다. 요소를 찾을 수 없으면 -1 값이 반환됩니다.

현재 Stack 하위 클래스 는 단순성과 유연성으로 인해 실제로 사용되지 않지만 그럼에도 불구하고 발생할 수 있습니다. 예를 들어, 오류가 발생하고 콘솔에 이에 대한 메시지 스택이 표시됩니다. 이 문서 에서 스택과 큐에 대한 자세한 내용을 읽을 수 있습니다 .

7. 지도에 대해 알려주세요

위에서 설명한 것처럼 맵은 인터페이스와 해당 구현의 별도 구조를 갖는 컬렉션입니다. 여기에는 값이 한 번에 하나씩 저장되지 않고 "키-값" 쌍으로 저장되기 때문에 별개입니다. 기본 지도 방법 :

• put(K key, V value) - 맵에 요소를 추가합니다.
• get(Object key) - 키로 값을 검색합니다.
• containKey(Object key) — 이 키가 있는지 맵을 확인합니다.
• containValue(Object value) - 이 값이 있는지 맵을 확인합니다.
• 제거(객체 키) - 해당 키로 값을 제거합니다.

보시다시피 대부분의 작업은 키를 사용하여 수행됩니다. 일반적으로 불변 객체는 키로 선택됩니다 . 이 객체의 일반적인 예는 String 입니다 . 기본 지도 구현 :

1. HashMap - 값을 임의의 순서로 저장하도록 설계되었지만 맵 요소를 빠르게 검색할 수 있습니다. null 키워드를 사용하여 키를 지정할 수 있지만 한 번만 지정할 수 있습니다. 동일한 키를 가진 쌍은 서로 위에 기록됩니다. 주요 조건은 키의 고유성입니다. 값이 반복될 수 있습니다(여러 개의 null 값이 있을 수 있음).
2. LinkedHashMap 은 추가된 순서대로 값을 저장하는 HashMap과 유사합니다 . 따라서 LinkedList 와 마찬가지로 헤더 (이중 연결 목록의 헤드)가 있습니다 . 초기화되면 자신을 가리킵니다.

   LinkedHashMap에는 반복자가 사용될 때 요소에 액세스하는 방법을 지정하는 accessOrder 도 있습니다 . accessOrder가 false 이면 요소가 삽입된 순서대로 액세스가 수행됩니다. true 인 경우 요소는 마지막으로 액세스한 순서대로 정렬됩니다(마지막으로 액세스한 요소는 끝에 배치됩니다).

3. TreeMap 은 키 값을 기준으로 요소를 정렬하는 Map 입니다 . TreeSet 과 유사 하지만 키 값을 기반으로 하는 쌍입니다. TreeMap 정렬 규칙을 설정하려면 키가 Comparable 인터페이스를 구현해야 합니다 . 그렇지 않으면 내부에 TreeMap 객체로 구현된 TreeSet인 키 지향 비교기 (TreeMap 생성자에 지정된 것 ) 가 있어야 하며 실제로 모든 마법이 발생합니다.

   TreeMap 기능에 대한 기사에서 Red-Black 트리를 사용하여 TreeMap에서 정렬하는 방법에 대해 자세히 알아볼 수 있습니다 .

4. Hashtable은 HashMap 과 유사 하지만 null이 키나 값으로 저장되는 것을 허용하지 않습니다. 멀티스레딩 관점에서 세심하게 동기화되므로 멀티스레딩 관점에서도 안전하다는 의미입니다. 하지만 이 구현은 오래되고 느리기 때문에 이제 새 프로젝트에서는 Hashtable을 볼 수 없습니다 .

8. ArrayList 대 LinkedList. 어느 것을 사용하는 것이 바람직합니까?

이 질문은 아마도 데이터 구조에서 가장 인기 있는 질문일 것이며 몇 가지 함정을 수반합니다. 답변하기 전에 이러한 데이터 구조에 대해 자세히 알아보겠습니다. ArrayList는 List 인터페이스를 구현 하고 필요에 따라 확장되는 내부 배열에서 작동합니다. 내부 배열이 완전히 채워져 새 요소를 삽입해야 하는 경우 (oldSize * 1.5) +1 크기의 새 배열이 생성됩니다. 그런 다음 이전 배열의 모든 데이터가 새 + 새 요소에 복사되고 이전 배열은 가비지 수집기에 의해 삭제됩니다 . add 메소드는 배열의 마지막 빈 셀에 요소를 추가합니다. 즉, 이미 3개의 요소가 있는 경우 네 번째 셀에 다음 요소가 추가됩니다. 기본 메소드의 성능을 살펴보겠습니다.

• get(int index) - 배열의 요소를 인덱스로 가져오는 것이 O(1) 에서 가장 빠릅니다 .
• add(Object obj) - 내부 배열에 새 요소를 위한 충분한 공간이 있는 경우 추가가 마지막 셀을 대상으로 하기 때문에 일반적인 삽입의 경우 O(1) 시간이 소요됩니다.

  새 배열을 만들고 내용을 복사해야 하는 경우 시간은 배열 O(n) 의 요소 수에 정비례합니다 .

• 제거(int 인덱스) - 예를 들어 가운데에서 요소를 제거하면 O(n/2) 시간이 걸립니다. 요소를 오른쪽으로 한 셀 뒤로 이동해야 하기 때문입니다. 따라서 목록의 처음부터 삭제하면 O(n), 끝에서 - O(1);
• add(int index, Object obj) - 삭제와 유사한 상황: 중간에 추가할 때 오른쪽에 있는 요소를 한 셀 앞으로 이동해야 하므로 시간은 O(n/2)입니다. 물론, 처음부터 - O(n), 끝부터 - O(1);
• set(int index, Object obj) - 여기서 상황은 다릅니다. 원하는 요소만 찾아 나머지를 이동하지 않고 덮어쓰면 되므로 O(1)입니다.

이 기사 에서 ArrayList 에 대해 자세히 알아보세요 . LinkedList는 List 와 Queue 라는 두 가지 인터페이스를 동시에 구현하므로 두 데이터 구조에 고유한 속성과 메서드가 있습니다. List에서 그는 인덱스별로 요소에 액세스했고, Queue에서 "머리"와 "꼬리"가 있는 요소에 액세스했습니다. 내부적으로는 이중 연결 리스트를 나타내는 데이터 구조로 구현됩니다. 즉, "꼬리"와 "머리"를 제외한 각 요소에는 다음 및 이전 요소에 대한 링크가 있습니다.

• get(int index) - 목록 중간에 있는 요소를 검색할 때 원하는 요소를 찾을 때까지 모든 요소를 ​​순서대로 검색하기 시작합니다. 논리적으로 검색에는 O(n/2) 가 필요 하지만 LinkedList에도 꼬리가 있으므로 검색이 양쪽에서 동시에 수행됩니다. 따라서 시간은 O(n/4) 로 단축됩니다 .

  요소가 목록의 시작 부분이나 끝 부분에 가까우면 시간은 O(1) 이 됩니다 .

• add(Object obj) - 새 요소를 추가할 때 "tail" 요소에는 추가된 다음 요소에 대한 링크가 있고 새 요소는 이 이전 요소에 대한 링크를 받아 새 "tail"이 됩니다. 따라서 시간은 O(1) 이 됩니다 .
• 제거(int index) - get(int index) 메소드 와 유사한 논리입니다 . 목록 중간에서 요소를 제거하려면 먼저 해당 요소를 찾아야 합니다. 이것은 다시 O(n/4) 이지만, 삭제 자체는 실제로 아무것도 사용하지 않습니다. 왜냐하면 이웃 객체의 포인터만 변경하기 때문입니다(서로 참조하기 시작함). 요소가 시작이나 끝에 있으면 다시 - O(1) ;
• add(int index, Object obj) 및 set(int index, Object obj) - 대부분의 시간이 요소를 검색하는 데 소비되므로 메소드는 get(int index) 와 동일한 시간 복잡도를 갖습니다. 따라서 목록 중간의 경우 - O(n/4) , 처음의 경우 - O(1)입니다.

LinkedList 작업에 대한 자세한 내용은 이 문서 에 설명되어 있습니다 . 이 모든 것을 표로 살펴보겠습니다. 이미 이해하셨겠지만, 이 질문에 명확하게 대답하는 것은 불가능합니다. 결국, 서로 다른 상황에서는 서로 다른 속도로 작동합니다. 그러므로 이런 질문을 받으면 이 목록이 무엇에 중점을 두고 어떤 작업을 가장 자주 수행할지 즉시 질문해야 합니다. 이것부터 시작하여 답변을 하되, 왜 그런지에 대한 설명도 함께 제공하십시오. 비교를 요약해 보겠습니다. ArrayList:

• 가장 빈번한 작업이 요소 검색, 요소 덮어쓰기인 경우 최선의 선택입니다.
• 작업이 시작-중간에서 삽입 및 삭제인 경우 최악의 선택입니다. 오른쪽에 있는 요소의 이동 작업이 발생하기 때문입니다.

링크드리스트:

• 빈번한 작업이 시작 중간에서 삽입 및 삭제되는 경우 최선의 선택입니다.
• 가장 일반적인 작업이 검색인 경우 최악의 선택입니다.

9. HashMap에 요소는 어떻게 저장되나요?

HashMap 컬렉션에는 내부 배열 Node[] 테이블이 포함되어 있으며 , 그 셀은 버킷 이라고도 합니다 . 노드에는 다음이 포함됩니다.

• 키 - 키에 대한 링크,
• 값 - 값에 대한 참조
• 해시 - 해시 값,
• next - 다음 Node 에 연결합니다 .

table[] 배열 의 한 셀에는 다음 Node 요소에 대한 링크가 있는 Node 객체 에 대한 참조가 포함될 수 있으며 다른 Node 요소에 대한 링크도 있을 수 있습니다. 결과적으로 이러한 Node 요소는 다음 을 형성할 수 있습니다 . 단일 연결 리스트(Single Linked List) , 다음 요소에 대한 링크가 포함된 요소입니다. 이 경우 동일한 체인에 있는 요소의 해시 값은 동일합니다. 잠시 이야기를 나눈 후 HashMap 에 요소가 저장되는 방식을 살펴보겠습니다 .

1. 키에 null 이 있는지 확인됩니다 . null 인 경우 null에 대한 해시 코드가 항상 0이므로 키는 table[0] 셀 에 저장됩니다 .
2. 키가 null 이 아니면 키 객체의 hashcode() 메서드가 호출되어 해당 해시 코드를 반환합니다. 이 해시 코드는 Node 객체가 저장될 배열 셀을 결정하는 데 사용됩니다.
3. 다음으로, 이 해시코드는 해시코드를 계산하는 내부 hash() 메서드에 배치되지만 크기는 table[] 배열 내에 있습니다 .
4. 다음으로, 해시 값에 따라 Node가 table[] 배열의 특정 셀에 배치됩니다 .
5. 현재 Node 요소를 저장하는 데 사용된 table [] 셀이 비어 있지 않지만 이미 일부 요소가 있는 경우 마지막 요소에 도달할 때까지 Node 요소가 다음 값 에 대해 반복됩니다. 즉, 다음 필드가 null 인 필드 입니다 .

   이 검색 중에 보호되는 Node 개체 의 키는 검색 중인 개체의 키와 비교됩니다.

   • 일치하는 항목이 발견되면 검색이 종료되고 새 노드는 일치하는 항목이 발견된 노드를 덮어씁니다 (해당 값 필드만 덮어쓰게 됩니다 ).
   • 일치하는 키가 없으면 새 노드가 이 목록의 마지막 노드가 되고 이전 노드 에는 다음 링크가 포함됩니다 .

인터뷰 중에 종종 나오는 질문: 갈등이란 무엇입니까 ? table[] 배열의 셀이 하나의 요소가 아닌 두 개 이상의 체인을 저장하는 상황을 충돌 이라고 합니다 . 단일 table[] 셀 에 하나의 요소만 저장되는 일반적인 경우 HashMap 의 요소에 액세스하는 데는 일정한 O(1) 시간 복잡도가 있습니다 . 그러나 원하는 요소가 있는 셀에 요소 체인( collision )이 포함되어 있으면 O(n)이 됩니다 . 이 경우 시간은 정렬되는 요소 수에 정비례하기 때문입니다.

10. 반복자를 설명하세요

위의 컬렉션 계층 매핑 다이어그램 에서 컬렉션 인터페이스는 전체 계층이 시작되는 곳이지만 실제로는 그렇지 않습니다. 컬렉션은 Iterator<E> 인터페이스 를 구현하는 객체를 반환하는 iterator() 메서드를 사용하여 인터페이스에서 상속됩니다 . Iterator 인터페이스는 다음과 같습니다.

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - 이 메소드를 호출하면 다음 요소를 얻을 수 있습니다. hasNext() - 다음 요소가 있는지, 컬렉션의 끝에 도달했는지 여부를 확인할 수 있습니다. 그리고 아직 요소가 있으면 hasNext()는 true를 반환합니다 . 일반적으로 hasNext()는 next() 메서드 보다 먼저 호출됩니다 . 왜냐하면 next()는 컬렉션의 끝에 도달하면 NoSuchElementException을 발생시키기 때문입니다 . 제거() - next() 에 대한 마지막 호출로 검색된 요소를 제거합니다 . Iterator의 목적은 요소를 반복하는 것입니다. 예를 들어:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

실제로 for-each 루프는 반복자를 사용하여 내부적으로 구현됩니다. 이에 대한 자세한 내용은 여기에서 읽을 수 있습니다 . List는 자체 버전의 반복자를 제공하지만 더 멋지고 정교한 버전인 ListIterator 를 제공합니다 . 이 인터페이스는 Iterator를 확장 하고 추가 메서드가 있습니다.

• hasPrevious는 컬렉션에 이전 요소가 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
• 이전 요소는 현재 요소를 반환하고 이전 요소로 이동합니다. 아무것도 없으면 NoSuchElementException이 발생합니다.
• add는 next() 에 대한 다음 호출에서 반환될 요소 앞에 전달된 객체를 삽입합니다 .
• set은 현재 요소에 전달된 객체에 대한 참조를 할당합니다.
• nextIndex는 다음 요소의 인덱스를 반환합니다. 그러한 것이 없으면 목록의 크기가 반환됩니다.
• PreviousIndex는 이전 요소의 인덱스를 반환합니다. 아무것도 없으면 숫자 -1이 반환됩니다.

글쎄, 오늘은 그게 다야. 이 기사를 읽은 후 개발자가 되겠다는 소중한 꿈에 더욱 가까워지기를 바랍니다.