美文网首页
数据结构(集合)

数据结构(集合)

作者: joshul | 来源:发表于2017-03-24 22:46 被阅读0次
    集合框架
    1.常用容器继承关系图
    Paste_Image.png
    Iterator不是容器,只是一个操作遍历集合的方法
    2.Collection和Map

    在Java容器中一共定义了2种集合, 顶层接口分别是Collection和Map。但是这2个接口都不能直接被实现使用,分别代表两种不同类型的容器。

    Collection:是容器继承关系中的顶层接口。是一组对象元素组。有些容器允许重复元素有的不允许,有些有序有些无序。 JDK不直接提供对于这个接口的实现,但是提供继承与该接口的子接口比如 List Set。
    接口定义:

      public interface Collection<E> extends Iterable<E> {
          ...
      }
    

    泛型<E>即该Collection中元素对象的类型,继承的Iterable是定义的一个遍历操作接口,采用hasNext next的方式进行遍历。
    几个重要的接口方法:

      add(E e)确保此 collection 包含指定的元素(可选操作)。
      clear()移除此 collection 中的所有元素(可选操作)。
      contains(Object o)如果此 collection 包含指定的元素,则返回 true。
      isEmpty()如果此 collection 不包含元素,则返回 true。
      iterator()返回在此 collection 的元素上进行迭代的迭代器。
      remove(Object o)从此 collection 中移除指定元素的单个实例,如果存在的话(可选操作)。
      retainAll(Collection<?> c)仅保留此 collection 中那些也包含在指定 collection 的元素(可选操作)。
      size()返回此 collection 中的元素数
      toArray()返回包含此 collection 中所有元素的数组
      toArray(T[] a)返回包含此 collection 中所有元素的数组;返回数组的运行时类型与指定数组的运行时类型相同
    

    Map:一个保存键值映射的对象。 映射Map中不能包含重复的key,每一个key最多对应一个value。
    Map集合提供3种遍历访问方法:
    1.获得所有key的集合然后通过key访问value。
    2.获得value的集合。
    3.获得key-value键值对的集合(key-value键值对其实是一个对象,里面分别有key和value)。

    Map的访问顺序取决于Map的遍历访问方法的遍历顺序。 有的Map,比如TreeMap可以保证访问顺序,但是有的比如HashMap,无法保证访问顺序。

    接口定义如下:

      public interface Map<K,V> {
          ...
          interface Entry<K,V> {
              K getKey();
              V getValue();
              ...
          }
      }
    

    泛型<K,V>分别代表key和value的类型。这时候注意到还定义了一个内部接口Entry,其实每一个键值对都是一个Entry的实例关系对象,所以Map实际其实就是Entry的一个Collection,然后Entry里面包含key,value。再设定key不重复的规则,自然就演化成了Map。(个人理解)

    几个重要的接口方法:

      clear()从此映射中移除所有映射关系
      containsKey(Object key)如果此映射包含指定键的映射关系,则返回 true。
      containsValue(Object value)如果此映射将一个或多个键映射到指定值,则返回 true。
      entrySet()返回此映射中包含的映射关系的 Set 视图。
      equals(Object o) 比较指定的对象与此映射是否相等。
      get(Object key)返回指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null。
      isEmpty()如果此映射未包含键-值映射关系,则返回 true。
      keySet()返回此映射中包含的键的 Set 视图。
      put(K key, V value)将指定的值与此映射中的指定键关联(可选操作)。
      putAll(Map<? extends K,? extends V> m)从指定映射中将所有映射关系复制到此映射中(可选操作)。
      remove(Object key)如果存在一个键的映射关系,则将其从此映射中移除(可选操作)。
      size()返回此映射中的键-值映射关系数。
      values()返回此映射中包含的值的 Collection 视图。
    

    3个遍历Map的方法:

    1.Set<K> keySet():

    会返回所有key的Set集合,因为key不可以重复,所以返回的是Set格式,而不是List格式。
    获取到所有key的Set集合后,由于Set是Collection类型的,所以可以通过Iterator去遍历所有的key,然后再通过get方法获取value
    如下:

    Map<String,String> map = new HashMap<String,String>();
    map.put("01", "zhangsan");
    map.put("02", "lisi");
    map.put("03", "wangwu");
    
    Set<String> keySet = map.keySet();//先获取map集合的所有键的Set集合
    Iterator<String> it = keySet.iterator();//有了Set集合,就可以获取其迭代器。
    
    while(it.hasNext()) {
         String key = it.next();
         String value = map.get(key);//有了键可以通过map集合的get方法获取其对应的值。
         System.out.println("key: "+key+"-->value: "+value);//获得key和value值
    }
    
    2.Collection<V> values():

    直接获取values的集合,无法再获取到key。所以如果只需要value的场景可以用这个方法。获取到后使用Iterator去遍历所有的value。
    如下:

        Map<String,String> map = new HashMap<String,String>();
        map.put("01", "zhangsan");
        map.put("02", "lisi");
        map.put("03", "wangwu");
    
        Collection<String> collection = map.values();//返回值是个值的Collection集合
        System.out.println(collection);
    
    3.Set< Map.Entry< K, V>> entrySet():

    是将整个Entry对象作为元素返回所有的数据。然后遍历Entry,分别再通过getKey和getValue获取key和value。
    如下:

    Map<String,String> map = new HashMap<String,String>();
    map.put("01", "zhangsan");
    map.put("02", "lisi");
    map.put("03", "wangwu");
    
    //通过entrySet()方法将map集合中的映射关系取出(这个关系就是Map.Entry类型)
    Set<Map.Entry<String, String>> entrySet = map.entrySet();
    //将关系集合entrySet进行迭代,存放到迭代器中
    Iterator<Map.Entry<String, String>> it = entrySet.iterator();
    
    while(it.hasNext()) {
          Map.Entry<String, String> me = it.next();//获取Map.Entry关系对象me
          String key = me.getKey();//通过关系对象获取key
          String value = me.getValue();//通过关系对象获取value
    }
    

    通过以上3种遍历方式我们可以知道,如果你只想获取key,建议使用keySet。如果只想获取value,建议使用values。如果key value希望遍历,建议使用entrySet。
    (虽然通过keySet可以获得key再间接获得value,但是效率没entrySet高,不建议使用这种方法)

    3.List、Set和Queue

    List和Set。他们2个是继承Collection的子接口,就是说他们也都是负责存储单个元素的容器。
    最大的区别如下:
    1.List是存储的元素容器是有个有序的可以索引到元素的容器,并且里面的元素可以重复。
    2.Set里面和List最大的区别是Set里面的元素对象不可重复。

    List:一个有序的Collection(或者叫做序列)。使用这个接口可以精确掌控元素的插入,还可以根据index获取相应位置的元素。
    不像Set,list允许重复元素的插入。有人希望自己实现一个list,禁止重复元素,并且在重复元素插入的时候抛出异常,但是我们不建议这么做。
    
    List提供了一种特殊的iterator遍历器,叫做ListIterator。这种遍历器允许遍历时插入,替换,删除,双向访问。 并且还有一个重载方法允许从一个指定位置开始遍历。
    List接口新增的接口,会发现add,get这些都多了index参数,说明在原来Collection的基础上,List是一个可以指定索引,有序的容器。
    在这注意以下添加的2个新Iteractor方法:
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    
    ListIterator的代码:
    
    public interface ListIterator<E> extends Iterator<E> {
        // Query Operations
    
        boolean hasNext();
    
        E next();
    
        boolean hasPrevious();
    
        E previous();
    
        int previousIndex();
    
        void remove();
    
        void set(E e);
    
        void add(E e);
    }
    

    一个集合在遍历过程中进行插入删除操作很容易造成错误,特别是无序队列,是无法在遍历过程中进行这些操作的。
    但是List是一个有序集合,所以在这实现了一个ListIteractor,可以在遍历过程中进行元素操作,并且可以双向访问。

    List的实现类,ArrayList和LinkedList.

    1.ArrayList
    ArrayList是一个实现了List接口的可变数组可以插入null它的size, isEmpty, get, set, iterator,add这些方法的时间复杂度是
    O(1),如果add n个数据则时间复杂度是O(n).ArrayList不是synchronized的。

    然后我们来简单看下ArrayList源码实现。这里只写部分源码分析。
    所有元素都是保存在一个Object数组中,然后通过size控制长度。

           transient Object[] elementData;
           private int size;
           public boolean add(E e) {
               ensureCapacityInternal(size + 1);  // Increments modCount!!
               elementData[size++] = e;
               return true;
           }
    
           private void ensureCapacityInternal(int minCapacity) {
               if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                   minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
               }
    
               ensureExplicitCapacity(minCapacity);
           }
    
           private void ensureExplicitCapacity(int minCapacity) {
               modCount++;
    
               // overflow-conscious code
               if (minCapacity - elementData.length > 0)
                   grow(minCapacity);
           }
    
           private void grow(int minCapacity) {
               // overflow-conscious code
               int oldCapacity = elementData.length;
               int newCapacity = oldCapacity + (oldCapacity >> 1);
               if (newCapacity - minCapacity < 0)
                   newCapacity = minCapacity;
               if (newCapacity - MAX_ARRAY_SIZE > 0)
                   newCapacity = hugeCapacity(minCapacity);
               // minCapacity is usually close to size, so this is a win:
               elementData = Arrays.copyOf(elementData, newCapacity);
           }
    

    其实在每次add的时候会判断数据长度,如果不够的话会调用Arrays.copyOf,复制一份更长的数组,并把前面的数据放进去。
    我们再看下remove的代码是如何实现的。

    public E remove(int index) {
          rangeCheck(index);
          modCount++;
          E oldValue = elementData(index);
          int numMoved = size - index - 1;
          if (numMoved > 0)
          System.arraycopy(elementData, index+1, elementData, index,numMoved);
          elementData[--size] = null; // clear to let GC do its work
          return oldValue;
    }
    其实就是直接使用System.arraycopy把需要删除index后面的都往前移一位然后再把最后一个去掉。
    
    2.LinkedList

    LinkedList是一个链表维护的序列容器。和ArrayList都是序列容器,一个使用数组存储,一个使用链表存储。
    数组和链表2种数据结构的对比:
    1.查找方面。数组的效率更高,可以直接索引出查找,而链表必须从头查找。
    2.插入删除方面。特别是在中间进行插入删除,这时候链表体现出了极大的便利性,只需要在插入或者删除的地方断掉链
    然后插入或者移除元素,然后再将前后链重新组装,但是数组必须重新复制一份将所有数据后移或者前移。
    3.在内存申请方面,当数组达到初始的申请长度后,需要重新申请一个更大的数组然后把数据迁移过去才行。而链表只需
    要动态创建即可。
    如上LinkedList和ArrayList的区别也就在此.

    总结:

    List实现 使用场景 数据结构
    ArrayList 数组形式访问List链式集合数据,元素可重复,访问元素较快 数组
    LinkedList 链表方式的List链式集合,元素可重复,元素的插入删除较快 双向链表
    Vector: 底层是数组数据结构。线程同步。被ArrayList替代了。因为效率低。

    4.Set

    Set的核心概念就是集合内所有元素不重复。在Set这个子接口中没有在Collection特别实现什么额外的方法,应该只是定义了一个Set概念。下面我们来看Set的几个常用的实现HashSet、LinkedHashSet、TreeSet

    HashSet:
    HashSet实现了Set接口,基于HashMap进行存储。遍历时不保证顺序,并且不保证下次遍历的顺序和之前一样。HashSet中允许null元素。

    进入到HashSet源码中我们发现,所有数据存储在:
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();
    意思就是HashSet的集合其实就是HashMap的key的集合,然后HashMap的val默认都是PRESENT。HashMap的定义即是key不重复的集合。使用HashMap实现,这样HashSet就不需要再实现一遍。
    所以所有的add,remove等操作其实都是HashMap的add、remove操作。遍历操作其实就是HashMap的keySet的遍历,举例如下

        ...
        public Iterator<E> iterator() {
            return map.keySet().iterator();
        }
    
        public boolean contains(Object o) {
            return map.containsKey(o);
        }
    
        public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }
    
        public void clear() {
            map.clear();
        }
        ...
    

    LinkedHashSet:
    LinkedHashSet的核心概念相对于HashSet来说就是一个可以保持顺序的Set集合。HashSet是无序的,LinkedHashSet会根据add,remove这些操作的顺序在遍历时返回固定的集合顺序。这个顺序不是元素的大小顺序,而是可以保证2次遍历的顺序是一样的。
    类似HashSet基于HashMap的源码实现,LinkedHashSet的数据结构是基于LinkedHashMap。过多的就不说了。

    TreeSet:
    TreeSet即是一组有次序的集合,如果没有指定排序规则Comparator,则会按照自然排序。(自然排序即e1.compareTo(e2) == 0作为比较)
    注意:TreeSet内的元素必须实现Comparable接口。
    TreeSet源码的算法即基于TreeMap,具体算法在说明TreeMap的时候进行解释。

    总结:

    Set实现 使用场景 数据结构
    HashSet 无序的、无重复的数据集合 基于HashMap
    LinkedSet 维护次序的HashSet 基于LinkedHashMap
    TreeSet 保持元素大小次序的集合,元素需要实现Comparable接口 基于TreeMap

    4.HashMap、LinkedHashMap、TreeMap和WeakHashMap
    HashMap就是最基础最常用的一种Map,它无序,以散列表的方式进行存储。之前提到过,HashSet就是基于HashMap,只使用了HashMap的key作为单个元素存储。
    HashMap的访问方式就是继承于Map的最基础的3种方式,详细见上。在这里我具体分析一下HashMap的底层数据结构的实现。

    在看HashMap源码前,先理解一下他的存储方式-散列表(哈希表)。像之前提到过的用数组存储,用链表存储。哈希表是使用数组和链表的组合的方式进行存储。(具体哈希表的概念自行搜索)如下图就是HashMap采用的存储方法。

    Map实现 使用场景 数据结构
    HashMap 哈希表存储键值对,key不重复,无序 哈希散列表
    LinkedHashMap 是一个可以记录插入顺序和访问顺序的HashMap 存储方式是哈希散列表,但是维护了头尾指针用来记录顺序
    TreeMap 具有元素排序功能 红黑树
    WeakHashMap 弱键映射,映射之外无引用的键,可以被垃圾回收 哈希散列表

    详细:http://www.jianshu.com/p/047e33fdefd2

    相关文章

      网友评论

          本文标题:数据结构(集合)

          本文链接:https://www.haomeiwen.com/subject/eudqottx.html