S E P H ' S

HashSet, LinkedHashSet 다음에 다루려던 것이 TreeSet이었는데 TreeSet이 내부적으로 Red-Black Tree로 구현되어있다. 그런데 또 Red-Black Tree를 이해하려면 BST(Binary Search Tree)도 이해해야 하고 결과적으로 TreeSet을 알아보기 전에 Tree 에 대한 개념과 이해를 선행해야겠다는 생각이 들었다. 그래서 트리에 대해 전반적으로 알아보고 차례대로 Tree 종류들을 알아보고 TreeSet을 다뤄보도록 할 것이다. Tree 트리는 비선형구조이다. 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화 시키고자 할 때 사용되는 자료구조이다. 데이터의 요소들이 단순한 나열이 아닌 부모 - 자식 관계의 계층적 구조로 표현된다. 아래 이미지..

Linked Hash Set HashSet 자체는 순서를 보장하지 않는다. 이번에는 입력 순서를 보장하는 LinkedHashSet을 알아볼 것이다. 이전에 구현했던 LinkedList와 HashSet의 특성을 같이 갖는 자료구조이다. Doubly LinkedList HashSet HashSet을 구현할때, 우리는 데이터를 해싱한 값을 Node[] table 배열의 인덱스(index)로 활용하여 해당 인덱스에 데이터를 저장했다. 이는 데이터를 빠르게 탐색할 수 있는 장점을 갖게 하지만 데이터가 해싱된 값에 따라 저장되는 위치가 달라지므로 순서가 보장되지는 않는다. 이러한 단점을 보완하기 위해 LinkedList를 구현할 때, 노드 클래스에는 이전 노드를 가리키는 변수인 prev와 다음 노드를 가리키는 ne..

Set 자료구조들을 포스팅 하다가 중요한 개념인 해시 충돌에 대해서 짚고 넘어가야 할것 같아 따로 포스팅을 하게 됐다. 해시 테이블에서만 뿐만 아니라 해시 기법 자체가 여러 곳에서 사용되기 때문에 해시 충돌에 대해서는 항상 염두에 두고 있어야 한다고 생각을 했기 때문이다. 해시 충돌 (지난 포스트에서도 다룬 내용임) 자바에서는 hasCode() 라는 간편한 함수의 존재로 해시함수를 굳이 구현할 필요가 없다. hashCode()를 통해 객체의 주소값을 이용하여 해시 알고리즘에 의해 생성된 고유의 정수값을 반환할 수 있다. 즉, 객체가 같은 메모리 주소를 가리키고 있다면 같은 정수값을 얻을 수 있다. int a = X.hashCode(); 그러나 객체가 같은 주소를 가리킬 경우에는 주의해야한다. 객체가 같은..

Hash HashSet에 대해 다루기 전에 Hash에 대한 개념을 먼저 다뤄보도록 하자. Hash는 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환하는 것이다. 그리고 위와 같은 기능을 하는 함수를 해시 함수(Hash Function)이라고 한다. abcd 라는 문자열이 있다면 이를 특정 길이 (ex 256bit, 512bit 등) 의 데이터로 변환시키는 것이다. 만약 특정 길이를 32bit로 고정된다는 가정하에 아래 이미지를 보자. 32bit는 2진수일때 기준이므로, 16진수로 보자면 4bit 당 한 묶음이기 때문에 16진수로 표현하면 8개의 문자를 얻게된다. 즉 해시함수를 돌리기 전 문자열의 길이가 얼마이든지 일정한 길이를 얻는다는 것이다. 실제로 대표적인 해시함수의 SHA계열의 SHA-51..