자료구조

지난번 HashSet과 해쉬충돌에 대해 알아보면서 해쉬충돌이 발생한 경우 HashSet(=HashMap)은 Separate Chaining 방식을 사용한다고 언급했었다. 특정한 임계치를 넘기 전까진 링크드리스트 구조로 노드를 연결하다가 임계치를 넘으면 자료구조를 Red-Black트리로 변경한다. Red-Black트리가 무엇인지, 자바는 왜 Red-Black트리를 선택했는지 생각해보자. 왜 트리 구조로 변경하는가? 하필이면 왜 레드-블랙 트리로?HashSet의 검색 성능[O(1)]을 보장하기 위해서는 노드를 링크드리스트로 연결하다간 O(N)의 시간 복잡도를 갖을 수 있다. 물론 데이터가 적다면 무시할 수 있겠지만 데이터가 많아진다면 O(N)은 절대 무시할 수가 없다. 링크드 리스트 대신 이진 탐색 트리를 ..

해쉬충돌은 해쉬알고리즘을 사용하는 자료구조에겐 성능상 치명적이다. 해쉬알고리즘을 사용하는 것의 목적은 자료를 정수로 표현해 인덱스를 구하기 위함인데, 해쉬충돌이 발생하면 인덱스가 충돌되기 때문에 O(1)의 시간복잡도를 유지할 수 없다. 정말 최최최악의 경우엔 O(N)의 시간복잡도를 갖게 된다. 해쉬 충돌을 해결하는 여러가지 방법을 알아보려한다. Open Addressing개방주소법이라고 불리는 이 방식은 해쉬 충돌이 발생하면 비어있는 공간을 찾아가는 알고리즘이다. Open Addressing는 크게 세 가지로 나뉜다. 1. Linear Probing Linear Probing 방식은 해쉬 충돌이 발생하면 비어있는 버킷을 발견할 때 까지 선형적으로 버킷을 검색한다. 이는 H(key,i) = (H_qp(ke..

Set은 List와 달리 중복을 허용하지 않고 순서를 보장하지 않으며 수학에서 집합과 같은 개념을 구현한 자료구조다. 특히 List의 검색은 O(N)인 반면 Set의 검색은 O(1)의 복잡도를 갖는다. Set의 검색이 항상 O(1)을 보장하진 않지만 전반적으로 굉장히 빠르다. 어떻게 O(1)이 될 수 있는지 그리고 항상 O(1)을 보장할 수 없는 이유를 알아보자. O(1)의 시간복잡도O(1)의 시간 복잡도를 갖는 자료구조로 가장 유명한 것은 배열이다. 배열을 사용하면 인덱스를 통해 한 번에 자료에 접근이 가능하기 때문이다. 한 번이라는 의미는 연산이 한 번 일어난다는 의미다. 배열에 대한 이야기는 아래 포스팅에 적어 두었다. ArrayList의 배열 리사이징ArrayList는 내부적으로 가변크기 배열을..

LinkedList링크드리스트 자료구조 역시 이름에서 특징이 잘 드러난다. 링크드리스트는 노드라고 불리는 객체가 서로서로 연결된 리스트다. 아래는 자바의 링크드리스트의 노드 클래스다. private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; }} 내부 클래스로 되어있고 하나의 노드엔 다음 노드와 이전 노드를 가리킬 수 있는 필드가 선언돼있다.  이렇게 노드는 각자가 서로를 참조하는 형태로 연결돼 앞뒤로 이동이 가능하다. 이런..

ArrayList는 내부적으로 가변크기 배열을 이용한다. 하지만 배열 크기 자체가 동적으로 설정되는 것은 아니라 내부에서 새로운 크기의 배열을 생성하고 복사한다. 먼저 배열을 알아보자배열은 자료구조에서 가장 기초적이면서도 핵심적인 위치에 있다. 인덱스를 통한 배열 접근은 O(1)로 한 번의 연산으로 데이터에 접근이 가능하다.int[] arr = new arr[5];arr[0] = 1;System.print.out(arr[0]);  배열은 어떻게 시간 복잡도가 O(1)이 될 수 있을까?배열은 메모리에 연속적으로 할당된다.  연속적인 메모리 할당이 주는 이점은 배열의 시작주소와 자료형을 알 수 있다면 (시작주소 + 자료형 크기 * 인덱스) 라는 한 번의 연산으로 데이터의 위치를 알아 낼 수 있다. 자료형은 ..