数据结构(集合)

集合框架
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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,214评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,307评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,543评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,221评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,224评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,007评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,313评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,956评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,441评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,925评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,018评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,685评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,234评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,240评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,464评论 1 261
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,467评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,762评论 2 345

推荐阅读更多精彩内容