S E P H ' S

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..

Set Interface Set은 말그대로 집합이다. 기본적으로 Set 혹은 Set 계열을 구현하는 클래스들은 다음과 같은 공통점이 있다. 중복 요소(원소)를 허용하지 않는다. 저장 순서를 유지하지 않는다. (LinkedHashSet 만 예외) 가장 중요한 특징은 '중복 요소를 허용하지 않는다'는 점이다. Set의 종류 Set은 크게 HashSet, LinkedHashSet, TreeSet으로 나뉜다. HashSet 가장 기본적인 Set 컬렉션의 클래스이다. 입력 순서를 보장하지 않고 순서도 보장되지 않는다. 가장 쉽게 이해할 수 있는 예시로는 게임에서 닉네임 중복확인을 할때이다. 이는 데이터가 정렬될 필요도 없을뿐더러 빠르게 중복되는 값인지만 찾으면 되므로 유용한 방법이 될 수 있다. hash에 의해 ..