[Data Structure] Array, List, Stack, Queue, HashTable

CS 공부 5일차 :) 오늘은 자료구조에서 Array와 List, Stack과 Queue, HashTable에 대해 정리해보았습니다.

Array

• 정해진 크기에 배열에 데이터들을 하나씩 넣는 구조입니다. 메모리에 연속적인 공간이 할당되고 random access가 가능하여 검색이 빠르지만 삽입이나 삭제가 크기에서 벗어나게 할 수 는 없습니다.

List

• LinkedList : 크기가 정해져 있지 않고 데이터가 하나씩 연결되어 늘어가면 LinkedList의 크기도 늘어납니다. 중간에 요소를 삽입하면 양 옆의 링크를 끊고 삽입한 요소와 연결해줍니다. 메모리에 하나씩 흩어져서 저장됩니다.

• ArrayList : LinkedList와 유사하지만 중간에 요소를 삽입하면 그 요소를 포함한 새로운 객체를 만들어주고 뒤 요소들은 뒤로 한칸씩 밀리는 차이점이 있습니다.

• List vs Map : Map은 Key와 Value 값으로 구성되어 있어서 검색이 빠르고 List는 데이터 저장 속도가 빠릅니다.

• Vectorvs ArrayList : Vector와 ArrayList는 기능은 동일하게 하지만 원래 있는 Vector 구조를 java.util이 구현한 것이며, ArrayList의 사용이 더 권장됩니다.

Stack & Queue

• Stack vs Queue : 둘다 선형자료구조의 일종으로 Stack은 LIFO이고 Queue는 FIFO입니다.

• Priority Queue : Java에서 Queue는 Interface로서 Queue를 구현하여 Priority Queue를 사용할 수 있습니다. array나 LinkedList, Heap로도 Priority Queue를 구현할 수 있습니다.

HashTable

• Hash Function: key값 전체를 참고하여 최대한 collision이 적도록 함수를 정합니다. hash function을 통해 만들어진 적은 범위의 값을 가지고 index로 사용합니다.

• Resolve Collision

  • Open Addressing : 해시 테이블의 빈공간에 위치시키는 방법입니다.
    • Linear Probing : 순차적으로 돌면서 빈공간을 찾는 방법
    • Quadratic Probing : +1, +4, +9로 돌면서 빈공간을 찾는 방법
    • Double Hashing : 재해싱이라고도 하며 해쉬 함수를 두번 적용해서 빈공간을 찾는 방법
  • Separate Chaining : 중복되는 값들을 LinkedList로 만드는 방법입니다. JAVA 8 부터는 LinkedList의 길이가 8이상이면 tree형태로 바꾸어 저장하고 6이하로 내려가면 다시 LinkedList의 형태로 저장합니다.
  • Resize : 데이터가 75%정도 차면 2배로 table의 크기를 늘립니다.

• HashSet vs HashMap : HashSet은 hashcode함수를 사용하여 객체를 해쉬값으로 변형해 중복된 값이 있나 확인하고 넣습니다. HashMap은 key-value의 형태로 key를 hashfunction을 돌려서 삽입합니다. HashMap이 더 빠릅니다.

• HashMap vs HashTable : HashTable이 더 먼저 생기고 HashMap이 더 나중에 생겼는데 HashMap은 동기화가 지원되지 않아서 멀티 스레드 환경에서는 HashTable이나 ConcurrentHashMap을 사용하는 것이 낫습니다. 또한 HashMap은 null값을 허용하고 HashTable은 허용하지 않습니다.

• Map vs HashMap : Map은 레드블랙트리로 구성되어 있어서 O(logN)만큼 시간이 걸리고 HashMap은 O(1)만큼(최악의 경우 O(N)) 시간이 걸린다.