Java复习之集合框架总结

俗话说：温故而知新。想想学过的知识，就算是以前学得很不错，久不用了，就会忘记，所以温习一下以前学习的知识我认为是非常有必要的。而本篇文件温习的是 java基础中的集合框架。

为什么会有集合框架？

平时我们用数组存储一些基本的数据类型，或者是引用数据类型，但是数组的长度是固定的，当添加的元素超过了数组的长度时，需要对数组进行重新的定义，这样就会显得写程序太麻烦，所以java内部为了我们方便，就提供了集合类，能存储任意对象，长度是可以改变的，随着元素的增加而增加，随着元素的减少而减少。

数组可以存储基本数据类型，也可以存储引用数据类型，基本数据类型存储的是值，引用数据类型存储的是地址，而集合只能存储引用数据类型（也就是对象），其实集合中也可以存储基本数据类型，但是在存储的时候会自动装箱变成对象。

有了集合不意味着我们要抛弃数组，如果需要存储的元素个数是固定的，我们可以使用数组，而当存储的元素不固定，我们使用集合。

集合的种类

集合分为单列集合和双列集合。单列集合的根接口为collection,双列结合的根接口为map,两种集合都有基于哈希算法的集合类（hashmap和hashset），现在我们可能会有疑问，到底是双列集合基于单列集合还是单列集合基于双列集合呢，下面我们来看往集合hashmap和hashset添加元素的源码：

/*
*hashmap的put 方法 
*/
 public v put(k key, v value) {
    return putval(hash(key), key, value, false, true);
  }

final v putval(int hash, k key, v value, boolean onlyifabsent,
          boolean evict) {
    node<k,v>[] tab; node<k,v> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
      n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newnode(hash, key, value, null);
    else {
      node<k,v> e; k k;
      if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
      else if (p instanceof treenode)
        e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value);
      else {
        for (int bincount = 0; ; ++bincount) {
          if ((e = p.next) == null) {
            p.next = newnode(hash, key, value, null);
            if (bincount >= treeify_threshold - 1) // -1 for 1st
              treeifybin(tab, hash);
            break;
          }
          if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
          p = e;
        }
      }
      if (e != null) { // existing mapping for key
        v oldvalue = e.value;
        if (!onlyifabsent || oldvalue == null)
          e.value = value;
        afternodeaccess(e);
        return oldvalue;
      }
    }
    ++modcount;
    if (++size > threshold)
      resize();
    afternodeinsertion(evict);
    return null;
  }

/*
* hashset 的add 方法
*/
public boolean add(e e) {
    return map.put(e, present)==null;
  }
// present是一个object 对象
 private static final object present = new object();

由上源码，我们可以看出，双列集合的put方法源码中并没有出现add方法，而单列集合的add源码只能怪出现了put；我们可以知道单列集合是基于双列集合实现的。其实道理很简单，单列集合每次添加元素，只要添加key就可以，而key也是双列集合元素的唯一标识，而其值value则由一个object对象代替并且隐藏，每次加入，输出元素都是隐藏单列结合的这个值， 底层基于双列集合，隐藏一列是很好实现的，而如果是单列集合要变成双列集合估计就会有很大的难度，就好比魔术师变魔术，魔术师变东西前肯定事先准备好要变的东西，只是将其隐藏，但是如果魔术师变魔术是真的从无到有，那我估计他就是神仙了，想要什么就变出来什么便是。

单列集合

首先我们看单列结合的继承图，单列集合的根接口是collection,而list的实现类为arraylist、linkedlist、vector，set接口的实现类是hashset和treeset。

其次我们来看看各个集合的功能

list集合的特有功能概述

    * void add(int index,e element) //集合中添加元素
    * e remove(int index) //删除集合中index位置上的元素
    * e get(int index)  //获取集合中index位置上的元素
    * e set(int index,e element) 将index位置上的元素替换成 element

vector类特有功能

    * public void addelement(e obj)  添加元素
    * public e elementat(int index)  //获取元素
    * public enumeration elements()  //获取元素的枚举（迭代遍历的时候用到）

linkedlist类特有功能

    * public void addfirst(e e)及addlast(e e)  //集合头添加元素或者集合尾添加元素
    * public e getfirst()及getlast() //获取头元素 获取尾元素
    * public e removefirst()及public e removelast() //删除头元素删除尾元素
    * public e get(int index);//获取index元素

根据上述linkedlist的功能，我们可以模拟栈获取队列的数据结构，栈是先进后出，队列为先进先出。

/**
 * 模拟的栈对象
 * @author 毛麒添
 * 底层还是使用linkedlist实现
 * 如果实现队列只需要将出栈变为 removefirst 
 */
public class stack {

  private linkedlist linklist=new linkedlist();
  
  /**
   * 进栈的方法
   * @param obj
   */
  public void in(object obj){
    linklist.addlast(obj);
  }
  
  /**
   * 出栈
   */
  public object out(){
    return linklist.removelast();
  }
  /**
   * 栈是否为空
   * @return
   */
  public boolean isempty(){
    return linklist.isempty();
  }
}


//集合的三种迭代（遍历集合）删除
arraylist<string> list=new arraylist();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("world");
//1，普通for循环删除元素
for(int i=0;i<list,size();i++){//删除元素b
   if("b".equals(list.get(i))){
    list.remove(i--);// i-- 当集合中有重复元素的时候保证要删除的重复元素被删除
 }
}
//2.使用迭代器遍历集合
iterator<string> it=list.iterator();
while(it.hasnext){
  if("b".equals(it.next())){
   it.remove();//这里必须使用迭代器的删除方法，而不能使用集合的删除方法，否则会出现并发修改异常（concurrentmodificationexception）
 }
}

//使用增强for循环来进行删除
for (string str:list){
   if("b".equals(str)){
    list.remove("b");//增强for循环底层依赖的是迭代器，而这里删除使用的依旧是集合的删除方法，同理肯定是会出现并发修改异常（concurrentmodificationexception），所以增强for循环一直能用来遍历集合，不能对集合的元素进行删除。
 }
}

接下里我们看set集合，我们知道set 集合存储无序，无索引，不可以存储重复的对象；我们使用set集合都是需要去掉重复元素的, 如果在存储的时候逐个equals()比较, 效率较低,哈希算法提高了去重复的效率, 降低了使用equals()方法的次数，其中hashset底层基于哈希算法，当hashset调用add方法存储对象，先调用对象的hashcode()方法得到一个哈希值, 然后在集合中查找是否有哈希值相同的对象，如果没有哈希值相同的对象就直接存入集合，如果有哈希值相同的对象, 就和哈希值相同的对象逐个进行equals()比较,比较结果为false就存入, true则不存。下面给出hashset存储自定义对象的一个例子，自定义对象需要重写hashcode()和equals()方法。

/**
 * 自定义对象
 * @author 毛麒添
 * hashset 使用的bean 重写了equals和hashcode方法
 */
public class person1 {
  private string name;
  private int age;
  public person1() {
    super();
    // todo auto-generated constructor stub
  }
  public person1(string name, int age) {
    super();
    this.name = name;
    this.age = age;
  }
  public string getname() {
    return name;
  }
  public void setname(string name) {
    this.name = name;
  }
  public int getage() {
    return age;
  }
  public void setage(int age) {
    this.age = age;
  }
  @override
  public string tostring() {
    return "person1 [name=" + name + ", age=" + age + "]";
  }
  
  //使hashset存储元素唯一
  @override
  public int hashcode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + age;
    result = prime * result + ((name == null) ? 0 : name.hashcode());
    return result;
  }
  @override
  public boolean equals(object obj) {
    system.out.println("equals调用了");
    if (this == obj)
      return true;
    if (obj == null)
      return false;
    if (getclass() != obj.getclass())
      return false;
    person1 other = (person1) obj;
    if (age != other.age)
      return false;
    if (name == null) {
      if (other.name != null)
        return false;
    } else if (!name.equals(other.name))
      return false;
    return true;
  }  
}

public class demo1_hashset {

  public static void main(string[] args) {
    hashset<person1> hs=new hashset<person1>();
    hs.add(new person1("张三", 23));
    hs.add(new person1("张三", 23));
    hs.add(new person1("李四", 24));
    hs.add(new person1("李四", 24));
    hs.add(new person1("李四", 24));
    hs.add(new person1("李四", 24));
    system.out.println(hs);
  }

运行结果如图，达到了不存储重复自定义对象的目的。其实hashset的下面还有一个linkedhashset,底层是链表实现的，是set中唯一一个能保证怎么存就怎么取的集合对象,是hashset的子类，保证元素唯一，与hashset原理一样,这里就不多说了。

最后是treeset集合，该集合是用来进行排序的，同样也可以保证元素的唯一，可以指定一个顺序, 对象存入之后会按照指定的顺序排列。

指定排序有两种实现：

comparable：集合加入自定义对象的时候，自定义对象需要实现comparable接口，

• 实现接口的抽象方法中返回0，则集合中只有一个元素
• 返回正数，则集合中怎么存则怎么取，
• 返回负数，集合倒序存储

comparator（比较器）：

• 创建treeset的时候可以制定 一个comparator
• 如果传入了comparator的子类对象, 那么treeset就会按照比较器中的顺序排序
• add()方法内部会自动调用comparator接口中compare()方法排序
• 调用的对象是compare方法的第一个参数,集合中的对象是compare方法的第二个参数

原理：

• treeset底层二叉排序树
• 返回小的数字存储在树的左边（负数），大的存储在右边（正数），相等则不存（等于0）
• 在treeset集合中如何存取元素取决于compareto（）方法的返回值

下面来看例子：

/**
 * 自定义对象 用于treeset
 * @author 毛麒添
 *
 */
public class person implements comparable<person>{

  private string name;
  private int age;
  
  public person(){
    super();
  }
  public person(string name, int age) {
    super();
    this.name = name;
    this.age = age;
  }
  public string getname() {
    return name;
  }
  public void setname(string name) {
    this.name = name;
  }
  public int getage() {
    return age;
  }
  public void setage(int age) {
    this.age = age;
  }
  @override
  public string tostring() {
    return "person [name=" + name + ", age=" + age + "]";
  }
  
  @override
  public boolean equals(object obj) {
    person p=(person) obj;
    return this.name.equals(p.name)&&this.age==p.age;
  }
  
  @override
  public int hashcode() {
    // todo auto-generated method stub
    return 1;
  }
  
  /*//按照年龄进行排序（treeset）
  @override
  public int compareto(person o) {
    int number=this.age-o.age;//年龄是比较的主要条件
    //当年龄一样的时候比较名字来确定排序
    return number==0?this.name.compareto(o.name):number;
  }*/
  
  //按照姓名进行排序（treeset）
    @override
    public int compareto(person o) {
      int number=this.name.compareto(o.name);//姓名是比较的主要条件
      //当姓名一样的时候比年龄来确定排序
      return number==0?this.age- o.age:number;
    }
    
    //按照姓名长度进行排序（treeset）
        /*@override
        public int compareto(person o) {
          int length=this.name.length()-o.name.length();//姓名长度比较的次要条件
          int number=length==0?this.name.compareto(o.name):length;//姓名是比较的次要条件
          //比年龄也是次要条件
          return number==0?this.age- o.age:number;
        }*/
}

/**
 * 
 * @author 毛麒添
 * treeset集合
 * 集合加入自定义对象的时候，自定义对象需要实现comparable接口，
 * 实现接口的抽象方法中返回0，则集合中只有一个元素
 * 返回正数，则集合中怎么存则怎么取，
 * 返回负数，集合倒序存储
 * 
 * 将字符按照长度来进行排序在treeset中,需要使用有比较的构造方法进行比较。
 */
public class demo_treeset {

  public static void main(string[] args) {
    // todo auto-generated method stub
    demo1();//整数存取排序
    demo2();//自定义对象排序
    
    //将字符按照长度来进行排序在treeset中
    treeset<string> strlenset=new treeset<string>(new comparebylen());
    strlenset.add("aaaaa");
    strlenset.add("lol");
    strlenset.add("wrc");
    strlenset.add("wc");
    strlenset.add("b");
    strlenset.add("wnnnnnnnnnnn");
    
    system.out.println(strlenset);
  }

  private static void demo2() {
    treeset<person> ptreeset=new treeset<person>();
    
    ptreeset.add(new person("李四",12));
    ptreeset.add(new person("李四",16));
    ptreeset.add(new person("李青",16));
    ptreeset.add(new person("王五",19));
    ptreeset.add(new person("赵六",22));
    
    system.out.println(ptreeset);
  }

  private static void demo1() {
    treeset< integer> treeset=new treeset<integer>();
    treeset.add(1);
    treeset.add(1);
    treeset.add(1);
    treeset.add(3);
    treeset.add(3);
    treeset.add(3);
    treeset.add(2);
    treeset.add(2);
    treeset.add(2);
    
    system.out.println(treeset);
  }

}

//treeset 构造器，实现compare对需要存储的字符串进行比较
class comparebylen implements comparator<string>{

  //按照字符串的长度进行比较，该方法的返回值和继承comparable的compareto方法返回值同理。
  @override
  public int compare(string o1, string o2) {
    int num=o1.length()-o2.length();//以长度为主要条件
    return num==0?o1.compareto(o2):num;//内容为次要条件
  }
  
}

下面是运行截图，其中compareto的实现方法对几种条件排序进行了实现，具体可以查看person自定义类中的实现。

单列集合复习就到这里吧。

双列集合

同样的，在复习双列结合之前我们先看看双列集合的继承图。

map集合的功能梳理：

添加功能

• v put(k key,v value):添加元素。
• 如果键是第一次存储，就直接存储元素，返回null
• 如果键不是第一次存在，就用值把以前的值替换掉，返回以前的值

删除功能

• void clear():移除所有的键值对元素
• v remove(object key)：根据键删除键值对元素，并把值返回

判断功能

• boolean containskey(object key)：判断集合是否包含指定的键
• boolean containsvalue(object value):判断集合是否包含指定的值
• boolean isempty()：判断集合是否为空

获取功能

• set<map.entry<k,v>> entryset():
• v get(object key):根据键获取值
• set<k> keyset():获取集合中所有键的集合
• collection<v> values():获取集合中所有值的集合

长度功能

• int size()：返回集合中的键值对的个数

map类集合也有三种遍历方式：

• 使用迭代器进行遍历
• 使用增强for循环来进行遍历
• 使用map.entry来遍历集合中的元素

下面我们来看看如何实现上面三种遍历方式

/**
 * 
 * @author 毛麒添
 * map 集合的遍历
 */
public class demo {

  public static void main(string[] args) {
    map<string ,integer> map=new hashmap<string, integer>();
    map.put("张三", 18);
    map.put("李四", 19);
    map.put("王五", 20);
    map.put("赵六", 21);
    
    //使用迭代器进行遍历
    /*set<string> keyset = map.keyset();//获取所有key的集合
    iterator<string> iterator = keyset.iterator();
    while(iterator.hasnext()){
      string key = iterator.next();
      integer i=map.get(key);
      system.out.println(i);
    }*/
    //使用增强for循环来进行遍历
    for (string key :map.keyset()) {
      integer integer = map.get(key);
      system.out.println(integer);
    }
/*---------------------------使用map.entry来遍历集合中的元素--------------------------*/
    set<map.entry<string,integer>> en=map.entryset();////获取所有的键值对象的集合
    /*//使用迭代器来遍历
    iterator<entry<string, integer>> iterator = en.iterator();
    while(iterator.hasnext()){
      entry<string, integer> e=iterator.next();//获取键值对对象
      string key = e.getkey();//根据键值对对象获取键
      integer value = e.getvalue();//根据键值对对象获取值
      system.out.print(key);
      system.out.println(value);
    }*/
    //使用增强for循环来遍历
    for (entry<string, integer> entry : en) {
      string key = entry.getkey();
      integer value = entry.getvalue();
      system.out.print(key);
      system.out.println(value);
    }
/*---------------------------使用map.entry来遍历集合中的元素--------------------------*/
  }
}

linkhashmap与linkhashset一样，怎么存怎么取，保证元素唯一（key 是唯一判定值）,由于保证元素唯一，其性能肯定会低一些，这里就不细说了。

treemap是双列集合，其实他和treeset是很像的，但是双列集合的键是唯一标识，所以treemap排序的是每个元素的键。对于存储自定义对象排序，它也有comparable和comparator，下面我们来看例子

/**
 * 
 * @author 毛麒添
 * treemap
 * 通treeset 原理，存取自定义对象也需要继承comparable结构，
 * 或者实现比较器comparator
 */
public class demo6_treemap {

  public static void main(string[] args) {
    treemap<student, string> tm=new treemap<student, string>(new comparator<student>() {

      @override
      public int compare(student s1, student s2) {
        int num=s1.getname().compareto(s2.getname());//以姓名作为主要比较条件
        return num==0?s1.getage()-s2.getage():num;
      }
    });
    tm.put(new student("张三",13),"杭州");
    tm.put(new student("张三",14), "贺州");
    tm.put(new student("王五",15), "广州");
    tm.put(new student("赵六",16), "深圳");
    
    system.out.println(tm);
  }

}

/**
 * 自定义对象
 * @author 毛麒添
 * hashmap 存储对象 与 hashset 同理 需要重写 hashcode 和equals 方法 
 * treemap 实现 comparable接口
 */
public class student implements comparable<student>{

  private int age;
  private string name;
  
  public student(){
    super();
  }
  public student(string name,int age){
    this.name=name;
    this.age=age;
  }
  public int getage() {
    return age;
  }
  public void setage(int age) {
    this.age = age;
  }
  public string getname() {
    return name;
  }
  public void setname(string name) {
    this.name = name;
  }
  
  
  @override
  public string tostring() {
    return "student [age=" + age + ", name=" + name + "]";
  }
  @override
  public int hashcode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + age;
    result = prime * result + ((name == null) ? 0 : name.hashcode());
    return result;
  }
  @override
  public boolean equals(object obj) {
    if (this == obj)
      return true;
    if (obj == null)
      return false;
    if (getclass() != obj.getclass())
      return false;
    student other = (student) obj;
    if (age != other.age)
      return false;
    if (name == null) {
      if (other.name != null)
        return false;
    } else if (!name.equals(other.name))
      return false;
    return true;
  }
  @override
  public int compareto(student o) {
    int num =this.age-o.age;//以年龄为主要条件
    return num==0?this.name.compareto(o.name):num;//姓名作为次要条件
  }  
}

到这里，java集合框架的复习基本完成，最后来一个斗地主的例子对集合框架做一个综合应用，只是实现斗地主洗牌和发牌，至于怎么打牌，逻辑复杂，这里不做实现。

/**
 * 
 * @author 毛麒添
 * 模拟斗地主洗牌和发牌，牌排序
 * 买一副扑克
 * 洗牌
 * 发牌
 * 看牌
 */
public class doudizhu_progress {

  public static void main(string[] args) {
    // todo auto-generated method stub
    //构造一副扑克牌
    string[] number={"3","4","5","6","7","8","9","10","j","q","k","a","2"};
    string[]color={"黑桃","红桃","梅花","方块"};
    hashmap<integer, string> pokermap=new hashmap<integer, string>();//存放牌的map
    arraylist<integer> list=new arraylist<integer>();//存放牌的索引
    int index=0; //索引
    for (string s1 : number) {
      for (string s2 : color) {
        pokermap.put(index,s2.concat(s1));
        list.add(index);
        index++;
      
      }
    }
    //加入大小王
    pokermap.put(index,"小王");
    list.add(index);
    index++;
    pokermap.put(index,"大王");
    list.add(index);
    
    //洗牌
    collections.shuffle(list);
    //system.out.println(list);
    
    //发牌，3个人玩 加上底牌3张 使用treeset 来存放索引，并自动对索引排好序
    treeset<integer> mao=new treeset<integer>();
    treeset<integer> li=new treeset<integer>();
    treeset<integer> huang=new treeset<integer>();
    treeset<integer> dipai=new treeset<integer>();
    
    for(int i=0;i<list.size();i++){
      if(i>=list.size()-3){//最后三张牌，作为底牌
        dipai.add(list.get(i)); 
      }else if(i%3==0){
        mao.add(list.get(i));
      }else if(i%3==1){
        li.add(list.get(i));
      }else {
        huang.add(list.get(i));
      }
    }
    
    //看牌
    lookpoker(pokermap,mao,"mao");
    lookpoker(pokermap,li,"li");
    lookpoker(pokermap,huang,"huang");
    lookpoker(pokermap,dipai,"底牌");
  }

  /**
   * 看牌的方法
   * @param pokermap 存放牌的map
   * @param mao 该玩家的牌的索引集合
   * @param name 玩家名字
   */
  private static void lookpoker(hashmap<integer, string> pokermap,
      treeset<integer> mao, string name) {
    if(name.equals("底牌")){
      system.out.print("地主"+name+"的牌是：");
    }else{
      system.out.print("玩家"+name+"的牌是：");
    }
    for (integer integer : mao) {
      system.out.print(pokermap.get(integer)+" ");
    }
    
    system.out.println();
    
  }

}

运行截图：

写在最后：

如果你看到这里，估计你也温故知新了吧，那就这样吧，这篇又臭又长的文章就到这里啦。希望对大家的学习有所帮助，也希望大家多多支持。