指点成金-最美分享吧

登录

List 与 Set 的 contains方法比较

佚名 举报

篇首语：本文由小编为大家整理，主要介绍了List 与 Set 的 contains方法比较相关的知识，希望对你有一定的参考价值。

一、结论

1. set.contains("obj")的效率明显高于list.contains("obj")

主要比较了 ArrayList,LinkedList 和 HashSet

2. 主要原因是 List 底层是通过遍历的方式去作比较，而 Set 是算key的hash值的形式与集合内元素比较

二、源码

1. ArrayList

ArrayList list = new ArrayList<>();list.contains("");// 调用indexof    /**     * Returns true if this list contains the specified element.      * More formally, returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e)).     * 参数: o – element whose presence in this list is to be tested     * 返回: true if this list contains the specified element     */public boolean contains(Object o) {    return indexOf(o) >= 0;}/** * Returns the index of the first occurrence of the specified element in this list,  * or -1 if this list does not contain the element.  * More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), * or -1 if there is no such index. */public int indexOf(Object o) {    if (o == null) {        for (int i = 0; i < size; i++)            if (elementData[i]==null)                return i;    } else {        for (int i = 0; i < size; i++)            if (o.equals(elementData[i]))                return i;    }    return -1;}
2. LinkedList
// 类似 ArrayListLinkedList linkedList = new LinkedList<>();linkedList.contains("");public boolean contains(Object o) {    return indexOf(o) != -1;}public int indexOf(Object o) {    int index = 0;    if (o == null) {        for (Node x = first; x != null; x = x.next) {            if (x.item == null)                return index;            index++;        }    } else {        for (Node x = first; x != null; x = x.next) {            if (o.equals(x.item))                return index;            index++;        }    }    return -1;}
3.  HashSet
HashSet set = new HashSet<>();set.contains("");/** * Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)). * 参数: o – element whose presence in this set is to be tested * 返回: true if this set contains the specified element */public boolean contains(Object o) {    return map.containsKey(o);}// 下面就是高效率的关键点，算hash二不是一个个比对/** * Returns true if this map contains a mapping for the specified key. * 参数: key – The key whose presence in this map is to be tested * 返回: true if this map contains a mapping for the specified key. */public boolean containsKey(Object key) {    return getNode(hash(key), key) != null;}/** * 计算key.hashCode()并将哈希值的高位扩展为低位。 */static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}/** * Implements Map.get and related methods * 先算比对hash 再 equals * 参数: hash – hash for key ,key – the key * 返回: the node, or null if none */final Node getNode(int hash, Object key) {    Node[] tab; Node 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)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;}
以上是关于List 与 Set 的 contains方法比较的主要内容，如果未能解决你的问题，请参考以下文章
            

    

    

       上一篇Java double转long方法 
            

    

        下一篇安卓官方团队支持的新语言 —— Kotlin 
            





    
相关文章

    
    
                 
    
        
    
                  
                兵器百科 俄罗斯MP-443手枪 
            
        
    
        
    
            
    兵器百科 俄罗斯MP-443手枪 
    
            
            
    
                资讯
                佚名
                100
                
            
    
        
    
    
    
        
    
        
    
                  
                前端开发——两种定时器 
            
        
    
        
    
            
    前端开发——两种定时器 
    
            
            
    
                资讯
                佚名
                32
                
            
    
        
    
    
    
        
    
        
    
                  
                词语大全 荡涤的近义词是什么 
            
        
    
        
    
            
    词语大全 荡涤的近义词是什么 
    
            
            
    
                资讯
                佚名
                43
                
            
    
        
    
    
    
        
        
    
        
    
                  
                linux&#47;debian到底怎么重启和关机 
            
        
    
        
    
            
    linux&#47;debian到底怎么重启和关机 
    
            
            
    
                资讯
                佚名
                19
                
            
    
        
    
    
    
        
    
        
    
                  
                QT实现ping命令 
            
        
    
        
    
            
    QT实现ping命令 
    
            
            
    
                资讯
                佚名
                42
                
            
    
        
    
    
    
        
        
        
    
        
    
                  
                TCP/IP详解 笔记十四 
            
        
    
        
    
            
    TCP/IP详解 笔记十四 
    
            
            
    
                资讯
                佚名
                26
                
            
    
        
    
    
    
        
    
        
    
                  
                ubuntu怎么查看cpu的核数 
            
        
    
        
    
            
    ubuntu怎么查看cpu的核数 
    
            
            
    
                资讯
                佚名
                170
                
            
    
        
    
    
    
            


         
    
    




        
    

        

            Copyright © 2021  闽ICP备10200827号-10