精华内容
下载资源
问答
  • 题目:设计并实现一个集合数据结构Set。一个集合中没有重复元素,支持下列运算: boolean add(E o) 如果 set 中尚未存在指定的元素o,则添加此元素。 boolean addAll(Set c) 如果 set 中没有指定集合c中的...
  • Java集合数据结构

    千次阅读 2015-08-03 07:21:26
    集合类型 Set集合集合元素是不能重复的。元素是没有顺序的。所以它不能基于位置访问元素。TreeSet和HashSet是它的实现类。 List集合集合元素是可以重复的。元素是有顺序的。所以它可以基于位置访问元素。...

    集合类型

    Set集合:集合元素是不能重复的。元素是没有顺序的。所以它不能基于位置访问元素。TreeSet和HashSet是它的实现类。

    List集合: 集合元素是可以重复的。元素是有顺序的。所以它可以基于位置访问元素。ArrayList和LinkedList是它的实现类。

    Map:它包含键值对。Map的键是不能重复的。Map不能保证存储的顺序。HashMap和TreeMap是它的实现类。

    怎样来选择?

    事实上,选择Set,List或者Map是依赖你的数据结构的。如果你将要存储的数据没有重复且不需要顺序,你可以选择用Set。如果你将要存储的数据需要保证顺序,你可以选择用List。如果你有一个键值对来关联两个不同的对象或者用一个标识符来标识对象,那么你可以选择Map。

    举个例子:

    颜色的集合最好放入Set中。

    球队最好放在List中。因为球队的出场需要顺序。

    Web Sessions的集合最好在Map上;唯一的session ID会更好的引用实际对象。

    当我们选择用哪个集合的时候,我们主要关心的是集合的速度:

    • 访问元素的速度
    • 添加一个新元素的速度
    • 移除一个元素的速度
    • 迭代的速度

    此外, 也有一致性的问题。一些实现会保证访问的速度,而一些实现将有个变化的速度。我们关心的这些速度依赖于集合的具体实现。

    链表实现

    具体的类:LinkedList, LinkedHashSet

    内部原理:每个节点中都持有一个元素和下一个元素的指针。如下图:

    链表实现

    • 如果我们想加入一个元素到上图的第二个位置上,是很简单的。就像下图一样,它只须把原图中的第一个节点中的指针指向新加入的这个元素,把新加入的这个元素的指针指向原图中的第二个节点就可以了。这个速度是非常快的!不需要拷贝,移动和记录原集合中的元素。
    • 移除元素也是同理的,只要把原图中第一个节点中的指针指向原图中第二个节点的元素就可以了。

    链表实现

    当我们想访问集合中的元素是很慢的。先看看LinkedList的源码:

    /**
         * 返回指定索引位置的元素
         */
        Node<E> node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }

    当我们想获取指定位置的一个元素时,程序会先将集合大小size右移一位(也就是说,把size的大小会减少一半),然后判断索引位置是离第一个节点位置近还是最后一个节点位置近,然后开始遍历,得到指定的节点。

    举个例子:如果集合中有50个元素,如果你想获取第20个元素,那么它会从集合中第一个元素开始遍历,直到获取到第20个元素为止;如果你想获取第40个元素,那么它会从集合中最后一个元素开始遍历,直到获取到第40个元素为止。

    所以对于链表实现的集合来说,它访问元素的速度很慢。而且访问不同位置的元素,速度还不一致。还有一点我们要深深牢记的是:当我们做添加和移除操作时,都会调用到上面的node方法,从而遍历获取所要操作节点的前一个节点,因此,这会对速度有一定的影响。

    因此,当你需要更快的添加/移除,而且并不怎么关心访问时间的时候,像LinkedList这样的链表集合是更合适的。如果你打算在你的集合中有很多的添加/移除元素操作,那么这是个不错的选择。

    数组实现

    具体的类:ArrayList

    ArrayList是集合类中的唯一基于数组实现的。

    看下图:在ArrayList中,当我们把一个新元素添加到第四个位置上时,它会把第四个位置(包括第四个位置)以后的每一个位置上的元素都向后挪一位,然后在把新加入的元素插入到第四个位置上。这是很慢的,而且这并不能保证时间,它依赖于有多少的元素需要拷贝。同理,移除一个元素就是把后面的元素全部向前挪一位。

    数组实现

    还有一种更糟糕的情况。当我们创建ArrayList对象的时候,它的数组长度是固定的(这个长度可以在构造函数中设置,如果不设置默认为10)。当我们操作集合的时候,如果它的容量超过这个固定长度的话,就不得不创建一个更大容量的数组,然后把当前集合中的所有元素拷贝到新创建的这个集合当中。这是非常非常慢的。

    然而,ArrayList访问元素的速度是很快的。对于数组来说,它在内存空间中的位置是连续的,所以我们不需要遍历整个集合就可以准确的算出元素引用在内存中的位置。并且,耗费的时间也是一致的。

    因此,如果你有一些并不怎么修改,而且需要快速访问的元素,那么ArrayList是一个很好的选择。

    Hash实现

    具体的类:HashSet, HashMap

    HashSet是基于HashMap实现的,所以这里我就只解释HashMap了。

    HashMap的工作原理:HashMap底层就是一个数组结构(叫做Entry Table),数组中的每一项又是一个链表(叫做Bucket)。当新建一个HashMap的时候,就会初始化一个数组。

    Hash实现

        public V put(K key, V value) {
            ......
            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            ......
            addEntry(hash, key, value, i);
            return null;
        }

    上面是HashMap中put方法的部分代码(JDK7)。当我们向HashMap中put元素的时候,先根据key重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标),再通过这个下标访问到Bucket的链头并开始遍历整个Bucket(也就是整个链表),如果Bucket中已经存在新添加的key的值,则将原有的值设置成新添加的值,并返回旧值。否则,新加入的元素放在链头,最先加入的放在链尾。

    总的来说,程序首先根据准备放入的元素的key(通过hash算法)决定该Entry在Entry Table中的存储位置。如果新加入的这个Entry 的key与原有Entry的Key通过equals比较返回 true,那么新添加 Entry的value将覆盖集合中原有Entry的value,但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部(也就是Bucket的链头)。

    同理,从HashMap中get元素时,首先通过key计算出的Hash值来确定Entry在Entry Table中的存储位置,然后通过key的equals方法在对应位置的链表中找到需要的元素。

    总结:HashMap 底层采用一个 Entry[] 数组来保存所有的Entry对象(里面包含hash值、key-value对、下一个Entry的指针),当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。

    HashMap的rehashing

    当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容。数组容量将会自动扩大两倍,在数组扩容时,所有原存在的Entry会重新计算索引值,并且Entry链的顺序也会发生颠倒(如果还在同一个链中的话),而该新添加的Entry的索引值也会重新计算,这是最消耗性能的,这个过程就是rehashing。

    那么HashMap什么时候进行扩容呢?当HashMap中的元素个数超过数组小loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

    展开全文
  • 算法起步之并查集(不相交集合数据结构)  在java中经典的数据结构基本都给实现好了,我们可以直接调用,但是并查集这种数据结构却没有很好的替代工具,在这里我们我们自己去实现并查集数据结构。首先我们先...
    原文: 算法起步之并查集(不相交集合数据结构)

             在java中经典的数据结构基本都给实现好了,我们可以直接调用,但是并查集这种数据结构却没有很好的替代工具,在这里我们我们自己去实现并查集数据结构。首先我们先要去了解什么是并查集。并查集也是一种非常经典常用的数据结构。像求连通子图跟我们下面要研究的最小生成树问题都会用到并查集。并查集就是能够实现若干个不相交集合,较快的合并和判断元素所在集合的操作。不相交集合:一个不相交集合维护了一个不相交动态集合{s1,s2,s3……}我们用一个代表标示每一个集合,他是这个集合的成员。我们不关心哪个成员作为代表,仅关心2次查询这个集合时放回结果应该相同(如果我们不修改集合)。

        并查集主要就有三个方法:

        make-set(x)建立一个新集合唯一元素就是x,因为是不相交集合所以x不会出现在其他集合中。

        union(x,y)将包含x和y的2个动态集合合并成一个新集合。

        find-set(x)返回一个指针,这个指针指向包含x的集合的代表。

        这样说是不是有点懵,我们来看一个图。


           

            上图两棵树就是一个不相交集合,a数的代表就是a而e树代表就是e我们在a树上查找b则返回a而查找c也返回a说明b与c在同一结合上,而查找f返回e,说明b与e是在两个结合上,他们两个是不相交的。而union操作就是将两颗树合并成一棵树。

         我们先给出一个一般的实现,数组表示不相交集合保存的各个集合的元素。初始化时:


               每个元素都指向自己的父节点也就是自己。这种方式每个节点都指向自己的上一节点。而只有代表节点指向的是自己。所以我们根据这个来搜索代表节点。

    public class Ufsarry {
    
    	
    	private int[] node;
    	private int max;
    	public void makeset(int n){
    		node=new int[n+1];
    		max=n;
    		//所有的节点都是不相交集合,代表节点都指向自己。
    		for (int i = 0; i < node.length; i++) {
    			node[i]=i;
    		}
    	}
    	public int findset(int x){
    		while (x!=node[x]) {
    			x=node[x];
    		}
    		return x;
    	}
    	public void union(int x,int y){
    		node[x]=y;
    	}
    }
               下面我们要说的就是并查集的优化,按秩合并与路径压缩。听着好像很高深,其实很哄人的。两张图就可以解释。



                第一张图就是路径压缩,我们之前都是指向的上一节点,而压缩则是直接指向代表节点。而按秩合并则是我们外加一个属性来记录集合的秩。而秩多的则说明树比较高,我们将矮的树嫁接在高的树上,这样总的高度较小。而如果高度相同,则只需要将一个树嫁接过去,给他的秩加一即可。

    public class Ufs {
    	
    	private int[] father;
    	private int[] rank;
    	
    	public void makeset(int x){
    		father[x]=x;
    		rank[x]=0;
    	}
    	public int findset(int x){
    		if (father[x]!=x) {
    			father[x]=findset(father[x]);
    		}
    		return father[x];
    	}
    	
    	public void union(int x,int y){
    		x=findset(x);
    		y=findset(y);
    		if (x==y) {
    			return;
    		}else {
    			if (rank[x]>rank[y]) {
    				father[y]=x;
    			}else{
    				if (rank[x]==rank[y]) {
    					rank[y]++;
    				}
    				father[x]=y;
    			}
    		}
    	}
    
    
    }


            优化后的代码并不比之前的代码复杂。我们这里是用的数组来实现的,当然也可以用链表来实现。我们下面要说的Kruskal算法的效率就要看,我们写的并查集的实现。而按秩合并与路径压缩是目前已知渐进时间最快的Kruskal算法实现方式。

    友情提示:转载请注明出处【作者idlear    博客http://blog.csdn.net/idlear/article/details/19556587】


    展开全文
  • Python字典集合数据结构深入理解

    千次阅读 2017-11-02 20:49:28
    说明在python中字dict和set是非常常用的两种数据结构,但是两种数据结构为什么要放在一起讨论。因为他们之所以拥有非常快的速度,是因为他们的内部结构都是散列表(散列表其实是一个稀疏数组总是有空白元素的数组...

    说明

    在python中字dict和set是非常常用的两种数据结构,但是两种数据结构为什么要放在一起讨论。因为他们之所以拥有非常快的速度,是因为他们的内部结构都是散列表(散列表其实是一个稀疏数组总是有空白元素的数组称为稀疏数组)

    dict中的散列表

    • 散列表算法

    正常想要获取dict中的值,首先要知道key通过dict[key]获取对应的value,在散列表中为了达到这种操作,首先会计算key的hash值即散列值,把这个值最低的几位数字当作偏移量,在散列表里
    查找表元(具体取几位,得看当前散列表的大小)。若找到表元为空,异常KeyError,不为空,表元里会有一对 found_key:found_value。这时候 Python 会检验 search_key == found_key 是否为真,如果它们相等的话,就会返回 found_value。如果两个值不匹配,则是散列冲突。

    而散列表本
    身的索引又只依赖于这个数字的一部分。为了解决散列冲突,算法会在散列值中另外
    再取几位,然后用特殊的方法处理一下,把新得到的数字再当作索引来寻找表元。
    若这次找到的表元是空的,则同样抛出 KeyError;若非空,或者键匹配,则返回这
    个值;或者又发现了散列冲突,则重复以上的步骤。

    image

    另外在插入新值时,Python 可能会按照散列表的拥挤程度来决定是否要重新分配内存
    为它扩容。如果增加了散列表的大小,那散列值所占的位数和用作索引的位数都会随
    之增加,这样做的目的是为了减少发生散列冲突的概率。

    Python 会设法保证大概还有三分之一的表元是空的,所以在快要达到这个阈值的时
    候,原有的散列表会被复制到一个更大的空间里面。

    • dict的散列实现导致的结果

    1.key必须是可hash的,所有不可变类型都是可哈希的故可作为键,可变类型不可哈希即不可作为键,如列表,字典类型。

    2.在内存消耗上是巨大的,由于字典使用了散列表,而散列表又必须是稀疏的,这导致它在空间上的效率低下。

    3.key查询很快,hash表空间换时间。

    4.key的排列顺序,取决于添加顺序,并且当dict添加新数据,原有的排列可能会被打乱,因为Python 会设法保证大概还有三分之一的表元是空的,所以在快要达到这个阈值的时
    候,原有的散列表会被复制到一个更大的空间里面。这时候重新hash导致排列顺序改变。

    5.由此可知,不要对字典同时进行迭代和修改。如果想扫描并修改一个字典,最好分成
    两步来进行:首先对字典迭代,以得出需要添加的内容,把这些内容放在一个新字典
    里;迭代结束之后再对原有字典进行更新。

    集合中的散列表

    集合的实现和dict一样,集合的元素就相当于dict中的key,只不过集合没有散列表指向的value。
    其特点:
    - 集合里的元素必须是可散列的
    - 集合很消耗内存
    - 可以很高效地判断元素是否存在于某个集合
    - 元素的次序取决于被添加到集合里的次序
    - 往集合里添加元素,可能会改变集合里已有元素的次序

    leason | 博客

    展开全文
  • JAVA集合数据结构

    千次阅读 2009-12-16 20:23:00
    本文转自http://www.blogjava.net/action/archive/2005/11/02/17869.html 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在java.util...

    本文转自

    http://www.blogjava.net/action/archive/2005/11/02/17869.html

     

    线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在java.util包中。本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用这些类。

     

    Collection

    List

    │├LinkedList

    │├ArrayList

    │└Vector

    │ └Stack

    Set

    Map

    Hashtable

    HashMap

    WeakHashMap

     

    Collection接口

      Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如ListSet

      所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个空的Collection,有一个Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection

      如何遍历Collection中的每一个元素?不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下:

        Iterator it = collection.iterator(); // 获得一个迭代子

        while(it.hasNext()) {

          Object obj = it.next(); // 得到下一个元素

        }

      由Collection接口派生的两个接口是ListSet

    主要方法:

    boolean add(Object o)添加对象到集合

    boolean remove(Object o)删除指定的对象

    int size()返回当前集合中元素的数量

    boolean contains(Object o)查找集合中是否有指定的对象

    boolean isEmpty()判断集合是否为空

    Iterator iterator()返回一个迭代器

    boolean containsAll(Collection c)查找集合中是否有集合c中的元素

    boolean addAll(Collection c)将集合c中所有的元素添加给该集合

    void clear()删除集合中所有元素

    void removeAll(Collection c)从集合中删除c集合中也有的元素

    void retainAll(Collection c)从集合中删除集合c中不包含的元素

     

    List接口

      List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。

    和下面要提到的Set不同,List允许有相同的元素。

      除了具有Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个ListIterator接口,和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素,还能向前或向后遍历。

      实现List接口的常用类有LinkedListArrayListVectorStack

    主要方法:

    void add(int index,Object element)在指定位置上添加一个对象

    boolean addAll(int index,Collection c)将集合c的元素添加到指定的位置

    Object get(int index)返回List中指定位置的元素

    int indexOf(Object o)返回第一个出现元素o的位置.

    Object removeint(int index)删除指定位置的元素

    Object set(int index,Object element)用元素element取代位置index上的元素,返回被取代的元素

     

    LinkedList

      LinkedList实现了List接口,允许null元素。此外LinkedList提供额外的getremoveinsert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。

      注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List

        List list = Collections.synchronizedList(new LinkedList(...));

     

    ArrayList

      ArrayList实现了可变大小的数组。它允许所有元素,包括nullArrayList没有同步。

    sizeisEmptygetset方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。

      每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

      和LinkedList一样,ArrayList也是非同步的(unsynchronized)。

    主要方法:

    Boolean add(Object o)将指定元素添加到列表的末尾

    Boolean add(int index,Object element)在列表中指定位置加入指定元素

    Boolean addAll(Collection c)将指定集合添加到列表末尾

    Boolean addAll(int index,Collection c)在列表中指定位置加入指定集合

    Boolean clear()删除列表中所有元素

    Boolean clone()返回该列表实例的一个拷贝

    Boolean contains(Object o)判断列表中是否包含元素

    Boolean ensureCapacity(int m)增加列表的容量,如果必须,该列表能够容纳m个元素

    Object get(int index)返回列表中指定位置的元素

    Int indexOf(Object elem)在列表中查找指定元素的下标

    Int size()返回当前列表的元素个数

     

    Vector

      Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和ArrayList创建的Iterator是同一接口,但是,因为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。

     

    Stack

      Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的pushpop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

     

    Set接口

      Set是一种不包含重复的元素的Collection,即任意的两个元素e1e2都有e1.equals(e2)=falseSet最多有一个null元素。

      很明显,Set的构造函数有一个约束条件,传入的Collection参数不能包含重复的元素。

      请注意:必须小心操作可变对象(Mutable Object)。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

     

    Map接口

      请注意,Map没有继承Collection接口,Map提供keyvalue的映射。一个Map中不能包含相同的key,每个key只能映射一个valueMap接口提供3种集合的视图,Map内容可以被当作一组key集合,一组value集合,或者一组key-value映射。

    主要方法:

    boolean equals(Object o)比较对象

    boolean remove(Object o)删除一个对象

    put(Object key,Object value)添加key和value

    Hashtable

      Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value

      添加数据使用put(key, value),取出数据使用get(key),这两个基本操作的时间开销为常数。

    Hashtable通过initial capacityload factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大,这会影响像getput这样的操作。

    使用Hashtable的简单示例如下,将123放到Hashtable中,他们的key分别是”one”,”two”,”three”:

        Hashtable numbers = new Hashtable();

        numbers.put(one, new Integer(1));

        numbers.put(two, new Integer(2));

        numbers.put(three, new Integer(3));

      要取出一个数,比如2,用相应的key

        Integer n = (Integer)numbers.get(two);

        System.out.println(two = + n);

      由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCodeequals方法。hashCodeequals方法继承自根类Object,如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。

      如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),要避免这种问题,只需要牢记一条:要同时复写equals方法和hashCode方法,而不要只写其中一个。

      Hashtable是同步的。

     

    HashMap

      HashMapHashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null valuenull key。,但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。

     

    WeakHashMap

      WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。

     

    总结

      如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList

      如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高,如果多个线程可能同时操作一个类,应该使用同步的类。

      要特别注意对哈希表的操作,作为key的对象要正确复写equalshashCode方法。

      尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变。这就是针对抽象编程。

    展开全文
  • Common Lisp学习之五:集合数据结构

    千次阅读 2013-12-29 22:31:33
    向量是基于数字索引的集合,分为变长和定长两种。 (vector values) 用来创建并初始化一个定长的向量。 (make-array dim &key initial-element fill-pointer adjustable ...)  用来创建变长向量,其中命名参数...
  • 数据结构集合

    万次阅读 2020-09-08 22:57:44
    数据结构集合
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都有着独特的数据...
  • 集合这个概念应该大家在学习数学的时候都听过并且有学习过,它也是一种数据结构,我们还是需要用代码来实现集合的很多方法。 学习过ES6语法的小伙伴应该知道,ES6新增了一种 Set 数据结构,这就是集合,尽管官方已经...
  • 不相交集合,即集合内元素无交集。在一些具体应用中,需将n个不同的元素分成一组不相交的集合。不相交集合的两个重要操作,...不相交集合数据结构保持一组不相交的动态集合S={S1, S2,…, Sk}。每个集合通过一个代表来识
  • List集合&数据结构

    千次阅读 2020-06-16 14:09:21
    1.1集合的体系结构 集合类的特点 提供一种存储空间可变的存储模型,存储的数据容量可以随时发生改变 集合类的体系 1.2Collection集合概述和基本使用 Collection集合概述 是单例集合的顶层接口,他表示一组对象,...
  • 数据结构集合

    千次阅读 2014-02-11 13:27:09
    所谓直接存储是指:该类型的集合数据元素可以直接通过下标(也即index)来访问,在C#中有三种形式:Array(包括数组和List),string,struct。直接存储结构的优点是:向数据结构中添加元素是很高效的,只要直接放在...
  • 不相交集合数据结构的概念和操作:  不相交集合数据结构(disjoing-set data structure)保持一组不相交的动态集合S={S1,S2,S3,……Sk}。每个集合通过一个代表来识别,代表即集合中的某个成员。 不相交集合数据...
  • java集合(上)——数据结构详解

    千次阅读 2017-02-08 14:55:43
    当我们要处理一串数据的时候,相比较c++和c中的数组和指针,在Java中我们更为常用的是ArrayList、HashMap等集合数据结构。c语言对指针的支持成就了他的深度,而Java中多种多样的包装类成就了他的广度。在java中,...
  • 不相交集合数据结构的概念和操作:  不相交集合数据结构(disjoing-set data structure)保持一组不相交的动态集合S={S1,S2,S3,……Sk}。每个集合通过一个代表来识别,代表即集合中的某个成员。 我们希望不...
  • JavaScript数据结构-集合

    千次阅读 2016-11-06 15:41:57
    集合(set)是一种包含不同元素的数据结构集合中的元素称为成员。集合具有两个重要特性: (1)集合中的成员是无序的 (2)集合中不允许相同成员存在 当想创建一个数据结构,用来保存一些独一无二的元素时,...
  • 不相交集合数据结构(disjoint-set data struct)保持一组不相交的动态集合S={S1,S2,……,Sk} 这种数组结构支持三种操作: (1)MAKE-SET(x):构造一种只有元素x的集合 (2)UNION(x,y):合并两个集合 (3)FIND...
  • JavaScript数据结构——集合JavaScript数据结构集合)封装集合集合常见的操作JavaScript代码实现封装集合基本方法实现多个集合操作测试代码 JavaScript数据结构集合集合通常是由一组无序的、不能重复的元素...
  • 数据结构-集合

    千次阅读 2019-05-06 17:21:36
    假设利用两个线性表LA和LB分别表示两个集合A和B(即:线性表中的数据元素即为集合中的成员),现要求一个新的集合A=A∪B。这就要求对线性表做如下操作:扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据...
  • 不相交集合数据结构

    千次阅读 2015-06-06 00:15:09
    不相交集合数据结构本来想着来实现基于贪婪思想的Kruskal算法—–最小生成树的算法之一。 却发现当我们合并集合时里面还涉及到一个判断“环”的问题,继而有了本篇博文:不相交集合数据结构
  • 数据结构集合

    千次阅读 2019-04-26 16:28:58
    写在前边:本文是个人学习笔记。...List集合 集合初始化 数组集合 集合与泛型 元素的比较: JDK中使用的排序方法TimSort hashCode 和equals fail-fast机制 Map类集合: 关于树: 平衡二...
  • Java 数据结构集合

    千次阅读 2018-11-15 23:01:22
    List 集合是线性数据结构的主要实现,List 集合的遍历结果是稳定的。该体系最常用的是 ArrayList 和 LinkedList。 ArrayList 是容量可以改变的非线程安全集合。内部实现使用数组进行存储,集合扩容时会创建更大的...
  • 集合中常用数据结构总结

    千次阅读 2019-04-28 20:17:49
    常见的和集合相关的数据结构有: 数组, 栈, 队列,链表,哈希表, 二叉树 下面简单总结一下个数据结构特点: 1. 数组 ArrayList(public class ArrayList extends AbstractList implements List, RandomAccess, ...
  • Java集合数据存储结构总结

    千次阅读 2018-03-11 19:56:23
    一)Collection接口:存储单列数据: (1)List:单列有序集合(可以重复): A、ArrayList:底层结构是数组,底层查询快,增删慢(非线程安全); B、LinkedList:底层结构是链表型的,增删快,查询慢; C、...
  • 数组、链表等常用数据结构集合浅解(java)

    万次阅读 多人点赞 2017-04-21 20:23:38
    数组、链表等常用数据结构和集合浅解(java)脑子转了一圈,巴拉巴拉的写了一大堆,本来今天步行者打骑士的比赛在上半场已经花了,步行者领先20多分,...1.集合数据结构中的元素之间除了“同属一个集合” 的相互关系...
  • Python set(集合)数据结构

    千次阅读 2018-12-25 16:34:41
    set(集合)数据结构 set(集合)是⼀个⾮常有⽤的数据结构。它与列表(list)的⾏为类似,区别在于set不能 包含重复的值。 这在很多情况下⾮常有⽤。例如你可能想检查列表中是否包含重复的元素,你有两个选 择,第⼀个...
  • set(集合)数据结构

    千次阅读 2017-07-03 15:53:29
    (集合)是一个非常有用的数据结构。它与列表list的行为类似,区别在于set不能包含重复的值。 some_list = ['a', 'b', 'c', 'd', 'b', 'a', 'n', 'n'] duplicates = set([x for x in some_list if some_list.count(x)...
  • 用于不相交集合的数据结构 ...不相交集合数据结构保持一组不相交的动态集合,每个集合通过一个代表来标识,代表即集合中的某个成员。 一些操作: MAKE-SET(x): 建立一个新的集合,其唯一成员为x。 UN

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 76,164
精华内容 30,465
关键字:

集合数据结构

数据结构 订阅