자료구조
자료구조란 데이터를 효율적으로 저장하고 관리하는 방식
Create, Read, Update, Delete가 되어야 한다 (CRUD)
이번 글에선 자바의 배열과 Collections 자료구조에 대해서 간단하게 정리해보았다.
배열(Array)
메모리에 연속적인 위치에 차례대로 저장된다.
크기 고정(선언시에 지정한 크기 변하지 않는다.)
int[] intArr = {1,2,3,4}
//임마는 크기가 4개로 고정Collections Framework
자바는 collections라는 라이브러리를 통해 다양한 자료구조를 제공한다.
java.util패키지에 포함되어 있음.
배열리스트(ArrayList<E>)
배열과 다르게 크기가 동적이다.
일정크기의 배열을 만들었다가 일정 수준 해당 배열이 차면 내부적으로 크기를 늘린다.
자바의 ArraryList는 길이가 자동으로 확장되지만, 자동으로 축소되진 않는다.
인덱스 기반 접근이 빠름 - 배열의 크기 조절, 중간에 요소 삽입/삭제 느림
⇒ 줄이고 싶으면 trimToSize()
ArrayList<String> arrList = new ArrayList<>();
arrList.add("Hello");
arrList.add("World"); //값 추가
arrList.get(1); //1번 인덱스 값 가져옴
arrList.remove(0) //0번 인덱스 값 삭제
연결리스트(LinkedList<E>)
내부적으로 노드를 사용하여 값을 연결한다. (연속적 위치 ❌)
요소의 삽입과 삭제가 쉽다.
자바의 연결리스트는 이중연결리스트로 구현되어 있다.
⇒ 각 노드가 자기의 앞, 뒤의 노드를 알고 있음
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("Hello");
linkedList.add("World");
linkedList.add("!");
linkedList.removeFirst();
linkedList.remove(1);스택(Stack<E>)
LIFO(Last In, First Out) 구조를 가진다
⇒ 마지막에 추가된 데이터가 먼저 나온다. (ex. 쌓여올려진 접시들을 생각해보자)
인덱스로 접근하지 않고 push, pop을 이용하여 데이터를 추가, 삭제한다.
Stack<Integer> intStack = new Stack<>();
for(int i = 1; i <= 5; i++) {
intStack.push(i); //1,2,3,4,5
}
intStack.pop(); //1,2,3,4
intStack.pop(); //1,2,3큐(Queue)
FIFO(First In, First Out) 구조
⇒ 추가된 순서대로 데이터가 나온다. (줄을 선 모습을 생각해보자)
스택과 비슷하게 인덱스로 접근하지 않고 add와 poll로 데이터를 추가, 삭제한다.
💡 Queue는 인터페이스이므로 LinkedList 또는 PriorityQueue로 객체 생성해야 한다.
Queue<Integer> q = new LinkedList<>();
for(int i = 1; i <= 5; i++){
q.add(i); // 1,2,3,4,5
}
q.poll(); // 2,3,4,5
q.poll(); // 3,4,5
System.out.println(q.peek()); //맨 앞 값 반환(제거X) 3
System.out.println(q); // 3,4,5덱(Deque<E>)
Deque(Double Ended Queue)는 스택과 큐를 합쳤다고 생각하면 편하다.
⇒ 양쪽(앞/뒤)에서 삽입과 삭제가 모두 가능하다.
💡 Deque는 인터페이스이므로 LinkedList 또는 ArrayDeque로 객체 생성해야 한다.
Deque<Integer> dq = new LinkedList<>();
dq.addFirst(10); //10
dq.addLast(20); //10,20
dq.addFirst(30); //30,10,20
dq.pollLast(); //30, 10
dq.pollFirst(); // 10해쉬맵(HashMap<K, V>)
키-값(Key, Value)쌍을 저장하는 자료구조
내부적으로 배열과 연결 리스트를 조합하여 구현된다.
키가 해슁되어 저장되기 때문에 검색이 빠르다.
💡해쉬(Hash)란?
본인은 해쉬를 정보보안으로 처음 알았다. 특히 포렌식할때 중요한 개념으로 배웠는데 어떠한 파일이나 자료들의 무결성을 증명하는 수단으로 쓰였다. 왜냐? 이 해시라는 것은 원칙적으로는 유일성을 보장하기 때문이다.
⇒ 한마디로 해싱이란 어떠한 데이터를 해쉬알고리즘을 통해서 그 데이터으로만 만들 수 있는 값을 만드는 것이다.
위 말대로면 아주 완벽해 보이지만 이 또한 인간이 만든것이므로 간혹 다른 데이터가 같은 해쉬값을 만들어 낼 수 도 있다. 이를 해쉬충돌이라고(Hash Collsion)이라고 한다.
이러한 문제가 해시맵에서 일어났을 때는 어떻게 대처를 하는지 밑에서 알아보자
- 키를 해싱하여 해시 값을 만든다.
- 이 해쉬값을 버킷이라는 배열의 길이로 나머지연산(%)하여 나온 값이 인덱스가 되어 해당 위치에 저장된다.(버킷은 고정길이 배열(
Node<K,V>[])가 들어있다. 2차원 배열과 비슷?) - 여기서 만약 해쉬충돌이 일어난다면, 같은 버킷 내의 연결리스트로 값을 추가한다.(같은 키값 다른 벨류)
- JAVA8부터는 연결리스트가 많아지면(해시충돌이 많이 일어나면) 트리(Red-Black Tree)로 변환되어 성능 최적화
배열 (Bucket) 구조:
[0] → null
[1] → null
[2] → ("apple", 100) → ("grape", 300) ⬅ (해시 충돌 발생, 연결 리스트로 저장)
[3] → null
[4] → ("banana", 200)HashMap<String, Integer> map = new HashMap<>();
// 데이터 추가 (put)
map.put("Apple", 1000);
map.put("Banana", 2000);
map.put("Cherry", 3000);
// 데이터 가져오기 (get)
System.out.println(map.get("Apple"));
// 키 존재 여부 확인 (containsKey)
System.out.println(map.containsKey("Banana"));
// 값 존재 여부 확인 (containsValue)
System.out.println(map.containsValue(400));
// 크기 확인 (size)
System.out.println(map.size());
// 데이터 삭제 (remove)
map.remove("Cherry");
// 전체 출력 (entrySet)
for (var entry : map.entrySet()) {
System.out.println(entry.getKey() + " -> " + entry.getValue());
}