10. HashSet 소스 코드 분석

1. 클래스 주석
  • HashSet 의 밑바닥 은 HashMap 을 바탕 으로 하기 때문에 교체 할 때 삽입 순서에 따라 교체 할 수 없다.
  • HashSet 의 add, remove, contanins, size 등 방법의 시간 소모 성능 은 데이터 양 이 증가 함 에 따라 증가 하지 않 습 니 다. 이 유 는 HashMap 바 텀 의 배열 데이터 구조 와 관련 이 있 습 니 다. 데이터 양 이 아무리 많 더 라 도 hash 충돌 을 고려 하지 않 은 상황 에서 시간 복잡 도 는 O (1) 입 니 다.
  • HashSet 은 라인 이 안전 하지 않 습 니 다. 안전 이 필요 하 다 면 스스로 자 물 쇠 를 채 우거 나 Collections 의 synchronizedSet 방법 을 사용 하 십시오.
  • 교체 과정 에서 데이터 구조 가 바 뀌 면 빠 른 속도 로 실패 하고 Concurrent ModificationException 이상 을 던 집 니 다.

  • 2. 실현 방식 은 클래스 주석 에서 볼 수 있 듯 이 HashSet 의 실현 은 HashMap 을 바탕 으로 하 는 것 이 고 자바 에서 기초 류 를 바탕 으로 혁신 적 으로 실현 하려 면 두 가지 방법 이 있다.하 나 는 기초 류 를 계승 하고 기초 류 를 복사 하 는 방법 이다. 예 를 들 어 HashMap 을 계승 하고 add 방법 을 복사 하 는 것 이다.또 다른 방법 은 기초 류 를 조합 하여 기초 류 를 호출 하 는 방법 을 통 해 기초 류 의 능력 을 재 활용 하 는 것 이다.HashSet 은 후 자 를 사용 하고 조합 HashMap 을 통 해 제공 하 는 기능 을 사용 하 는데 그 장점 은 다음 과 같다.우선, 상속 은 부자 류 가 같은 사물 임 을 나타 내 고 Set 와 Map 은 두 가지 사물 을 표현 하기 때문에 계승 이 타당 하지 않 고 자바 문법 제한 으로 자 류 는 한 부모 류 만 계승 할 수 있 고 후속 적 으로 확장 하기 어렵다.그 다음으로 조합 이 더욱 유연 하고 기 존의 기초 류 를 임의로 조합 할 수 있 으 며 기초 류 방법 을 바탕 으로 확장, 편성 등 을 할 수 있 으 며 방법 명명 이 상대 적 으로 유연 하여 기초 류 의 방법 명칭 과 일치 하지 않 아 도 된다.구체 적 으로 소스 코드 를 실현 하 는 것 은 다음 과 같다.
    public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
         
    	// HashMap    ,key Hashset key,value    PRESENT
     	private transient HashMap<E,Object> map;
      	
      	//HashMap  value
        private static final Object PRESENT = new Object();
    }
    

    소스 코드 분석
  • HashSet 을 사용 할 때, 예 를 들 어 add 방법 은 하나의 입 참 만 있 지만, 조 합 된 Map 의 add 방법 은 key 와 value 두 개의 입 참 이 있 습 니 다. 이에 대응 하 는 key 는 add 의 입 참 입 니 다. value 는 두 번 째 줄 코드 중의 PRESENT 입 니 다. 이곳 은 매우 교묘 하 게 설계 되 었 습 니 다. Map 의 Value 를 기본 값 PRESENT 로 대체 합 니 다.
  • HashSet 이 공유 되면 여러 스 레 드 가 접근 할 때 스 레 드 안전 문제 가 발생 합 니 다. 후속 적 인 모든 작업 에 잠 금 이 추가 되 지 않 았 기 때 문 입 니 다.

  • 3. HashSet 초기 화 는 간단 합 니 다. new 를 직접 사용 하면 됩 니 다. 원본 집합 데이터 가 초기 화 된 경우 HashMap 의 초기 용량 을 계산 합 니 다. 소스 코드 는 다음 과 같 습 니 다.
    public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
         
    	// HashMap       
    	public HashSet(Collection<? extends E> c) {
         
        	map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        	addAll(c);
    	}
    	
    	public boolean add(E e) {
         
        //    HashMap put  ,           
        	return map.put(e, PRESENT)==null;
    	}
    }
    

    소스 코드 분석
  • Math. max (int) (c. size () /.75f) + 1, 16) 는 바로 HashMap 의 용량 을 계산 한 것 이다. 중국어 로 번역 하면 괄호 에서 두 수의 최대 치 (기대 치 / 0.75 + 1, 기본 값 16) 를 얻 는 것 이다. 계산 에서 알 수 있 듯 이 HashSet 의 실현 자 는 HashMap 의 밑바닥 실현 에 대해 매우 명확 하 다. 주로 두 가지 측면 에 나타난다. 16 과 크기 를 비교 한 다 는 뜻 이다.주어진 HashMap 의 초기 용량 이 16 보다 적 으 면 HashMap 의 기본 16 으로 초기 화하 면 되 고 16 보다 크 면 주어진 값 으로 초기 화 됩 니 다.HashMap 확장 한도 값 의 계산 공식 은 Map 의 용량 0.75f 로 밸브 값 에 도달 하면 확장 된다. 여 기 는 (int) (c. size () /.75f) + 1 로 초기 화 된 값 을 표시 하면 기대 하 는 크기 가 확 장 된 밸브 값 보다 1 크 고 확장 되 지 않 으 며 HashMap 확장 공식 에 부합된다.
  • HashSet 의 다른 방법 은 상대 적 으로 간단 하 다. 바로 Map 의 api 를 포장 한 것 이다. 예 를 들 어 상기 add 방법 이다.
  • 좋은 웹페이지 즐겨찾기