<Interview> 4. 자료구조 정리

0. 자료구조

• 처리해야 되는 데이터들을 효율적으로 관리하기 위해 사용하는 방법

1. 해시테이블

• 해시알고리즘을 이용하여 검색시간을 단축하는 key-value 형태의 자료구조이다.

• 해시함수는 어떤 키 값을 받아서 숫자로 반환하는 함, 해시함수는 반환값에 대해 일관성, 독립성을 가져야한다.(간단하게는 아스키코드)

• 검색키값을 해시함수를 통해 해시코드로 변환하고 이값을 이용해서 배열의 인덱스로 환산해서 데이터에 접근하는 것을 말한다.

• 테이블의 인덱스들을 bucket, 값을 Entity라고 한다.

  가. 문제점 & 방법

  • 해시코드는 결국 정수 이므로 중복이 발생 할수도 있다.(Collusion)
  • Chaning 방식은 LinkedList 이용하여 연결하는 형태로 구현한다. 리스트 안에는 key-value 모두 가지고 있어야 한다.
  • JAVA 8버전 부터는 노드가 8개 이하면 LinkedList 초과하면 Tree에 데이터를 저장된다.
  • Open addressing 방식은 비어있는 해시테이블의 인덱스를 활용하는 방법으로 메모리를 효율적으로 사용할 수 있다.
  • 종류에는 Linear Probing이 있는데 bucket 사용중일 경우 그 다음 인덱스부터 빈방을 찾아 저장하는 방법이다.

2. ArrayList & LinkedList

• Array는 정적인 배열이므로 동적으로 크기를 늘리거나 줄이거나 할때 직접 새로 만들어야하는 단점이 있다.
• Vector는 자동동기화 기능때문에 성능저하로 사용하지 않는다.
• ArrayList는 배열을 이용해서 resize하는 방식으로 추가 삭제를 할떄 임시배멸에 작성 후 데이터를 복사하는 방법을 사용한다.
• LinkedList는 각각의 데이터들을 노드로 취급하고 노드안에는 다음 노드의 주소값으로 연결하는 방식이다.(불연속적 데이터)

가. 특징

• ArrayList는 배열을 이용하기 때문에 검색 Index로 접근하게 되므로 속도가 빠르다.
• LinkedList는 값을 찾기 위해서는 첫 노드부터 탐색해야 하므로 속도가 느리다.
• ArrayList는 추가 삭제 할때 배열복사 과정이 있기 때문에 O(N) 최대 크기의 한계가 존재한다.
• LinkedList는 추가 삭제시 참조값만 변경하면 되기 때문에 위치에 관계없이 속도가 빠르다. 검색 + O(N)
• LinkedList는 참조객체를 이용해야 하므로 메모리 낭비가 있다.

3. 스택 & 큐

• 스택은 LIFO 방식으로가자 나중에 들어간 데이터를 제일 먼저 빼는 방식
• 사용처로는 수식계산, 브라우저 뒤로 앞으로, 함수 콜 스택 등
• 큐는 FIFO 방식으로 먼저 들어간 데이터가 먼처 처리되는 방식
• 사용처는 버퍼, 은행 접수표 등
• 큐의 배열을 재배치 해야하는 문제가 있어 %를 키워드로 하는 원형큐 방식이 있다.

4. 트리

• 하나의 루트 노드를 가지고 뻣어나가는 형태를 가진 비선형 자료구조
• 사용처는 리눅스 디렉토리 구조
• 이진트리는 상위노드가 두개 이하의 하위 노드를 가지는 것이다. 완전이진트리는 왼쪽부터 차례로 삽인하는 트리

5. 힙

• 최댓값 & 최소값을 빠르게 찾기위해 완전이진트리를 이용한 자료구조이다.
• 힙은 중복값을 허용하고 상위노드의 인덱스와 하위노드의 인덱스를 비교하여 트리를 구성한다.
• 최대힙은 상위 인덱스가 큰것 최소힙은 작은 것이다.
• 힙의 데이터 삽입은 가장 끝에 삽입되어 상위 인덱스랑 비교를 통해 자리를 바꿔주는 방식을 취한다.

6. 그래프

• 다익스트라 : 최단경로를 찾는 알고리즘으로 시작정점에서 인접정점의 가중치가 가장 최소가 되는 선택하는 그리디 방식이다.

7. Hash collections

가. HashMap과 TreeMap

• HashMap은 해시알고리즘을 이용하여 key값을 정수로 변환하여 Node 배열에 인덱스로 사용하여 값을 저장한다.
• TreeMap은 key값을 정렬하여 Tree 구조로 데이터를 저장한다.

나. HashMap과 HashTable과 ConcurrentHashMap

• HashMap은 데이터 변경시 동기화를 지원하지 않는다. 단일스레드 환경에서 속도가 빠르다.
• HashTable은 데이터 변경하는 메소드들이 동기화를 지원한다. 멀티스레드 환경에서 데이터의 무결성을 지원한다.
• ConcurrentHashMap은 Map전체에 동기화를 걸지않고 부분부분 나누어 거는 형태로 성능이 좋다.

참고 & 출처

• http://www.nextree.co.kr/p6506/
• https://www.youtube.com/watch?v=Vi0hauJemxA
• https://bcho.tistory.com/1072
• https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
• https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations
• https://ooz.co.kr/71
• Hello Coding 그림으로 개념을 이해하는 알고리즘