集合框架

发布于 2020-03-29  113 次阅读


java集合框架

  • 从物理角度只有两种数据结构
  1. 连续存储
  2. 链式存储
  • 从逻辑角度有很多种数据结构
  1. 顺序存储
  2. 链式存储
  3. map
  4. 红黑树
  • 集合框架被设计成要满足以下几个目标。
  • 该框架必须是高性能的。基本集合(动态数组,链表,树,哈希表)的实现也必须是高效的。
  • 该框架允许不同类型的集合,以类似的方式工作,具有高度的互操作性。
  • 对一个集合的扩展和适应必须是简单的。

为此,整个集合框架就围绕一组标准接口而设计。你可以直接使用这些接口的标准实现,诸如: LinkedList, HashSet, 和 TreeSet 等,除此之外你也可以通过这些接口实现自己的集合。

以下内容,参考来自这位大佬跳转

Collection

Collection 是最基本的集合接口

List

List接口是一个有序的 Collection
使用此接口能够精确的控制每个元素插入的位置,能够通过索引(元素在List中位置,类似于数组的下标)来访问List中的元素
第一个元素的索引为 0,而且允许有相同的元素。
List 接口存储一组不唯一,有序(插入顺序)的对象。

List接口又有两个常用的实现类ArrayList和LinkedList


  • ArrayList

ArrayList -> List接口 -> Collection接口
ArrayList 底层就是数组

ArrayList数组线性表的特点为:类似数组的形式进行存储,因此它的随机访问速度极快。    
ArrayList数组线性表的缺点为:不适合于在线性表中间需要频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素。

  1. 如果在初始化ArrayList的时候没有指定初始化长度的话,默认的长度为10
  2. ArrayList在增加新元素的时候如果超过了原始的容量的话,ArrayList扩容ensureCapacity的方案为原始容量*3/2
  3. ArrayList是线程不安全的,在多线程的情况下不要使用

如果一定在多线程使用List的,您可以使用Vector,因为Vector和ArrayList基本一致,区别在于Vector中的绝大部分方法都          使用了同步关键字修饰,这样在多线程的情况下不会出现并发错误哦,还有就是它们的扩容方案不同,ArrayList是通过原始容量*3/2,而Vector是允许设置默认的增长长度,Vector的默认扩容方式为原来的2倍。         切记Vector是ArrayList的多线程的一个替代品

  1. ArrayList实现遍历的几种方法
package com.yonyou.test;
 
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
 
public class Test{
public static void main(String[] args) {
     List<String> list=new ArrayList<String>();
     list.add("Hello");
     list.add("World");
     list.add("HAHAHAHA");
     //第一种遍历方法使用foreach遍历List
     for (String str : list) {
        System.out.println(str);
    }
 
     //第二种遍历,把链表变为数组相关的内容进行遍历
    String[] strArray=new String[list.size()];
    list.toArray(strArray);
    for(int i= 0;i<strArray.length;i++) 
    //这里也可以改写为foreach(String str:strArray)这种形式
    {
        System.out.println(strArray[i]);
    }
     
    //第三种遍历 使用迭代器进行相关遍历
     
     Iterator<String> ite=list.iterator();
     while(ite.hasNext())
     {
         System.out.println(ite.next());
     }
 }
}

  • LinkedList

LinkedList -> List接口 -> Collection接口
LinkedListt 底层是双向链表

LinkedList的链式线性表的特点为: 适合于在链表中间需要频繁进行插入和删除操作。     
LinkedList的链式线性表的缺点为: 随机访问速度较慢。查找一个元素需要从头开始一个一个的找。

  1. LinkedList的内部实现
  • LinkedList的内部是基于双向循环链表的结构来实现的。在LinkedList中有一个类似于c语言中结构体的Entry内部类。在Entry的内部类中包含了前一个元素的地址引用和后一个元素的地址引用类似于c语言中指针。    
  1. LinkedList不是线程安全的
  • 注意LinkedList和ArrayList一样也不是线程安全的,如果在对线程下面访问可以自己重写LinkedLis
  • ,然后在需要同步的方法上面加上同步关键字synchronized    
  1. d.LinkedList的遍历方法
package com.yonyou.test;
 
import java.util.LinkedList;
import java.util.List;

public class Test{
public static void main(String[] args) {
     
    List<String> list=new LinkedList<String>();
    list.add("Hello");
    list.add("World");
    //LinkedList遍历的第一种方式使用数组的方式
    String[] strArray=new String[list.size()];
    list.toArray(strArray);
    for(String str:strArray)
    {
        System.out.println(str);
    }
    //LinkedList遍历的第二种方式
    for(String str:list)
    {
        System.out.println(str);   
    }
    //LinkedList遍历的第三种方式(迭代器)
    Iterator<String> ite = list.iterator();
    while (ite.hasNext()) {
        System.out.println(ite.next());
    }
  }
}
  1. LinkedList可以被当做堆栈来使用
  • 由于LinkedList实现了接口Dueue(双向队列接口),所以LinkedList可以被当做堆栈来使用

Set

Set 具有与 Collection 完全一样的接口,只是行为上不同
Set 不保存重复的元素。Set 接口存储一组唯一,无序的对象

Set接口区别于List接口的特点在于:   Set中的元素实现了不重复,有点象集合的概念,无序,不允许有重复的元素,最多允许有一个null元素对象
需要注意的是:虽然Set中元素没有顺序,但是元素在set中的位置是有由该元素的HashCode决定的,其具体位置其实是固定的。

  • 此外需要说明一点,在set接口中的不重复是由特殊要求的。    举一个例子:对象A和对象B,本来是不同的两个对象,正常情况下它们是能够放入到Set里面的,但是    如果对象A和B的都重写了hashcode和equals方法,并且重写后的hashcode和equals方法是相同的话。那么A和B是不能同时放入到    Set集合中去的,也就是Set集合中的去重和hashcode与equals方法直接相关

HashSet

HashSet的底层就是基于HashMap来实现的
在HashMap中的key是不允许重复的,你换个角度看看,那不就是说Set集合吗?   这里唯一一个需要处理的就是那个Map的value弄成一个固定值即可

  • HashSet使用和理解中容易出现的误区:
  1. HashSet中存放null值
    HashSet中时允许出入null值的,但是在HashSet中仅仅能够存入一个null值
  2. HashSet中存储元素的位置是固定的
    HashSet中存储的元素的是无序的,但是由于HashSet底层是基于Hash算法实现的,使用了hashcode,所以HashSet中相应的元素的位置是固定的
  3. 遍历HashSet的几种方法
    这里先不写了,和上面给的方法类似

TreeSet

TreeSet是一种排序二叉树。存入Set集合中的值,会按照值的大小进行相关的排序操作。底层算法是基于红黑树来实现的。
TreeSet和HashSet的主要区别在于TreeSet中的元素会按照相关的值进行排序

  • TreeSet和HashSet的区别和联系
  1. HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key
  2. Map的key和Set都有一个共同的特性就是集合的唯一性.TreeMap更是多了一个排序的功能.
  3. hashCode和equal()是HashMap用的, 因为无需排序所以只需要关注定位和唯一性即可.
    • hashCode是用来计算hash值的,hash值是用来确定hash表索引的.
    • hash表中的一个索引处存放的是一张链表, 所以还要通过equal方法循环比较链上的每一个对象才可以真正定位到键值对应的Entry.
    • put时,如果hash表中没定位到,就在链表前加一个Entry,如果定位到了,则更换Entry中的value,并返回旧value
  4. 由于TreeMap需要排序,所以需要一个Comparator为键值进行大小比较.当然也是用Comparator定位的.
    • Comparator可以在创建TreeMap时指定
    • 如果创建时没有确定,那么就会使用key.compareTo()方法,这就要求key必须实现Comparable接口.
    • TreeMap是使用Tree数据结构实现的,所以使用compare接口就可以完成定位了.

下面是一个使用TreeSet的实例

package com.yonyou.test;
 
import java.util.Iterator;
import java.util.TreeSet;

public class Test{
    public static void main(String[] args) {
        //String实体类中实现Comparable接口,所以在初始化TreeSet的时候,
        //无需传入比较器
        TreeSet<String> treeSet=new TreeSet<String>();
        treeSet.add("d");
        treeSet.add("c");
        treeSet.add("b");
        treeSet.add("a");
        Iterator<String> iterator=treeSet.iterator();
        while(iterator.hasNext())
        {
            System.out.println(iterator.next());
        }
     }
}

Map

Map中的每个成员方法由一个关键字(key)和一个值(value)构成。
Map包装的是一组成对的“键-值”对象的集合,而且在Map接口的集合中也不能有重复的key出现,因为每个键只能与一个成员元素相对应。
Map接口不直接继承于Collection接口(需要注意)

HashMap

HashMap实现了Map、CloneMap、Serializable三个接口,并且继承自AbstractMap类。
HashMap基于hash数组实现,若key的hash值相同则使用链表方式进行保存。

  • 新建一个HashMap时,默认的话会初始化一个大小为16,负载因子为0.75的空的HashMap
  • HashMap中还存在一个内部类Entry,用于链表的存储

Entry是一个结点,它持有下一个元素的引用,这样就构成了一个链表

import java.util.*;

public class Test{
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>();
        map.put("1", "value1");
        map.put("2", "value2");
        map.put("3", "value3");

        //第一种:普遍使用,二次取值
        System.out.println("通过Map.keySet遍历key和value:");
        for (String key : map.keySet()) {
            System.out.println("key= "+ key + " and value= " + map.get(key));
        }

        //第二种
        System.out.println("通过Map.entrySet使用iterator遍历key和value:");
        Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, String> entry = it.next();
            System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
        }

        //第三种:推荐,尤其是容量大时
        System.out.println("通过Map.entrySet遍历key和value");
        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
        }

        //第四种
        System.out.println("通过Map.values()遍历所有的value,但不能遍历key");
        for (String v : map.values()) {
            System.out.println("value= " + v);
        }
    }
}

好久没有弄,暂时就这些了

2019-08-27修改


遥望漉雪千山都过尽,隔海隔山你的背影。