hashmap ，hashtable， hashset 的containskey比较

痛定思痛。 2022-05-19 09:34 217阅读 0赞

一直以为这三个结构的containskey算法是一样的都是通过计算散列值计算存不存在，今天没事查了下源代码详细看下。

hashmap：

public boolean containsKey(Object key) {
            return getNode(hash(key), key) != null;
        }
    
        /**
         * Implements Map.get and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @return the node, or null if none
         */
        final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

通过源代码可以看到，hashmap的containskey方法是先散列定位到桶，然后在桶中线性查找

hashset：

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);
        }

可以看到hashset实际是hashmap的keyset  去重用的，他的contains实际就是hashmap的containskey方法

hashtable：

/**
         * Tests if the specified object is a key in this hashtable.
         *
         * @param   key   possible key
         * @return  <code>true</code> if and only if the specified object
         *          is a key in this hashtable, as determined by the
         *          <tt>equals</tt> method; <code>false</code> otherwise.
         * @throws  NullPointerException  if the key is <code>null</code>
         * @see     #contains(Object)
         */
        public synchronized boolean containsKey(Object key) {
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    return true;
                }
            }
            return false;
        }

淘汰的hashtable查找方法其实和hashmap是一样的