HashSet与TreeSet的contains方法解读

缺乏、安全感 2021-06-10 20:39 504阅读 0赞

#### Set与Map的关系 ####

1、看下HashSet的add方法：

// Dummy value to associate with an Object in the backing Map
        private static final Object PRESENT = new Object();
    
        public boolean add(E e) { 
            return map.put(e, PRESENT)==null;
        }

它的put调用了map的put方法，其实Set和Map是本家，Set存放的对象作为map的key值，value（PRESENT）为同一个空对象。我们知道HashMap的put流程是：首先计算key的hash值，确定要存放的桶位置，再通过equals方法比对链表（或红黑树）上的对象，不存在则放入，存在则不操作。如下图，这也就是Set可以对象去重的原因：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70_pic_center]  
2、TreeSet的add方法：

/** * The backing map. */
        private transient NavigableMap<E,Object> m;
      
        public boolean add(E e) { 
            return m.put(e, PRESENT)==null;
        }

调用了treeMap的put方法，它是从根节点开始，对key与左右子树的key通过compare方法进行比较，找到则覆盖原有值，找不到则新增节点。

#### HashMap和TreeMap ####

HashMap基于哈希表（无序），而TreeMap基于红黑树（有序）。

*  这是HashMap的节点定义：

static class Node<K,V> implements Map.Entry<K,V> { 
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    }

维护了key的hash值，key和value，以及一个链式结构。

*  这是TreeMap的节点

static final class Entry<K,V> implements Map.Entry<K,V> { 
            K key;
            V value;
            Entry<K,V> left;
            Entry<K,V> right;
            Entry<K,V> parent;
            boolean color = BLACK;
    }

维护了key，value，左右子树，父节点，红黑标记

#### HashSet与TreeSet的Contains(key)方法解读 ####

##### 1、HashSet #####

HashSet的Contains(key)调用了hashMap的ContainsKey(key)

private transient HashMap<E,Object> map;
        
        /** * Returns <tt>true</tt> if this set contains the specified element. * More formally, returns <tt>true</tt> if and only if this set * contains an element <tt>e</tt> such that * <tt>(o==null ? e==null : o.equals(e))</tt>. * * @param o element whose presence in this set is to be tested * @return <tt>true</tt> if this set contains the specified element */
        public boolean contains(Object o) { 
            return map.containsKey(o);
        }

HashMap的Contains(key)，就是看该key下有没有存储的对象，传入Hash(key)和key对象

/** * Returns <tt>true</tt> if this map contains a mapping for the * specified key. * * @param key The key whose presence in this map is to be tested * @return <tt>true</tt> if this map contains a mapping for the specified * key. */
        public boolean containsKey(Object key) { 
            return getNode(hash(key), key) != null;
        }

##### TreeSet #####

TreeSet的Contains(key)调用了TreeMap的ContainsKey(key)

* Returns { @code true} if this map contains a mapping for the specified
         * key.
         *
         * @param key key whose presence in this map is to be tested
         * @return { @code true} if this map contains a mapping for the
         *         specified key
         * @throws ClassCastException if the specified key cannot be compared
         *         with the keys currently in the map
         * @throws NullPointerException if the specified key is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         */
        public boolean containsKey(Object key) { 
            return getEntry(key) != null;
        }

通过获取这个key的对象看是否存在来判断。获取这个key的方法自然就是红黑树的查找了。

/** * Returns this map's entry for the given key, or {@code null} if the map * does not contain an entry for the key. * * @return this map's entry for the given key, or {@code null} if the map * does not contain an entry for the key * @throws ClassCastException if the specified key cannot be compared * with the keys currently in the map * @throws NullPointerException if the specified key is null * and this map uses natural ordering, or its comparator * does not permit null keys */
        final Entry<K,V> getEntry(Object key) { 
            // 存在comparator的话通过自定义的comparator比较查找，否则就是默认的Comparable实现
            if (comparator != null)
                return getEntryUsingComparator(key);
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            Entry<K,V> p = root;
            while (p != null) { 
                int cmp = k.compareTo(p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
            return null;
        }
    
        /** * Version of getEntry using comparator. Split off from getEntry * for performance. (This is not worth doing for most methods, * that are less dependent on comparator performance, but is * worthwhile here.) */
        final Entry<K,V> getEntryUsingComparator(Object key) { 
            @SuppressWarnings("unchecked")
                K k = (K) key;
            Comparator<? super K> cpr = comparator;
            if (cpr != null) { 
                Entry<K,V> p = root;
                while (p != null) { 
                    int cmp = cpr.compare(k, p.key);
                    if (cmp < 0)
                        p = p.left;
                    else if (cmp > 0)
                        p = p.right;
                    else
                        return p;
                }
            }
            return null;
        }

#### 总结： ####

HashSet与TreeSet的Contains方法的不同实现源于他们的结构不同，一个是哈希表，一个是红黑树。时间复杂度的话，我们一般认为Hash表查找的复杂度是O(1),红黑树是O（lgN）。

#### 拓展 ####

在看到containsKey方法时，还看到有个containsValue方法（其实是全部元素查找遍历，时间复杂度O(n),一个比较低效的方法）：  
如HashMap：

/** * Returns <tt>true</tt> if this map maps one or more keys to the * specified value. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified value */
        public boolean containsValue(Object value) { 
            Node<K,V>[] tab; V v;
            if ((tab = table) != null && size > 0) { 
            	// 对所有桶进行遍历
                for (int i = 0; i < tab.length; ++i) { 
                	// 桶中的链式或红黑树进行遍历
                    for (Node<K,V> e = tab[i]; e != null; e = e.next) { 
                        if ((v = e.value) == value ||
                            (value != null && value.equals(v)))
                            return true;
                    }
                }
            }
            return false;
        }

TreeMap  
同理，他也是一个元素一个元素比较，先从最左下角的元素开始，逐个往右子树遍历（后序遍历）。

public boolean containsValue(Object value) { 
            for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
                if (valEquals(value, e.value))
                    return true;
            return false;
        }
        
        /** * Returns the first Entry in the TreeMap (according to the TreeMap's * key-sort function). Returns null if the TreeMap is empty. */
        final Entry<K,V> getFirstEntry() { 
            Entry<K,V> p = root;
            if (p != null)
                while (p.left != null)
                    p = p.left;
            return p;
        }
    
    	/** * Returns the successor of the specified Entry, or null if no such. */
        static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { 
            if (t == null)
                return null;
            else if (t.right != null) { 
                Entry<K,V> p = t.right;
                while (p.left != null)
                    p = p.left;
                return p;
            } else { 
                Entry<K,V> p = t.parent;
                Entry<K,V> ch = t;
                while (p != null && ch == p.right) { 
                    ch = p;
                    p = p.parent;
                }
                return p;
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210518/bb4f241d91074b5f8bd2d748cd3d96c8.png

发表评论取消回复

表情：

评论列表（有 0 条评论，504人围观）

还没有评论，来说两句吧...

相关阅读

相关 treeset java_Java TreeSet contains（）方法与示例

treeset java TreeSet类contains()方法 (TreeSet Class contains() method) contains() me

野性酷女/ 2023年03月05日 15:53/ 0 赞/ 46 阅读

相关 Java HashSet contains（）方法与示例

HashSet类contains()方法 (HashSet Class contains() method) contains() method is availa

- 日理万妓/ 2023年03月05日 15:53/ 0 赞/ 43 阅读

相关 Java HashSet 与 TreeSet比较

HashSet：底层使用HashMap，元素需实现hashcode和equals方法 HashSet 添加的元素是无序的，因为是根据重写的hashcode 方法散列的形式

素颜马尾好姑娘i/ 2023年02月17日 03:41/ 0 赞/ 1 阅读

相关 TreeSet和HashSet

目录 TreeSet 1、特性 2、通过构造方法自定义排序规则 3、通过包装达到线程安全 4、TreeSet 迭代 5、关于是否可以保存null 元素 H

心已赠人/ 2022年11月27日 15:42/ 0 赞/ 254 阅读

相关 hashset treeset java_Java——HashSet和TreeSet的区别

HashSet HashSet有以下特点  不能保证元素的排列顺序，顺序有可能发生变化  不是同步的  集合元素可以是null,但只能放入一个null 当向Ha

浅浅的花香味﹌/ 2022年11月03日 10:40/ 0 赞/ 286 阅读

相关 HashSet与TreeSet的区别

![Center][]HashSet与TreeSet的区别： HashSet是基于hash算法实现的，性能优于TreeSet。通常使用HashSet，在我们需要对其中元素排

浅浅的花香味﹌/ 2022年08月24日 00:55/ 0 赞/ 278 阅读

相关 Java 之 HashSet与TreeSet

Java 之 HashSet与TreeSet HashSet 此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set

比眉伴天荒/ 2022年06月18日 10:50/ 0 赞/ 284 阅读

相关 HashSet与TreeSet

HashSet与TreeSet 一、HashSet特点以及存储自定义对象保证元素唯一性 1，HashSet存储字符串并遍历 Java Code <tab

男娘i/ 2022年05月21日 12:50/ 0 赞/ 311 阅读

相关 TreeSet&HashSet

package com.test1; import java.util.HashSet; import java.util.Set;

爱被打了一巴掌/ 2022年01月09日 12:11/ 0 赞/ 342 阅读

相关 HashSet与TreeSet的contains方法解读

Set与Map的关系 1、看下HashSet的add方法： // Dummy value to associate with an Object in the

缺乏、安全感/ 2021年06月10日 20:39/ 0 赞/ 505 阅读