이전글 https://yonghwankim-dev.tistory.com/172 비선형 데이터구조, 해시(Hash) #2 해시함수에서 문자열 이전글 https://yonghwankim-dev.tistory.com/171 비선형 데이터구조, 해시(Hash) #1 해시소개 개요 대표적인 선형 데이터 구조인 연결리스트(LinkedList)는 삽입과 삭제와 같은 연산에서 낮은 비용으로 수행할 yonghwankim-dev.tistory.com 개요 이전글에서는 해시 함수에 문자열을 넣어 문자열에 따른 해시함수 값을 계산하는 해시함수를 구현하였습니다. 그런데 해시 함수에 키를 넣어 해시함수값을 구하여도 동일한 해시함수 값이 나올 수 있습니다. 따라서 이번글에서는 해시 충돌을 방지하기 위해서 해시 크기를 최적화하는 방..

이전글 https://yonghwankim-dev.tistory.com/171 비선형 데이터구조, 해시(Hash) #1 해시소개 개요 대표적인 선형 데이터 구조인 연결리스트(LinkedList)는 삽입과 삭제와 같은 연산에서 낮은 비용으로 수행할 수 있습니다. 그러나 대표적인 단점인 어떤 값을 찾기 위해서는 맨 앞의 노드에서 yonghwankim-dev.tistory.com 개요 이전글에서는 해시 함수에 문자열을 넣으면 필요없는 문자열을 제거한 후 숫자 부분만 추출하고 재가공하여 인덱스를 계산하였습니다. 이번글에서는 key가 문자열일때 해시함수값을 계산하는 방법에 대해서 소개하겠습니다. 1. 해시 함수에서 문자열 예를 들어 다음과 같은 코드가 있습니다. String s = "my name is Rob";..

개요 대표적인 선형 데이터 구조인 연결리스트(LinkedList)는 삽입과 삭제와 같은 연산에서 낮은 비용으로 수행할 수 있습니다. 그러나 대표적인 단점인 어떤 값을 찾기 위해서는 맨 앞의 노드에서부터 탐색하기 때문에 탐색 속도에서 O(n)의 시간이 소요됩니다. 그렇다고 배열 기반의 리스트를 사용하기에는 삽입과 삭제 연산에서 많은 비용이 발생합니다. 이 문제를 해결하기 위해서 해시를 소개하겠습니다. 해시소개 해시함수 작성시 고려사항 해시충돌이란 무엇인가? 1. 해시 소개 해시는 특정한 키(key)값을 해시 함수(HashFunction)의 수식에 대입시켜 계산 후 나온 결과를 주소로 사용하여 값(Value)에 접근하는 방법입니다. 예를 들어 학생의 아이디(Student ID)와 점수(Grade)가 아래와 ..

1. Priority Queue 데이터 구조란 무엇인가? Priority Queue는 객체들이 우선순위에 기반하여 처리될때 사용됩니다. Priority Queue의 처리순서는 일반적으로 Queue 데이터 구조인 FIFO(First-in-First-Out) 알고리즘을 따릅니다. 그러나 때때로 큐의 요소들이 우선순위에 따라 빠르게 처리해야 되는 경우가 존재합니다. 이럴때 Priority Queue를 통해서 순서에 상관없이 처리가 가능합니다. Priority Queue의 데이터 구조는 힙(Heap) 데이터 구조에 기반합니다. 우선순위 큐의 정렬은 기본적으로 오름차순이지만 객체 생성시 Comparator 인터페이스를 통해서 정렬기준 및 순서를 정할 수 있습니다. 아래 Priority Queue 예제에서 아스키 ..

1. 이진 힙(Binary Heap) 데이터구조란 무엇인가? 이진 힙은 아래와 같은 특성을 가지고 있는 이진 트리입니다. 이진 힙의 데이터 구조는 완전 이진 트리 기반 완전 이진 트리란 마지막 레벨을 제외하고 모든 레벨이 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 왼쪽에 있는 트리를 의미합니다. 이진 힙 구성 최소 힙(MinHeap) : 부모 노드가 자식 노드보다 값이 작음, 루트 노드의 경우 모든 노드들 중 가장 작은 값이 됨 최대 힙(MaxHeap) : 부모 노드가 자식 노드보다 값이 금, 루트 노드의 경우 모든 노드들 중 가장 큰 값이 됨 즉, 정리하면 이진 힙이란 완전 이진 트리이면서 최소 힙 또는 최대 힙의 규칙으로 구성된 트리를 의미합니다. 최소 힙(Min Heap) 예제 위의 그림..

1. TreeSet이란 무엇인가? TreeSet은 데이터를 저장하기 위해 Java Tree 데이터 구조 기반에 SortedSet 인터페이스의 구현 중 하나입니다. 명시적인 comparator 객체가 제공 여부에 관계없이 오름차순 정렬을 유지합니다. TreeSet 객체 생성시 생성자에서 Comparator 객체를 사용하여 정렬이 가능합니다. TreeSet은 AbstractSet 클래스를 상속하여 NavigableSet 인터페이스를 구현합니다. 위의 그림과 같이 NavigableSet 인터페이스는 SortedSet 인터페이스로부터 상속받습니다. 일반적인 Set은 삽입 순서를 유지하지 않기 때문에 NavigableSet 인터페이스는 Set 인터페이스를 통해서 안내하기 위해서 구현을 제공합니다. Navigabl..