자바 에서 set 집합 은 어떻게 요 소 를 추가 하여 중복 되 지 않도록 보장 합 니까?

자바 에서 set 집합 은 어떻게 요 소 를 추가 하여 중복 되 지 않도록 보장 합 니까?
Set 집합 은 무질서 하고 중복 할 수 없 는 집합 이다.오늘 은 왜 중복 이 안 되 는 지 살 펴 보 겠 습 니 다.
Set 는 인터페이스 입 니 다.가장 자주 사용 하 는 실현 류 는 바로 HashSet 입 니 다.오늘 우 리 는 HashSet 를 예 로 들 겠 습 니 다.
HashSet 클래스 를 간단하게 소개 해 드릴 게 요.
HashSet 류 는 Set 인 터 페 이 스 를 실 현 했 는데 그 밑바닥 은 사실 HashMap 을 포장 하여 실현 한 것 이다.HashSet 은 집합 에 있 는 요 소 를 HashCode 알고리즘 으로 액세스 하기 때문에 비교적 좋 은 읽 기와 찾기 성능 을 가지 고 있 습 니 다.
먼저 HashSet 의 몇 가지 구조 방법 을 살 펴 보 자.

//              HashMap
    public HashSet() {
        //   HashMap       ，  map
        map = new HashMap();
    }

    //         
    public HashSet(Collection extends E> c) {
        //   map。
        map = new HashMap(Math.max((int) (c.size()/.75f) + 1, 16));
        //    (c)         HashSet 
        addAll(c);
    }

    //   HashSet              
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap(initialCapacity, loadFactor);
    }

    //   HashSet         
    public HashSet(int initialCapacity) {
        map = new HashMap(initialCapacity);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap(initialCapacity, loadFactor);
    }

HashSet 의 성명 을 살 펴 보 겠 습 니 다.

private transient HashMap map;
 //     Map            
private static final Object PRESENT = new Object();

다음은 우리 의 중점 인 HashSet 의 add()방법 입 니 다.원본 코드 를 붙 입 니 다.

    /**
     *    e   HashSet ，      e  Key  HashMap 
     *
     * @param e     HashSet    
     * @return true         
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

원본 코드 를 보면 HashSet 의 add()방법 이 HashMap 의 put()방법 을 호출 한 것 을 알 수 있 습 니 다.그러면 HashMap 의 put()방법 으로 넘 어 갑 니 다.

    public V put(K key, V value) {
        //        false：        
        //       true：  HashMap       
        return putVal(hash(key), key, value, false, true);
    }

HashMap 의 put()방법 은 putVal()방법 을 호출 하여 기능 을 실현 하고 putVal()의 소스 코드 를 봅 니 다.

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab;
        Node p;
        int n, i;
        //       ，  resize()       ，    n       
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /**
         *       hash         ，      
         * Hash  ，(n - 1) & hash   key       
         * (n - 1) & hash     hash % n，     
         */
        if ((p = tab[i = (n - 1) & hash]) == null)
            //         map   
            tab[i] = newNode(hash, key, value, null);
        else {//         
            Node e;
            K k;
            //          (      ) hash   ，key  
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                //          e， e   
                e = p;
                //          ，        ，         
            else if (p instanceof TreeNode)
                e = ((TreeNode) p).putTreeVal(this, tab, hash, key, value);
                //          ，       ，           
            else {
                for (int binCount = 0; ; ++binCount) {
                    //        
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //             ，                 
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //       put     ，      ，    
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //        key hashCode           ，  put  
            if (e != null) { // existing mapping for key
                //   e value
                V oldValue = e.value;
                /**
                 * onlyIfAbsent false    null ，      
                 *       
                 */
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //      
                afterNodeAccess(e);
                //     
                return oldValue;
            }
        }
        //          
        ++modCount;
        //           ，  rehash
        if (++size > threshold)
            resize();
        //      
        afterNodeInsertion(evict);
        return null;
    }

원본 코드 에서 볼 수 있 듯 이 하나의 key-value 를 HashMap 에 넣 을 때 먼저 key 의 hashCode()반환 값 에 따라 이 Entry 의 저장 위 치 를 결정 합 니 다.두 key 의 hash 값 이 같 으 면 저장 위치 가 같 습 니 다.이 두 키 의 equals 가 트 루 로 돌아간다 면.그러면 새로 추 가 된 Entry 의 value 는 원래 의 Entry 의 value 를 덮어 쓰 고 key 는 덮어 쓰 지 않 습 니 다.또한 HashSet 에서 add()에서 map.put(e,PRESENT)==null 은 false 이 고 HashSet 에서 요 소 를 추가 하 는 데 실 패 했 습 니 다.따라서 HashSet 에 존재 하 는 요 소 를 추가 하면 새로 추 가 된 집합 요 소 는 기 존의 집합 요 소 를 덮어 쓰 지 않 습 니 다.