首页 > 代码库 > 关于集合框架的基本的介绍(JDK7)
关于集合框架的基本的介绍(JDK7)
集合框架中的接口以及继承关系
关于集合框架中的接口，注意下面列出的全都是接口：
![clip_image001[7]](/d/file/p/2024/07/27/f84c8cc99f7d4efc88c7ff4c92cd6a79.png "clip_image001[7]")
接口与具体的实现类蓝色表示接口橙色表示具体实现类（仅仅列出比较常用的一些）：
![clip_image001[9]](/d/file/p/2024/07/27/5fcd8136fc2aca667a8d929624246d51.png "clip_image001[9]")
这个图是一个具体的集合框架的接口以及实现类的图，可以和上面的全部接口相对应：
因为collection有很多的子类，为了操作方便，并没有哪个类直接实现了collecion接口，而是直接对collection接口进行继承，仅仅是提供了更加具体的子接口。
关于List
ArrayList的基本使用：
package com.javase.collection;import java.util.ArrayList;import java.util.LinkedList;public class testList { public static void main(String[] args) { //最好是通过泛型的方式来使用 负责取出元素的时候还需要进行强制类型转化 ArrayList<String> list=new ArrayList<String>(); //通过append的方式进行追加 list.add("abc"); list.add("def"); list.add("ghi"); list.add("jkl"); //获得固定下标的元素 String a=list.get(0); int s=list.size(); System.out.println("the size is "+s); for(int i=0;i<s;i++) { System.out.println(list.get(i)); } //判断某个元素的索引 System.out.println("the index of abc is "+ list.indexOf("def")); //删除固定索引的元素 list.remove(0); System.out.println("after the remove option the first element is "+ list.get(0)); //转化为一个数组 //这里要是写成 String [] str=(String [])list.toArray();在执行的时候就会抛出异常 //只能在使用的时候 先取出一个个 Object对象 再进行强制转化 //因为仅仅是String Integer等等这些类型继承了Object 而String[] Integer[]并没有继承Object[] //因此这里只能使用Object[]来进行强制类型转化 使用别的就会报错 Object [] str=(Object [])list.toArray(); System.out.println("--------------------"); for(int i=0;i<str.length;i++) { System.out.println(str[i]); } LinkedList linklist=new LinkedList(); //直接可以将其他的集合类型作为参数传入 生成一个ArrayList ArrayList list3=new ArrayList(linklist); //clear清除全部内容 list.clear(); System.out.println("after clear option the size is "+list.size()); }}输出结果：the size is 4abcdefghijklthe index of abc is 1after the remove option the first element is def--------------------defghijklafter clear option the size is 0
关于ArrayList源码的简要分析：
类的声明的结构如下
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
注意看整个ArrayList类声明的时候就是通过泛型的方式来进行的
一共有三个构造方法：
第一个是通过声明一个capacity
可以看到在构造函数中 关键的部分是：
this.elementData = http://www.mamicode.com/new Object[initialCapacity];
其中elementData是个Object类型的数组 初始的时候，实际ArrayList的底层是通过这个Object类型的数组来维护的。
第二个是没有参数的形式
public ArrayList() {
this(10);
}
可以看到这段，要是不指定capacity的话，ArrayList底层默认生成一个capacity为10的数组。
第三个是通过传入另外一个集合框架 将其中的内容转化成为一个ArrayList
比如可以生成一个LinkedList 对象 将其作为形参传入 生成ArrayList
关于add方法
注意添加新元素之前要对集合的siz+1进行检测，保证当前底层的Object数组的空间是足够的，这一步通过ensureCapacityInternal(size + 1);这个函数来进行，够的话就直接放入，size增加1，要是不够的话会通过调整newCapacity来继续进行，调整之后将原来的元素拷贝到一个新的Object数组中，数组空间大小为newCapacity(通过Arrays.copyof来进行):
elementData = http://www.mamicode.com/Arrays.copyOf(elementData, newCapacity);
还可以添加参数，将元素插入到指定的位置，但这种方式需要将插入位置后面的部分都进行移动，代价比较高通过这个函数来进行：
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
函数原型声明：（void java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)）
关于remove方法
这个其实与上面在固定位置插入元素的操作很相似，只不过拷贝的方式是向前进行的。
由于ArrayList的底层就是一个Object数组，因此在固定位置上的插入和删除操作代价都是比较高的。
关于LinkedList
这个也算是数据结构中最基本的了，就是链表的结构，根据链表自身的结构特性，比起ArrayList又有一些特殊的方法，比如头插addFirst 尾插 addLast。
当然LinkedList底层肯定维护的是一个链表，不想ArrayList那样维护一个数组，这个是结点Node 的部分，是一个用泛型来实现的静态内部类，内容就是我们通常意义上的具体元素值，前驱指针，后继指针：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
具体的插入删除操作都与通常数据结构书中介绍的内容类似。
还是那些老生常谈的问题，再注意一下，也就是线性表和链表的区别，插入删除操作的时候用LinkedList比较快，指定位置检索元素的时候用ArrayList比较快。
关于Set的机制
Hashcode与equals方法的补充说明
首先要再对hashcode 以及equal方法再进一步进行说明，之前的一些说明可以参（http://www.cnblogs.com/Goden/p/3990985.html）。
进一步补充：
hashcode的一般要求:
1、 一致性，同一个对象的hashcode方法被多次调用之后应当返回一样的值（前提是该对象的内容没有发生变化）
2、 两个对象a,b,如果a.equals(b)返回的是true,则对象a和b的hashcode值要是相同的。
3、 两个对象 a,b 如果a.equals(b)返回的是false,则对象 a 和 b 的hashcode不要求一定相同，即使说在hashcode相同的时候，a.equals(b)不一定是true,也可以是false。
对于Object类，其hashcode表示的是对象的地址，因此不同Object实例，其对象是不同的。
一般一个自定义的类的equal方法重写之后，对应的hashcode方法也需要进行重写，这是为了保证通过equal比较相等的对象有相同的hashcode。
当使用HashSet的时候，若是增加一个元素，则会判断已经存在集合中的所有元素的hashcode的值是否与增加的这个元素的hashcode的值是一致的。如果不一致，则将这个元素加进去。如果与某个对象一致（hashcode一样），按照前面的描述，这个时候equals方法还有可能返回的是false于是再进行equals方法的调用，若和这个对象进行比较，若equals返回为true，说明这个元素已经加入集合，就不再进行添加了。若equals返回为 false，说明这个元素还没有加入到集合中（就是那种hashcode相同而equals不相同的情况）Hashcode相同而equals不同的例子可能不太好想到，比如下面这个：
package com.testcollection;import java.util.HashSet;class People{ String name; public People(String name){ this.name=name; }}public class testHashcode { public static void main(String[] args) { HashSet<People> set=new HashSet<People>(); //这两次添加就成功了 因为按照object类的hashcode和equal方法 这个是两个不同的 //但实际上里面的内容是相同的 set.add(new People("abc")); set.add(new People("abc")); //像这种情况 虽然两个类的hashcode并不相同 但是实际上他们的内容是一样的 //属性的情况比较复杂的话 就不能满足需求了 //这种情况下 Object类中的hashcode与equals方法就不能满足实际的需要了 需要重写 System.out.println(set); People p1=new People("def"); System.out.println(set.add(p1)); //这个添加就失败了 System.out.println(set.add(p1)); }}/*打印结果[com.testcollection.People@55fe910c, com.testcollection.People@3be4d6ef]truefalse*/
实际情况下，应当对Person中的hashcode和equals方法进行重写，hashcode就直接用属性的hashcode，而equals方法则参照Object类中的equals方法来实现具体可以参考（http://www.cnblogs.com/Goden/p/3990985.html）
下面就是重写的例子：
package com.test.collection;import java.util.HashSet;public class testHashcode { public static void main(String[] args) { HashSet<People> set=new HashSet<People>(); System.out.println(set.add(new People("abc"))); //由于重写了people类的hashcode 以及equals方法 第二次插入就会返回false 插入失败 System.out.println(set.add(new People("abc"))); }}class People { String name; public People(String name) { this.name = name; } public int hashCode() { return this.name.hashCode(); } public boolean equals(Object obj) { boolean b = false; if (this == obj) { b = true; } if (null != obj && obj instanceof People) { People p = (People) obj; if (name.equals(p.name)) { b = true; } else { b = false; } } return b; }}
实际开发中对于hashcode以及equals方法的重写通常是需要通过一一比较类中的内容，这样进行下去。由于实际情况中这个用的还是比较普遍，通常直接在编译器的source->generate equals and hashcode的操作这样就能继续往下进行。
迭代器
各个集合的实现都有一个iterator()方法，这个方法主要是用来返回一个迭代器。
迭代器的最顶层就是一个用泛型来实现的public interface Iterator<E>接口，方法也比较简单，主要有三个：hasNext Next 以及remove。
hasNext表示集合中是否还有更多的元素，如果集合中还有更多元素的话，这个结果就返回true，要是没有更多元素的话，就返回false
Next 表示返回下一个元素，注意每次调用了Next之后，要执行两个操作：返回下一个元素，以及往后跳动一个位置。ｒemove 这个是用于安全地删除集合中的元素，具体的集合的实现类一般都对这个方法进行了不同的实现。
通常用到的是前两个方法。
下面是一个简要的逻辑图，便于理解next以及hasnext，注意初始的时候:
![clip_image001[11]](/d/file/p/2024/07/27/f3e2737d27c454d34449448b38b0f61c.png "clip_image001[11]")
由于每个集合框架都对这个Iterator接口有具体的实现，实际中也要是通过iterator函数返回一个iterator迭代器，之后通过这个迭代器来遍历集合当中的每个元素，这样一次可以返回一个元素，通常使用一个循环来遍历集合中的每个元素，格式比较固定，主要是三步：调用iterator方法得到迭代函数，建立hasNext()循环迭代，只要返回值为true就继续进行，在循环内部通过next方法得到下一个的元素（指针会同时后移）。
下面是一个基本的例子，对应的写法要掌握：
package com.test.collection;import java.util.HashSet;import java.util.Iterator;public class testIterator { public static void main(String[] args) { HashSet<Integer> set=new HashSet<Integer>(); for(int i=0;i<=10;i++){ set.add(i); } //通过迭代的方式遍历集合 打印出集合中全部元素 for(Iterator<Integer> iter=set.iterator();iter.hasNext();){ System.out.println(iter.next()); } }}
关于HashSet与TreeSort
通过名称也比较好理解，HashSet就是最直接的Set的机制，最后输出的话，输出元素的顺序是凌乱的而且每次输出的时候都不一样，TreeSet就是集合+排序，里面的元素在每次添加的时候都是自动排好序的，TreeSet实现了SortedSet的接口，里面元素的顺序是有序的，输出的时候就是按序输出的。注意定义TreeSet的时候，如果里面的元素是非原始的数据类型，一定要传入一个自定义的比较器，要不然就没法往TreeSet中放元素，一定要先通过TreeSet来指定好元素的比较顺序。
package com.test.collection;import java.util.HashSet;import java.util.Iterator;import java.util.TreeSet;public class testIterator { public static void main(String[] args) { HashSet<Integer> set=new HashSet<Integer>(); TreeSet<Integer> treeset=new TreeSet<Integer>(); for(int i=100;i>=1;i--){ set.add(i); treeset.add(i); } //通过迭代的方式遍历集合 打印出集合中全部元素 这个输出就是无序的 for(Iterator<Integer> iter=set.iterator();iter.hasNext();){ System.out.println(iter.next()); } //放到TreeSet里面的输出就是有序的 默认是从小到大的 for(Iterator<Integer> siter=treeset.iterator();siter.hasNext();){ System.out.println(siter.next()); } }}
关于Comparator接口
由于TreeSet实现了SortedSet接口，每次新加入进来的元素都是有序存放的，这里就涉及到了排序的问题。
就像C++的sort的实现一样，如果是自定义的排序问题的话，特别是对于结构话的数据进行比较，需要引入一个Comparator接口，在声明集合的时候将比较器传入。这个接口中有一个compare方法，自定义的比较器实现了这个接口之后再传入TreeSort中就可以按照自定义的模式进行比较了。
注意compare方法的返回类型是int类型，按照自定义的比较方式，如果：
第一个参数小于第二个参数 返回一个负数
第一个参数等于第二个参数 返回0
第一个参数大于第二个参数 返回一个正数
下面是一个基本的在定义TreeSet集合的时候使用自定义Comparator构造器的例子：
package com.test.tempTest;import java.util.Comparator;import java.util.Iterator;import java.util.TreeSet;class Person { int id; String name; public Person(int id, String name) { super(); this.id = id; this.name = name; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + id; 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; Person other = (Person) obj; if (id != other.id) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; }}class Mycompare implements Comparator<Person> { // sorted by name increasing public int compare(Person p1, Person p2) { int result = p1.getName().compareTo(p2.getName()); if (result == 0) { result = p1.getId() - p2.getId(); } return result; }}public class testbasicComparator { public static void main(String[] args) { // 声明的时候可以传入一个实现了comparator接口的类作为自定义比较器 TreeSet<Person> treeset = new TreeSet<Person>(new Mycompare()); treeset.add(new Person(1, "dfe")); treeset.add(new Person(2, "efd")); treeset.add(new Person(3, "abc")); treeset.add(new Person(4, "dfe")); // 通过迭代器输出 for (Iterator<Person> iter = treeset.iterator(); iter.hasNext();) { Person p = iter.next(); System.out.println("the name is: " + p.getName() + " the id is " + p.getId()); } }}/*输出结果如下，可以看出来结果符合Comparator中定义的顺序：the name is: abc the id is 3the name is: dfe the id is 1the name is: dfe the id is 4the name is: efd the id is 2*/
关于Collections类
Arrays类是数组方法的工具类，里面提供的许多对于数组操作的静态方法。类似地Collections是一个集合的工具类，里面提供了许多对于集合的操作的静态方法，操纵的目标是集合对象，为集合对象提供辅助的方法，比如最基本的sort方法可以提供实现了List接口的集合的排序。
还有一些比较常用到的辅助函数：
比如Collections.shuffle(List<E>list)这个主要功能是将list中元素的顺序弄乱，在快速排序的时候，用这个可以避免最差的那种情况，来提升效率。
还有就是Collections.min(List<E>list)以及Collections.max(List<E>list)用于返回序列中的最大和最小的元素。
整个Comparator就是基于策略模式实现的，下面是一个基于策略模式实现的比较的例子：一个Person类中有id,name,age三个属性，通过泛型来自定义一个比较器，通过策略模式来传入一种sort策略，进行排序。
//首先是一个基本的Person类package com.test.collector;public class Person { int id; int age; String name; public Person(int id, int age, String name) { super(); this.id = id; this.age = age; this.name = name; } public int getId() { return id; } public void setId(int id) { this.id = id; } 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; } //注意重写hashcode以及equals方法 //这里可以通过eclispe来自动生成 @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + age; result = prime * result + id; 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; Person other = (Person) obj; if (age != other.age) return false; if (id != other.id) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } }//Sort接口：package com.test.collector;import java.util.List;public interface Sort { public void sort(List<Person> list);}//Sort接口的两种实现，同时实现了Comparator接口：package com.test.collector;import java.util.Collections;import java.util.Comparator;import java.util.List;//这里同时还要实现comparator接口public class upNameSort implements Sort,Comparator<Person> { public void sort(List<Person> list) { //通过collections工具类的sort方法来进行排序 Collections.sort(list,this); } public int compare(Person p1, Person p2) { int result=p1.getName().compareTo(p2.getName()); //根据id来进行 if(result==0){ result=p1.getId()-p2.getId(); } return result; }}package com.test.collector;import java.util.Collections;import java.util.Comparator;import java.util.List;public class upIdSort implements Sort,Comparator<Person> { public void sort(List<Person> list) { Collections.sort(list, this); } public int compare(Person p1, Person p2) { int result=p1.getId()-p2.getId(); return result; }}//通过这个类来体现策略模式 通过传入的way参数来调用不同的方式进行排序：package com.test.collector;import java.util.List;public class SortWay { private Sort dosort; private int way; public Sort getDosort() { return dosort; } public void setDosort(Sort dosort) { this.dosort = dosort; } public void doSort(List<Person> list, int way) { if (way == 1) { this.dosort = new upIdSort(); dosort.sort(list); } if (way == 2) { this.dosort = new upNameSort(); dosort.sort(list); } }}//Client类 用于进行实际的测试：package com.test.collector;import java.util.ArrayList;import java.util.Iterator;public class Client { public static void main(String[] args) { ArrayList<Person> list = new ArrayList<Person>(); list.add(new Person(4, 23, "abc")); list.add(new Person(2, 24, "cdf")); list.add(new Person(3, 25, "fgr")); list.add(new Person(1, 26, "abc")); SortWay sw = new SortWay(); // 此时是按照id排序 sw.doSort(list, 1); for (Iterator<Person> iter = list.iterator(); iter.hasNext();) { Person p = iter.next(); System.out.println("the name is :" + p.getName() + " the id is :" + p.getId()); } System.out.println("--------------------------"); sw = new SortWay(); // 此时是按照name排序 sw.doSort(list, 2); for (Iterator<Person> iter = list.iterator(); iter.hasNext();) { Person p = iter.next(); System.out.println("the name is :" + p.getName() + " the id is :" + p.getId()); } }}/*输出结果：the name is :abc the id is :1the name is :cdf the id is :2the name is :fgr the id is :3the name is :abc the id is :4--------------------------the name is :abc the id is :1the name is :abc the id is :4the name is :cdf the id is :2the name is :fgr the id is :3上面是按照id进行排序 下面是按照name字典顺序进行的排序*/
关于Map的机制
关于map的基本概念
Map<K,V>数据结构主要用于表示一个key<—>value的键值对，key与value可以是通过泛型来定义的不同的数据类型，他们之间的的关系是一一对应的，一个key映射到一个value值上，但是所有的Key值是不可以重复的，如果add相同的key值，但是value不同的键值对进入map，貌似后插入的一个key-value值会将先前的key-value值覆盖掉，最后只存最后的key-value值。
通常使用的就是HashMap，就像HashSet一样，存入进来的键值对再取出的时候是乱序的。
放入的时候直接map.put(“key”，”value”)取value值的时候通过key值来作为索引取出，比如取出一个String类型的value，String value=http://www.mamicode.com/map.get(“key”)。（注意在map中是使用put而不是使用add）
关于迭代输出的时候通常有两种方法：
1、 通过返回map中所有key的集合（set类型），再依次通过map.get(“key”)取出所有的value的值。
2、 通过返回一个entry结构的集合（Map中的一个内部类，这个类中维护了key value的信息）具体见下面的源码分析
下面是一个Map基本操作的例子：
package com.test.testMap;import java.util.HashMap;import java.util.Iterator;import java.util.Map.Entry;import java.util.Set;public class basicMap { public static void main(String[] args) { HashMap<String, String> map = new HashMap<String, String>(); map.put("a", "aa"); map.put("b", "bb"); map.put("c", "cc"); map.put("d", "aa"); // 加入了key相同的键值对 后加入的一个先加入的一个键值对替代掉 map.put("a", "bb"); // 通过key的集合来迭代 Set<String> set = map.keySet(); for (Iterator<String> iter = set.iterator(); iter.hasNext();) { String key = iter.next(); String value = map.get(key); System.out .println("the key is :" + key + " the value is :" + value); } System.out.println("--------------------"); // 通过第二种方式进行迭代 通过返回一个Entry的集合来进行 Set<Entry<String, String>> entryset = map.entrySet(); for (Iterator<Entry<String, String>> entryiter = entryset.iterator(); entryiter .hasNext();) { Entry<String, String> e = entryiter.next(); String key = e.getKey(); String value = e.getValue(); System.out .println("the key is :" + key + " the value is :" + value); } }}/*输出的结果如下，可以看出来后加进来的关键字相同的(a,bb)键值对代替了最开始输入的的(a,aa)键值对。the key is :d the value is :aathe key is :b the value is :bbthe key is :c the value is :ccthe key is :a the value is :bb------------------------------the key is :d the value is :aathe key is :b the value is :bbthe key is :c the value is :ccthe key is :a the value is :bb*/
关于HashSet以及HashMap的简要源码分析
HashSet的底层是由HashMap来实现的，只是从逻辑上来看的话，就抽象成了一个HashSet,事实上在HashSet的源码中：
属性值中有这个：
private transient HashMap<E,Object> map;
默认的构造函数是这个：
public HashSet() {
map = new HashMap<>();
}
可以看出来Set的本质就是一个Map，只不过这Set中的值就是这个Map中的key值，这个Map中的Value值并没有实际的意义，只是用一个Object来占个位置就好了。逻辑上看成是一个Set类型，实际底层使用Map类型来实现的。当一个元素被放入HashSet中的时候，实际上这个元素是被放入了底层所维护的HashMap的key中，而他们的value值全都是一个Objec对象，并没有什么实际的意义，只起到占位的作用，这个对象在我们对Set进行操作的相关过程中并不会用到。
实际上只要把HashMap分析清楚就相当于把HashSet一起分析了。
先看HashSet中维护了静态类：
static class Entry<K,V> implements Map.Entry<K,V>
这个类里面维护了一个Key Value键值对的信息，以及其他的相关信息（指向下一个Entry结点的指针）。
在类的属性中有一个table表，实际上就是一个Entry的数组:
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE；
其中EMPTY_TABLE初始的时候是一个空的ENTRY数组：
static final Entry<?,?>[] EMPTY_TABLE = {}；
具体的代码没有一句一句来分析，只是把主要的思想记录下来,主要是分析在put一个键值对进入的时候具体都执行了哪些操作：
向HashMap中put一个键值对的时候，
先对空间进行检查，如果之前table是空的，就重新为table数组分配空间，之后通过hash函数进行hash地址的计算（这里用到了比较多的移位的操作），就像通常数据结构中介绍的那样，计算出散列地址，之后进行冲突处理。
这里对于冲突的处理方式是采用链地址法，每次散列到了一个新的地址，就会采用头插法，如果新的键值对与旧的键值对有相同的key值和不同的value值，后面的value值将会把之前的value值替换掉。如果新的键值对与旧的键值对仅仅是hash地址相同但key值是不同的，就是发生的地址冲突的情况，就用头插大将将新的Entry结点插入到当前的位置（最近被调用的再次被调用的几率比较大），当前新的Entry结点的next指针会指向旧的Entry结点。
在这个过程中还要涉及到table数组的重新复制以及扩容（扩容的阈值是通过之前指定的负载因子来控制的）。
其他
可能还有一些框架比如Vector这个基本上被ArrayList代替了，它们实现的功能大致也是相同的，类似地，HashTable也被HashMap代替了，它们也实现的是类似的功能。
关于集合框架的基本的介绍(JDK7)