[JAVA] LinkedHashSet

LinkedHashSet 구현 과정

• 초기 단계 (Iterable):
  newLinkedHashSet() 메서드는 초기화 시에 여러 요소가 담긴 Iterable을 인자로 받습니다. 이 Iterable는 여러 요소(예: element1, element2, ...)를 포함합니다.
• 반복 과정:
  메서드 내부에서는 전달된 Iterable을 반복하면서 각 요소를 LinkedHashSet에 추가합니다.
• LinkedHashSet:
  LinkedHashSet은 Set 인터페이스를 구현한 컬렉션으로, 요소의 중복을 허용하지 않으며 삽입 순서를 유지합니다.

만약 단일 객체를 전달하면 반복할 수 없으므로 Iterable 형식(예: 단일 객체를 포함한 리스트나 Collections.singleton())으로 감싸야 합니다.

 

List, Set, LinkedHashSet

 

List vs Set

• List
  • 순서 유지: List는 요소가 삽입된 순서를 유지합니다.
  • 중복 허용: 동일한 값의 요소가 여러 번 들어갈 수 있습니다.
  • 인덱스 접근: 인덱스를 통해 특정 위치의 요소에 접근할 수 있습니다.
• Set
  • 중복 제거: Set은 동일한 값의 요소가 중복해서 저장되지 않습니다.
  • 순서 보장 없음(일반 Set): 기본 Set은 요소의 순서를 보장하지 않습니다.
  • 빠른 검색: 중복 제거와 해시 기반 저장으로 요소의 검색 속도가 빠릅니다.

Set vs LinkedHashSet

• Set (인터페이스):
  • Set은 컬렉션 인터페이스로, 중복을 허용하지 않는다는 일반적인 특징을 가지고 있습니다.
  • 구현체에 따라 요소의 순서를 유지하지 않을 수 있습니다.
• LinkedHashSet
  • 삽입 순서 유지: LinkedHashSet은 내부적으로 연결 리스트를 사용하여 요소가 삽입된 순서를 유지합니다.
  • 중복 제거: HashSet과 같이 중복을 허용하지 않습니다.
  • 조금 더 많은 메모리: 순서를 유지하기 위한 추가적인 자료구조 때문에 일반 HashSet에 비해 약간의 오버헤드가 있습니다.

즉, 만약 순서가 중요하면서 중복을 제거하고 싶다면 LinkedHashSet이 적합하고, 순서가 중요하지 않다면 일반 HashSet을 사용할 수 있습니다. List는 중복을 허용하고 인덱스 기반 접근이 필요할 때 선택하게 됩니다.
하지만, set 은 list 처럼 index 기반의 접근을 할 수 없습니다.

 

1. List의 내부 구조와 인덱스 기반 접근

• 내부 구현 (예: ArrayList):
  ArrayList는 내부적으로 동적 배열을 사용합니다. 이 배열은 메모리 상에 연속적으로 할당되어 있어서 각 요소의 위치(인덱스)가 명확합니다.
• 인덱스 기반 접근:
  배열은 인덱스 값을 이용해 곧바로 특정 위치의 요소에 접근할 수 있습니다. 예를 들어, list.get(2)는 내부 배열의 2번 위치에 있는 값을 직접 반환할 수 있습니다. 이 과정은 O(1)의 시간 복잡도를 가집니다.
• 순서의 의미:
  배열의 연속적인 저장 덕분에 삽입된 순서가 그대로 유지되고, 이 순서가 인덱스에 직접 반영됩니다.

2. Set의 내부 구조와 인덱스 기반 접근 부재

• 내부 구현 (예: HashSet, LinkedHashSet):
  • HashSet: 주로 해시 테이블을 기반으로 구현됩니다. 요소들을 해시 값을 기준으로 저장하고 관리하여, 중복을 허용하지 않고 빠른 검색(추가, 삭제, 포함 여부 확인)을 지원합니다.
  • LinkedHashSet: HashSet의 기능에 더해 이중 연결 리스트를 추가로 사용합니다. 이 연결 리스트는 삽입 순서를 유지하지만, 인덱스와 직접 연관된 구조는 아닙니다.
• 인덱스 기반 접근의 부재:
  • 해시 테이블은 요소들을 고유의 해시값으로 관리하기 때문에, 메모리 상에 연속적으로 저장되지 않습니다. 요소들이 특정 "버킷(bucket)"에 분산되어 저장되므로, 인덱스라는 개념이 존재하지 않습니다.
  • LinkedHashSet은 삽입 순서를 유지하기 위해 요소 간의 연결 정보를 추가로 가지고 있지만, 이 연결 정보는 단순히 순서를 재현하기 위한 것으로, 배열처럼 각 요소가 연속적인 메모리 위치에 존재하지 않습니다. 따라서 특정 인덱스에 있는 요소를 곧바로 가져오는 메서드(get(index))는 제공되지 않습니다.

3. 요약

• List (ArrayList):
  • 내부구조: 연속된 배열
  • 특징: 인덱스 기반 접근이 가능, 순서 유지, 중복 허용
  • 예: list.get(index) 사용 가능
• Set (LinkedHashSet):
  • 내부구조: 해시 테이블 + 이중 연결 리스트
  • 특징: 중복 제거, 삽입 순서 유지(LinkedHashSet의 경우)
  • 단점: 인덱스라는 개념이 없으므로, 인덱스 기반 접근 메서드가 없음

즉, 두 자료구조의 차이는 내부 구현과 그 목적에 있습니다. List는 순서와 인덱스 접근이 중요한 경우에 적합하고, Set은 중복 없이 저장하고 빠른 검색이 중요한 경우에 적합합니다. LinkedHashSet은 해시 기반 검색과 함께 삽입 순서를 유지하는 기능을 제공하지만, 배열 기반 구조가 아니기 때문에 인덱스 기반 접근을 지원하지 않는 것입니다.

 

따라서 Hash 기반의 검색을 따른다.

해시 기반 검색은 각 객체의 해시코드를 계산하여, 그 결과를 이용해 객체가 저장될 위치(버킷)를 결정하는 방식입니다. 예를 들어, HashSet이나 HashMap에서는 객체의 hashCode() 메서드를 사용합니다.

1. 해시코드 계산:
   객체의 고유한 정보를 바탕으로 해시 함수를 통해 정수값(해시코드)이 생성됩니다.
2. 버킷 결정:
   생성된 해시코드를 기반으로 내부 배열에서 특정 인덱스(버킷)를 결정합니다. 이 인덱스는 보통 해시코드를 배열의 크기로 나눈 나머지 값으로 계산됩니다.
3. 빠른 검색:
   요소를 검색할 때도 같은 해시 함수를 적용해 해당 객체가 있어야 할 버킷을 바로 찾아갑니다. 버킷 내에서 동일한 해시코드를 가진 객체가 여러 개일 수 있으므로, equals() 메서드를 사용해 실제 객체를 비교합니다.
   이 과정 덕분에 전체 컬렉션을 순차적으로 검색하는 것이 아니라, 한정된 작은 영역(버킷)에서만 탐색하므로 평균적으로 매우 빠른 검색 속도를 보입니다.
4. 충돌 처리:
   서로 다른 객체가 동일한 해시코드를 갖게 되면, 동일한 버킷에 저장되는데, 이 경우 체이닝(버킷 내에 연결 리스트나 트리 구조를 사용하여 저장) 등의 방식으로 충돌을 처리합니다.

이러한 이유로 해시 기반 검색은 평균적으로 O(1)의 시간 복잡도를 갖게 되며, 대량의 데이터를 효율적으로 관리하고 검색할 수 있게 해줍니다.

 

 

 

Hash 기반

HashMap vs HashSet 차이점

 

1. 정의

• HashMap : Map Interface의 구현체로 HashTable과 유사한 자료구조로 데이터를 저장한다.
• HashSet : Set Interface의 구현체로, 내부적으로 HashMap을 사용해 데이터를 저장하기 때문에 HashTable과 유사한 자료구조로 데이터를 저장한다고 할 수 있다.

 

2. 데이터 저장 형태

• HashMap : key-value 형태로 데이터를 저장한다. 각 value들이 key에 mapping되어 있다.
• HashSet : 객체 그 자체를 저장한다. key 값으로는 삽입되는 객체 자체를, 내부 구현 코드에서 필드로 선언한 객체(dummy 객체)를 value 값으로 사용한다.

 

3. 데이터 삽입 방법

• HashMap : put() 메서드를 사용해 데이터를 삽입한다. key-value 형태의 한 쌍의 데이터를 저장하기 때문에 삽입 연산동안 단 하나의 객체가 생성된다.
• HashSet : add() 메서드를 사용해 사용해 데이터를 삽입한다. 객체 자체를 저장하고, 내부적으로 HashMap을 사용하기 때문에 삽입되는 객체(key 값)와 dummy 객체(value  값), 총 2개의 객체가 삽입 연산 동안 생성된다.

 

4. 중복 허용 여부

• HashMap : 중복 key는 허용하지 않지만, 중복 value는 허용한다.
  • ex) {'a': 1, 'b': 1, 'c': 2} : 가능 / {'a': 1, 'b': 1, 'a': 2} : 불가능

• HashSet : 객체 자체를 저장하는 형태이기 때문에 데이터 중복을 허용하지 않는다.
  • ex) {'a', 'b', 'c'}

 

5. null 허용 여부

• HashMap : 중복 key 값을 허용하지 않기 때문에 단 하나의 null 값을 key 값으로 가질 수 있고, 중복이 허용된 value의 경우 여러 null 값을 가질 수 있다.
• HashSet : 단 하나의 null 값을 가질 수 있다.

 

6. 성능(속도)

• HashMap : HashSet보다 빠르다.
• HashSet : 오직 객체만 저장 가능해 HashMap보다 느리다.