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可以对象去重的原因： 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的节点定义： 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的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的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; } }