[데이터 구조] HashSet 원리 및 학습 총화 실현

지난 블 로그 (HashMap 원리 와 학습 총 결 실현) 에서 HashMap 의 실현 과정 을 상세 하 게 정 리 했 는데 HashSet 에 있어 HashMap 을 바탕 으로 이 루어 진 것 이 고 밑바닥 은 HashMap 으로 요 소 를 보존 했다.그래서 HashMap 에 익숙 하 다 면 HashSet 의 원 리 를 잘 이해 할 수 있 을 것 입 니 다!
1. HsahSet 개요
HashSet 은 Set 인 터 페 이 스 를 실현 하고 해시 표 (실제 HashMap 인 스 턴 스) 가 지원 합 니 다.set 의 교체 순 서 를 보장 하지 않 습 니 다.특히 이 순서 가 영원히 변 하지 않 는 다 는 것 은 보장 되 지 않 는 다.null 요 소 를 사용 할 수 있 습 니 다.

public class HashSet<E>  
    extends AbstractSet<E>  
    implements Set<E>, Cloneable, java.io.Serializable  

HashSet 은 AbstractSet 클래스 를 계승 하여 Set, Cloneable, Serializable 인 터 페 이 스 를 실현 합 니 다.그 중에서 AbstractSet 은 Set 인터페이스의 골간 실현 을 제공 하여 이 인 터 페 이 스 를 실현 하 는 데 필요 한 작업 을 최대한 줄 였 다.Set 인 터 페 이 스 는 중복 요 소 를 포함 하지 않 는 Collection 으로 내부 순 서 를 유지 하기 때문에 무 작위 접근 은 의미 가 없습니다.기본 속성:

//     HashMap   HashSet     。
    private transient HashMap map;

    //        Object    HashMap value，       static final。
    private static final Object PRESENT = new Object();

구조 함수: 구조 함수 에서 알 수 있 듯 이 HashSet 의 모든 구 조 는 새로운 HashMap 을 구성 하 는 것 이다. 그 중에서 마지막 구조 함 수 는 패키지 접근 권한 을 대외 적 으로 공개 하지 않 고 LinkedHashSet 을 사용 할 때 만 작용 한다.
2. HsahSet 실현
HashSet 은 HashMap 을 바탕 으로 하기 때문에 HashSet 에 대해 그 방법의 실현 과정 은 매우 간단 하 다.1. iterator () iterator () 방법 은 이 set 의 요 소 를 교체 하 는 교체 기 를 되 돌려 줍 니 다.원 소 를 되 돌려 주 는 순 서 는 특정한 것 이 아 닙 니 다.바 텀 은 실제 바 텀 HashMap 의 keyset 을 호출 하여 모든 key 를 되 돌려 줍 니 다.HashSet 의 요 소 를 볼 수 있 습 니 다. 밑 에 있 는 HashMap 의 key 에 만 저장 되 어 있 습 니 다. value 는 static final 의 Object 대상 표 지 를 사용 합 니 다.

public Iterator iterator() {
        return map.keySet().iterator();
    }

2. size () 는 이 set 의 요소 의 수량 (set 의 용량) 을 되 돌려 줍 니 다.바 텀 에서 HashMap 의 size () 방법 을 실제 호출 하여 Entry 의 수량 을 되 돌려 주면 이 Set 의 요소 의 갯 수, 즉 HashMap 용기 의 크기 를 얻 을 수 있 습 니 다.

public int size() {
        return map.size();
    }

3. isEmpty () isEmpty () 는 HashSet () 집합 이 비어 있 는 지 판단 합 니 다. 이 set 에 요소 가 포함 되 어 있 지 않 으 면 true 로 돌아 갑 니 다.하 쉬 맵 의 isEmpty () 를 실제 호출 하여 이 하 쉬 세트 가 비어 있 는 지 판단 합 니 다.

public boolean isEmpty() {
        return map.isEmpty();
    }

4. contains (Object o) contains () 는 특정한 요소 가 HashSet () 에 존재 하 는 지 판단 하고 true 로 돌아 가 는 것 이 있 으 며, 그렇지 않 으 면 false 로 돌아 갑 니 다.더 정확히 말하자면 이러한 관 계 를 만족 시 켜 야 true 로 돌아 갈 수 있 습 니 다. (o = null? e = null: o. equals (e).하위 호출 contains Key 는 HashMap 의 key 값 이 비어 있 는 지 판단 합 니 다.

public boolean contains(Object o) {
        return map.containsKey(o);
    }

5. add () add () 이 set 에 지정 한 요소 가 포함 되 어 있 지 않 으 면 지정 한 요 소 를 추가 합 니 다.이 set 에 만족 (e = = null? e2 = = null: e. equals (e2) 의 e2 가 포함 되 어 있 지 않 으 면 e2 를 set 에 추가 하고 그렇지 않 으 면 false 를 추가 하지 않 고 되 돌려 줍 니 다.아래 에 HashMap 의 put 방법 을 사용 하여 key = e, value = PRESENT 를 key - value 키 쌍 으로 구축 합 니 다. 이 e 가 HashMap 의 key 에 존재 하면 value 는 원래 value 를 덮어 씁 니 다. 그러나 key 는 변 하지 않 습 니 다. 따라서 이미 존재 하 는 e 요 소 를 HashSet 에 추가 하면 새로 추 가 된 요 소 는 HashMap 에 저장 되 지 않 습 니 다.그래서 HashSet 에서 요소 가 중복 되 지 않 는 특성 을 만족 시 켰 습 니 다.

public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

6. remove () remove () 지정 한 요소 가 이 set 에 존재 하면 제거 합 니 다.바 텀 에 서 는 HashMap 의 reove 방법 으로 지정 한 Entry 를 삭제 합 니 다.

public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

7. clear () clear () 는 이 set 에서 모든 요 소 를 제거 합 니 다.하 쉬 맵 의 clear 방법 을 사용 하여 모든 Entry 를 제거 합 니 다.

public void clear() {
        map.clear();
    }

8. clone () 바 텀 에서 HashMap 의 clone () 방법 을 실제 호출 하여 HashMap 의 얕 은 표 사본 을 가 져 옵 니 다. 이 요소 자 체 를 복사 하지 않 았 습 니 다.

public Object clone() {
        try {
            HashSet newSet = (HashSet) super.clone();
            newSet.map = (HashMap) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }