Data Structure - YunByungKwan/Fundamental GitHub Wiki

Data Structure

배열(Array)

배열은 연속된 메모리 공간에 데이터를 저장하는 자료 구조이구요.
크기가 고정되어 있습니다.
그리고 인덱스를 통해서 데이터에 접근할 수 있는 특징이 있습니다.

리스트(List)

리스트는 데이터를 순차적으로 저장하는 선형 자료 구조이구요.
불연속적인 메모리 공간에 데이터를 저장하며 크기는 동적입니다.
그리고 포인터를 통해서 다음 데이터의 위치를 가리키고 있는 특징이 있습니다.
그리고 데이터의 추가/삭제는 빠르지만 검색은 느린 특징이 있습니다.

  • ArrayList
    ArrayList는 배열처럼 인덱스를 사용하고, 크기를 동적으로 늘릴 수 있습니다.
    단점으로는 중간에 데이터를 삽입/삭제할 경우 나머지 데이터들을 shift해야 하는 단점이 있습니다.

  • LinkedList
    LinkedList는 포인터를 통해서 다음 데이터의 위치를 가리키고 있는 특징이 있습니다.
    그리고 데이터의 삽입/삭제는 빠르지만 탐색이 느린 단점이 있습니다.

Set

  • Set은 데이터 삽입 순서대로 저장되지 않는다
  • 중복을 허용하지 않습니다

Map

Map은 데이터를 (Key, Value)형식으로 저장할 수 있는 자료 구조입니다.
Key는 중복이 불가능하고, Value는 중복이 가능한 특징을 가지고 있습니다.

  • HashMap
    Java의 HashMapHash Table과 거의 비슷합니다.(HashMap은 동기화 X)
    데이터의 순서를 보장하지 않으며,
    시간복잡도의 경우, get()/put()은 O(1), 순회는 O(capacity + size)이 걸리는 특징이 있습니다.
    2개의 parameter(init capacity, load factor)를 가지고 있습니다.
    • init capacity: Hash Table이 생성될 때 버킷의 수
    • load factor: capacity가 자동으로 늘어나기 전까지 hash table이 얼마만큼 늘어날 수 있는지 나타내는 척도

해시(Hash)

해시는 임의의 길이인 데이터(Key)를 고정된 길이의 데이터(Value)로 변환하는 것을 말합니다.

  • Hash Table
    (Key, Value)로 데이터를 저장하는 자료 구조입니다. 내부적으로 배열(버킷)을 사용하여 데이터를 저장함 예를 들어, ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장할 경우 index = hash_function("John Smith")%16으로 구하고 array[index] = "521-1234"로 저장한다. Hash Table의 원소 수가 load factor * capacity를 초과하게 되면 Hash Table은 현재 크기 *2 로 다시 생성된다. Java의 hashtable은 key, value에 null을 허용하지 않지만 hashMap은 null을 허용한다 Java8의 Hash Table은 Self-Balancing Binary Search Tree 자료 구조를 사용해 Chaining 방식을 구현하였다.

  • Hash Function
    임의의 길이를 가진 데이터(Key)를 고정된 길이의 데이터(Value)로 매핑하는 함수를 말합니다. 다시 말하면 키에 대한 해시값을 만드는 함수라고 할 수 있구요. 간단하게는 Key를 해시테이블 크기로 나눠서 나온 Value를 인덱스로써 사용할 수 있습니다.

  • 충돌
    충돌이 발생할 경우 아래의 방법들을 사용합니다.

    • Chaining
      충돌 발생 시, 그 버킷의 데이터들을 LinkedList형태로 연결하는 것을 말합니다.
      최악의 경우, 모든 데이터가 같은 해시값을 가져서 O(n)이 될 수 있습니다.

    • Open Addressing

    • Linear Probing
      충돌 발생 시, 바로 다음 인덱스에 데이터를 저장하는 것을 말합니다.
      만약, 다음 인덱스에서도 충돌이 발생한다면 그 다음 인덱스에 데이터를 저장합니다.

    • Quadratic Probing
      충돌 발생 시, 인덱스의 제곱만큼 이동하여 데이터를 저장합니다.

    • Double Hashing Probing
      해시된 값을 한번 더 해싱하는 방법입니다.

⚠️ **GitHub.com Fallback** ⚠️