集合

1.数据结构

1.1 数据结构之栈先进后出

       进栈:数据进入栈模型的过程

           出栈:数据离开栈模型的过程

1.2 数据结构之队列先进先出

入队列:数据从后端进入队列模型的过程

出队列:数据从前端离开队列模型的过程

1.3 数据结构之数组查询快,增删慢

查询时,通过索引定位,查询效率高

删除数据时,要将原始数据删除,同时将后面的数据前移,效率低

增加数据时,要将添加位置后的每个数据后移再添加,效率低

1.4数据结构之链表-增删快、查询慢

1.5数据结构之哈希表

底层采用数组+数组实现,可以说是一个元素为链表的数组。

JDk8以后,底层采用数组+数组+红黑树实现

 

2.集合

集合的体系结构

集合

单列

Collection

List可重复有序

Set不可重复无序

双列Map

HashMap

 

2.1 List集合

2.1.1特点:

有序,存储和取出的元素顺序一致

可重复

2.1.2 List的实现类

ArrayList集合底层是数组结构实现,查询快、增删慢LinkedList集合底层是链表结构实现,查询慢、增删快

2.1.3 List集合的遍历

方法一:Iterator

 Iterator<E> iterator():返回此集合中元素的迭代器,通过集合的iterator()方法得到      

 Iterator<String> it = list.iterator();         

//用while循环改进元素的判断和获取    

   while (it.hasNext()) {          

 String s = it.next();          

 System.out.println(s);      

 }

 

方法二:for循环

for(int i=0;i<list.size();i++){

    String s=list.get(i);

}

方法三:增强for

格式:for(元素类型 变量名:需要遍历的集合){}

例:for(int i:list){}

2.2 set集合

2.2.1 set集合的特点

元素存取无序;

没有索引、只能通过迭代器或增强for循环遍历,不能用for循环遍历;

不能存储重复元素

2.2.2 哈希值

哈希值是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值。

Object类有一个方法可以获取对象的哈希值:hashcode();

Student s=new Student();s.hashcode();

同一个对象多次调用hashcode获取的哈希值相同;

默认情况下,不同对象的哈希值不相同;

 

2.2.3 HashSet

2.2.3.1 HashSet特点

底层数据结构是哈希表

对集合的迭代顺序不作任何保证,也就是说不保证存储和取出的元素顺序一致,没有带索引的方法,所以不能使用普通for循环遍历

由于是Set集合,所以是不包含重复元素的集合

2.2.3.2 HashSet如何保证元素唯一

  添加一个元素的过程:

1)调用对象的hashcode方法获取到对象的哈希值。利用对象的哈希值计算对象的存储位置

2)该位置是否有元素,没有,直接存储

3)有,遍历该位置的所有元素,和新存的元素比较哈希值,都不相同,存储

4)有相同的,调用对象的equals方法,比较对象内容

,不同,存储。相同,不存。

重点注意:

对于我们来讲保证HashSet集合元素的唯一,其实就是根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象,那么保证其唯一,就必须重写hashCode和equals方法建立属于当前对象的比较方式。

2.2.4 LinkedHashSet

集合特点

1)由哈希表和链表实现的Set接口,具有可预测的迭代次序

2)由链表保证元素有序,也就是说元素的存储和取出顺序是一致的

3)由哈希表保证元素唯一,也就是说没有重复的元素

2.2.5 TreeSet

2.2.5.1集合特点

(1)元素唯一

(2)没有索引,不能使用普通for循环遍历

(3)元素有序,不是存储的先后顺序,而是按照一定的规则进行排序。其排序方式取决于构造方法。

TreeSet():根据其元素的自然排序进行排序TreeSet(Comparator comparator) :根据指定的比较器进行排序

重点:

TreeSet如何保证元素唯一:

TreeSet是通过在自定义的类中实现Comparable接口,重写compareTo()方法,实现元素唯一。

而非equals()和hashcode()。Student类中不重写equals和hashCode方法,对于添加的元素是否有重复的最终结果并没有影响!因此TreeSet在比较的时候,根本没有调用equals方法!

2.2.5.2 TreeSet类放入的自定义类

对于TreeSet,假如添加对象的类中不实现Comparable接口重写compareTo方法或者TreesSet创建对象未传入自定义的比较类的话,那么运行时将会报错!

Exception in thread "main" java.lang.ClassCastException: cn.com.clearlight.setframe.set.bean.Student cannot be cast to java.lang.Comparable

————————————————

(方案一)实现Comparable接口,重写compareTo方法

 

public class Student implements Comparable<Student> {

    @Override

    public int compareTo(Student o) {

        // 先根据年龄来排序,若年龄相同,则根据String类型中实现的compareTo方法进行排序

        int temp = this.age - o.age;

        return temp == 0 ? this.name.compareTo(o.name) : temp;

    }

}

(方案二)再写一个学生比较类实现Comparator方法

第一步:新建一个学生比较类,实现Comparator类,并重写compare(T o1, T o2)

第二步:在创建TreeSet对象时,传入(学生比较类)作为参数

新建的ComparatorStudent学生比较类

public class ComparatorStudent implements Comparator<Student> {

 

 

    @Override

    public int compare(Student o1, Student o2) {

          // 先根据名字来排序,若名字相同,则根据年龄的大小来排序

        int temp = o1.getName().compareTo(o2.getName());

        return temp==0 ? o1.getAge()-o2.getAge() : temp;

    }

}

将ComparatorStudent作为Treeset的参数:

TreeSet<Student> ts = new TreeSet<>(new ComparatorStudent ());

 

(方案二也可这样写)

 

 public static void main(String[] args) {      

 //创建集合对象        

TreeSet<Student> ts = new TreeSet<Student>(new Comparator<Student>() {          

 @Override            

public int compare(Student s1, Student s2) {          

      int temp = o1.getName().compareTo(o2.getName());

        return temp==0 ? o1.getAge()-o2.getAge() : temp;

});       

  //创建学生对象        

Student s1 = new Student("xishi", 29);      

  Student s2 = new Student("wangzhaojun", 28);    

    //把学生添加到集合        ts.add(s1);        ts.add(s2);      

}

}

 

3 Map集合

3.1 Map集合概述和特点

格式:

interface Map<K,V>

特点:

键值对映射关系

一个键对应一个值

键不能重复,值可以重复

元素存取无序。

注意:key同样put多次,用最后一次的键值

3.2 Map集合的遍历

     方法一:

 //获取所有键的集合

  Set<String> keySet = map.keySet();        

//遍历键的集合,获取到每一个键。用增强for实现      

 for (String key : keySet) {          

 //根据键去找值

 String value = map.get(key);        

   }

方法二:

//获取所有键值对对象的集合      

 Set<Map.Entry<String, String>> entrySet = map.entrySet();      

  //遍历键值对对象的集合,得到每一个键值对对象      

 for (Map.Entry<String, String> me : entrySet) {            

//根据键值对对象获取键和值            

String key = me.getKey();          

      String value = me.getValue();      

}

 

3 Collections

 

Collections类的作用是针对集合操作的工具类

方法说明:

public static void sort(List list)将指定的列表按升序排序public static void reverse(List<?> list)反转指定列表中元素的顺序

public static void shuffle(List<?> list)使用默认的随机源随机排列指定的列表

 

 

上一篇:TreeSet


下一篇:【Java】HashSet 和 TreeSet