S E P H ' S

HashSet, LinkedHashSet과 같이 해시 개념을 접목한 자료구조들에 대해서 알아보고 해시충돌과 같은 개념 또한 살펴보았다. 이번 포스트에서는 HashTable, HashMap에 대해서 알아볼 것이다. 추가적으로 해시 충돌 포스트에서 이를 해결하기 위한 여러 방법들이 있었는데 이 또한 더 자세히 알아보도록 하자. 그리고 자료구조 파트의 포스트가 매우 많기 때문에 이쯤에서 한번 [Java] 4. Collection (List, Map, Set) 포스트에서 전체적인 자료구조 흐름을 짚고 넘어오면 좋을 것 같다. HashTable, HashMap 두 자료구조 모두 공통된 특징을 갖고 있고 사용법도 유사하다. 둘 다 Map 인터페이스를 구현하고 있기 때문이다. Key, Value 구조로 데이터를 저장..

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(); 그러나 객체가 같은 주소를 가리킬 경우에는 주의해야한다. 객체가 같은..