자료구조

시간복잡도

알고리즘 효율성을 판단하는 지표로써,
알고리즘 수행에 걸리는 시간이 아닌
연산들이 몇번 이루어지는가 에 대한 지표이다.
메모리 사용량을 분석한 결과는 공간복잡도 이다.

• Big-O 표기법
  • 빠른 순서
  • O(1) : 데이터의 크기에 상관없이 언제나 일정한 시간이 걸림 (index를 통한 접근)
  • O(log₂ n) : 데이터가 커질수록 시간이 로그만큼 짧아짐 (이진탐색 / Tree)
  • O(n) : 데이터의 크기에 비례해 처리시간이 증가함 (선형탐색 / for문)
  • O(n log₂ n) : 데이터가 커질수록 시간이 로그 배 만큼 늘어남 (퀵/병합/힙 정렬)
  • O(n²): 데이터의 크기가 커질수록 처리시간이 기하급수적으로 늘어남 (이중for문 / 삽입/버블/선택 정렬)
  • O(2ⁿ) : 데이터의 크기가 커질수록 처리시간이 기하급수적으로 늘어남 (피보나치 수열)

Hash

임의의 크기를 가진 데이터를 고정된 크기의 데이터로 바꾸는 것.
단방향 암호화 기법으로 해시함수 또는 해시 알고리즘를 이용해 고정된 길이의 비트열로 변경한다.
10 X 10 = 100 이라는 것은 쉽게 알지만, 몇과 몇을 곱해야 100이 나오는지는 많은 경우의 수가 나오는데
해싱은 이런식으로 복호화가 어렵다.
하지만 동일한 내용은 항상 같은 해시값이 나온다는 단점이 있다.
예를들면 동일한 비밀번호는 항상 해시값이 같다.

• HashTable
  key와 value의 쌍으로 이루어진 데이터 구조이다.
  해시충돌이 일어나지 않는 가정 하에 평균 시간복잡도 O(1)로 효율적이다.
  이는 배열에서 index를 알고 접근하는 것과 동일한 시간복잡도를 보인다.

• key : 해시함수의 input이 되는 고유 값, 키는 해시함수를 통해 해시로 변경되고 index 역할을 하게된다.
• value : 저장소(버킷, 슬롯)에 최종적으로 저장되는 값.
• Hash : 임의의 값을 가지는 key값을 고정된 길이로 변환하는 것
• Hash Function : 임의의 값을 고정된 크기의 값으로 변환하는 함수. key -> hash
• 저장소(Bucket, Slot) : Hash Table 에서 하나의 데이터가 저장되는 공간

• 해시충돌 : 서로 다른 key가 같은 hash값이 되는 경우

  • 데이터 저장
    해시함수를 이용해 키값을 해시로 변경한 후 미리 준비해둔 저장소(버킷, 슬롯)중
    알맞는 해시값을 찾아 value를 저장한다.
    이 과정의 시간복잡도는 O(1) 이다.

  • 데이터 삭제
    버킷에서 삭제하려고 하는 key와 매핑되는 value값을 찾아서 삭제한다
    이 과정의 시간복잡도는 O(1) 이다.

  • 데이터 검색
    key를 이용해 value를 찾아내는 과정.
    먼저 key값과 해시함수를 이용해 hash를 찾아내고 해당 hash로 value를 찾는다.
    이 과정의 시간복잡도는 O(1) 이다.

• 자바의 Hash?
  • 자바에서는 Object클래스의 hashCode() 메서드로 모든 객체의 해시코드를 쉽게 구할 수 있다
  • 자바는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 중복되지 않는 값을 제공한다.
  • String의 경우 Object로부터 상속받은 hashCode()를 오버라이딩 하여 문자열의 내용으로 해시코드를 만들어 낸다. 그렇기 때문에 다른 인스턴스의 String이어도 문자열이 같다면 같은 해시코드값을 가진다.
  • HashMap도 같은 방법으로 객체를 구별하기 때문에 이미 존재하는 키와 동일한 값을 저장하면 기존의 값을 덮어쓰게 된다.

단점

• 정렬이나 순차적인 데이터 저장에 적합하지 않다
• 데이터가 저장되기 전에 저장공간을 확보해야 하기 때문에 공간효율성이 떨어진다.
• Hash Function이 복잡할수록 연산속도가 증가한다.
• 해시충돌이 발생할 경우 최악의 경우 시간복잡도가 O(N) 에 점점 수렴함

HashMap

thread-safe 하지 않아 싱글스레드 환경에 적합하며, 동기화 처리를 하지않기 때문에 탐색속도가 가장 빠르다.

• Key, Value 에 null을 허용한다.
• 동기화를 보장하지 않는다.

HashTable

thread-safe 하기 때문에 멀티스레드 환경에 적합하며, get(), put(), remove()등에 synchronized 키워드가
붙어있다. 스레드간 락을 걸기 때문에 데이터의 무결성을 보장하지만 synchronized 때문에 느리다.

• Key, Value 에 null을 허용하지 않는다.
• 동기화를 보장한다.

ConcurrentHashMap

HashMap의 동기화 문제를 보완하기 위해 나왔다. 동기화 처리를 할때, data를 조작하는 경우에만
선택적으로 락을건다. 락의 범위는 HashMap의 Bucket수준이다.
즉, data 수정작업에만 동기화 되며, read작업은 hashMap과 동일한 성능을 제공한다.

• Key, Value 에 null을 허용하지 않는다.
• 동기화를 보장한다.

그래서 뭐쓰는데?

싱글스레드 에선 HashMap을, 멀티스레드 환경에서 동기화처리가 필요하다면 스레드간 락을거는 HashTable보다
Entry 아이템별로 락을 거는 ConcurrentHashMap 을 쓰는게 좋다.
완벽한 비교는 아니지만 비슷한 맥락으로 비유해 보자면 HashTable / ConcurrentHashMap 의 차이는
테이블 락 과도 비유해 볼 수 있다. 모든 작업에 동기화를 거는건 테이블락과 비슷할 정도로 비효율 적이기 때문에

하지만?

우리는 Thread-safe 하지 않은 HashMap을 자주쓴다. 그래도 동시성 문제에서 어느정도 자유로웠을 것이다.
이건 왜그럴까?

java.util.concurrent 라는 패키지가 존재한다.

이펙티브자바 Item80 : 스레드보다는 실행자, 태스크, 스트림을 애용하라.

작업 큐를 손수 만드는 일은 삼가해야 하고, 스레드를 직접 다루는것도 일반적으로 삼가하라고 한다.
즉, 실행자 프레임워크를 통해 작업하라는 말이다.
대부분 request와 response의 스레드 생명주기를 가지는 웹 어플리케이션을 개발할때 스레드풀을 사용하기 때문에 큰 신경을 쓰지 않아도 thread-safe 한 것이다.
물론 싱글톤 이라던가 여러 스레드가 동일한 자원에 접근하여 수정하는 작업에선 따로 처리를 해줘야겠지?

Array

메모리상에 데이터를 순차적으로 배치하는 자료구조
동일한 type의 데이터를 여러개 나열한 선형구조이다.
index를 사용할 수 있으며, index값을 알고 접근할 경우 시간복잡도는 O(1)이다.

• 특징
  • 선언할 때 지정한 크기가 고정된다.
  • 선언된 값은 다시 배열을 선언하지 않는이상 변경할 수 없다.
  • 삽입 순서대로 저장된다. (새로운 데이터는 배열 맨 끝에 들어감)
  • 중복 가능

• 단점
  • 처음에 선언한 배열의 크기를 수정할 수 없다.
  • 데이터의 추가 / 삭제를 할 경우 뒤에있는 데이터들을 앞으로 옮기는 작업이 추가로 필요하다.
    • 원소의 개수가 1000개인 배열에서 0번 index를 삭제하면, 삭제를 하는 작업 외에 (1000 - 1)만큼의 원소를 이동하는 추가작업 필요

• 활용?
  • 순차적인 데이터를 저장할 때 유용
  • 특정요소를 빠르게 읽을 때 (index값이 필요함)
  • 데이터 사이즈가 바뀌지 않거나 데이터의 추가 / 삭제가 자주 일어나지 않을 때
  • 이펙티브 자바에서는 배열보다 리스트를 사용하라 라는 챕터가 있다.
    • 간단하게 말해 타입실수를 컴파일 단계에서 확인할 수 있냐 없냐의 차이
    • 배열의 성능이점보다 안전함을 더 중요하게 생각하는듯 하다.

List

데이터를 순차적으로 저장하는 선형구조의 자료구조
데이터가 삭제되도 빈공간으로 남겨두고 index를 유지하는 배열과 달리 빈공간을 남겨두지 않기 때문에
낭비되는 메모리가 없고 빈틈없는 데이터 구조를 가질 수 있다.
또한 배열과 다르게 데이터를 담을 공간의 추가가 가능하다.
하지만 배열처럼 고정된 index를 식별자로 이용할 수 없다.

• 선형구조 : 데이터가 순차적으로 저장되고 끊어지지 않으며 빈틈없이 데이터를 적재하는,
  보기에 한줄로 계속되기 때문에 마치 선과 같은 형태를 띈다 하여 선형구조라 함
  

• ArrayList
  • 배열을 이용해 구현된 List
  • 데이터를 추가/삭제 할때, 연속적인 물리적위치를 유지하기 위해 원소를 옮기는 추가작업이 필요하다.
    • 원소의 개수가 1000개인 ArrayList에서 0번 index를 삭제하면,
      삭제를 하는 작업 외에 (1000 - 1)만큼의 원소를 이동하는 추가작업이 필요하다.
  • 데이터 조회의 시간복잡도는 O(1)이다.
  • 데이터 탐색에 효율적이다.

• LinkedList
  • 연결 포인터를 이용해 구현한다.
    • 기본단위는 노드이다
    • 노드 : 자료(Data) + 링크(Link)
  • 각 데이터마다 다음 순서의 데이터가 뭔지 알려주는 포인터가 존재하는 구조이다.
  • 데이터를 추가/삭제 할때, 특정 노드의 링크필드(다음 노드주소)만 수정하면 된다.
    즉, 노드의 포인트가 가리키는 것만 바꾸면 되기 때문에 시간복잡도는 O(1)이다.
  • index가 없기때문에 데이터 조회의 시간복잡도는 모든 노드를 순회하는 O(n)이다.
  • 데이터의 추가/삭제에 효율적이다.

• 활용?
  • ArrayList : 탐색에 유용
    • 데이터를 중간에 추가 / 삭제하는 경우가 적다면 사용을 고려해보자.
  • LinkedList : 추가/삭제에 유용
    • 데이터를 중간에 추가 / 삭제하는 경우가 많다면 사용을 고려해보자.

Set

데이터의 집합이며 순서가 없고 집합이므로 중복된 데이터를 허용하지 않는다.
index가 따로 존재하지 않기 때문에 Iterator를 사용한다.

• 특징
  • 순서가 없고 중복을 허용하지 않는다.
  • 자바의 Set
    • Hash알고리즘을 이용한 HashSet
    • 이진탐색트리를 사용해 오름차순정렬을 해주는 TreeSet
    • 순서를 부여해주는 LinkedHashSet
  • 일반적으로 HashSet > TreeSet > LinkedHashSet 순으로 빠르다.

• HashSet
  • 입력된 키를 해시알고리즘으로 해시코드로 변환한다.
  • 그 후 해시코드를 인덱스로 bucket저장소에 저장한다.
  • 값이 키와 동일하게 설정된다.
  • 순서를 보장하지 않는다.

• TreeSet
  • 이진 탐색 트리(Red-Black Tree)를 기반으로 한다.
  • 오름차순으로 데이터를 저장한다.
  • 추가 / 삭제는 LinkedHashSet보다 느리지만 검색 / 정렬은 더 효율적이다.

• LinkedHashSet
  • 데이터가 들어간 순서대로 저장된다.

• 활용?
  • 중복된 값을 골라낼때 유용하다.
  • 빠른 탐색에 유용하다.
    • 특정 요소의 값을 찾기보다는 요소가 집합에 존재하는지 확인할 때
    • List의 contains 시간복잡도는 O(n)이지만 Set은 O(1)

Map

순차적으로 메모리에 데이터를 저장하는 Array와 List와는 달리,
Key와 Value로 이루어진 자료구조이다.

• 특징
  • 데이터의 순서가 없다.
  • Key는 중복을 허용하지 않는다.
  • List와 마찬가지로 인터페이스이다.

• Hash Table / Map
  • Hash를 Key로 가지는 Map, 앞에서 설명했듯 가장 큰 차이점은 동기화와 null이다.
    • HashMap : 동기화를 지원하지 않고 Key 와 Value에 null이 허용된다.
    • HashTable : 동기화를 지원하고 Key 와 Value에 null이 허용되지 않는다.

• LinkedHashMap
  • 데이터가 들어간 순서대로 저장된다.

• TreeMap
  • 이진검색 트리구조, Key를 기준으로 오름차순으로 저장된다.
    • 숫자 > 대문자 > 소문자 > 한글
  • 정렬된 순서로 저장하기 때문에 검색에는 빠르지만 저장 시 효율이 떨어진다.

• 활용?
  • 저장하고 싶은 데이터가 특별한 Key 값을 가질 때 - 검색에 유용
  • 특정 데이터를 순간마다 캐치해야 할 때
  • 특정 품목의 갯수를 카운트 해야할 때

Stack

Queue

Tree

Graph