java 集合_Java集合详解

SortedSet

TreeSet

HashSet 的后台有一个HashMap;初始化后台容量；只不过生成一个HashSet的话，系统只提供key的访问； 如果有两个Key重复，那么会覆盖之前的；

实现类 :

HashSet：equals返回true，hashCode返回相同的整数；哈希表；存储的数据是无序的。

LinkedHashSet：此实现与HashSet的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。存储的数据是有序的。

HashSet类

HashSet类直接实现了Set接口，其底层其实是包装了一个HashMap去实现的。HashSet采用HashCode算法来存取集合中的元素，因此具有比较好的读取和查找性能。

HashSet的特征:

不仅不能保证元素插入的顺序，而且在元素在以后的顺序中也可能变化(这是由HashSet按HashCode存储对象(元素)决定的，对象变化则可能导致HashCode变化)

HashSet是线程非安全的

HashSet元素值可以为NULL

HashSet常用方法:

public boolean contains(Object o) ：如果set包含指定元素，返回true

public Iterator iterator()返回set中元素的迭代器

public Object[] toArray() ：返回包含set中所有元素的数组public Object[] toArray(Object[] a) ：返回包含set中所有元素的数组，返回数组的运行时类型是指定数组的运行时类型

public boolean add(Object o) ：如果set中不存在指定元素，则向set加入

public boolean remove(Object o) ：如果set中存在指定元素，则从set中删除

public boolean removeAll(Collection c) ：如果set包含指定集合，则从set中删除指定集合的所有元素

public boolean containsAll(Collection c) ：如果set包含指定集合的所有元素，返回true。如果指定集合也是一个set，只有是当前set的子集时，方法返回true

实现Set接口的HashSet，依靠HashMap来实现的。

我们应该为要存放到散列表的各个对象定义hashCode()和equals()。

HashSet的equals和HashCode：

前面说过，Set集合是不允许重复元素的，否则将会引发各种奇怪的问题。那么HashSet如何判断元素重复呢？

HashSet需要同时通过equals和HashCode来判断两个元素是否相等，具体规则是，如果两个元素通过equals为true，并且两个元素的hashCode相等，则这两个元素相等(即重复)。

所以如果要重写保存在HashSet中的对象的equals方法，也要重写hashCode方法，重写前后hashCode返回的结果相等(即保证保存在同一个位置)。所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。

试想如果重写了equals方法但不重写hashCode方法，即相同equals结果的两个对象将会被HashSet当作两个元素保存起来，这与我们设计HashSet的初衷不符(元素不重复)。

另外如果两个元素哈市Code相等但equals结果不为true，HashSet会将这两个元素保存在同一个位置，并将超过一个的元素以链表方式保存，这将影响HashSet的效率。

如果重写了equals方法但没有重写hashCode方法，则HashSet可能无法正常工作，比如下面的例子。

import java.util.HashSet;

import java.util.Objects;

import java.util.Set;

public class R {

private int count;

public R(int count) {

this.count = count;

}

@Override

public String toString() {

return "R{" + "count=" + count + " # hashCode=" + this.hashCode() + '}';

}

@Override

public boolean equals(Object o) {

if (this == o) return true;

if (o == null || getClass() != o.getClass()) return false;

R r = (R) o;

return count == r.count;

}

// @Override

// public int hashCode() {

// return Objects.hash(count);

// }

public static void main(String[] args) {

Set set = new HashSet();

set.add(new R(5));

set.add(new R(-3));

set.add(new R(9));

set.add(new R(-2));

System.out.println(set.contains(new R(-3)));

System.out.println(set);

}

}

上面注释了hashCode方法，所以你将会看到下面的结果。

false

[R{count=9 # hashCode=2003749087}, R{count=5 # hashCode=1283928880}, R{count=-3 # hashCode=295530567}, R{count=-2 # hashCode=1324119927}]

取消注释，则结果就正确了

true

[R{count=5 # hashCode=36}, R{count=9 # hashCode=40}, R{count=-3 # hashCode=28}, R{count=-2 # hashCode=29}]

如何达到不能存在重复元素的目的？

“键”就是我们要存入的对象，“值”则是一个常量。这样可以确保，我们所需要的存储的信息是“键”。而“键”在Map中是不能重复的，这就保证了我们存入Set中的所有的元素都不重复。

HashSet如何过滤重复元素

调用元素HashCode获得哈希码--》判断哈希码是否相等，不相等则录入

---》相等则判断equals()后是否相等，不相等在进行 hashcode录入，相等不录入

LinkedHashSet的特征

LinkedHashSet是HashSet的一个子类，LinkedHashSet也根据HashCode的值来决定元素的存储位置，但同时它还用一个链表来维护元素的插入顺序，插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。查看LinkedHashSet的源码发现它是样的

public class LinkedHashSet

extends HashSet

implements Set, Cloneable, java.io.Serializable{

private static final long serialVersionUID = -2851667679971038690L;

public LinkedHashSet(int initialCapacity, float loadFactor){

super(initialCapacity, loadFactor, true);

}

....

在JAVA8中， LinkedHashSet没有定义任何方法，只有四个构造函数，它的构造函数调用了父类(HashSet)的带三个参数的构造方法，父类的构造函数如下

HashSet(int initialCapacity, float loadFactor, boolean dummy) {

map = new LinkedHashMap<>(initialCapacity, loadFactor);

}

由此可知，LinkedHashSet本质上也是从LinkedHashMap而来，LinkedHashSet的所有方法都继承自HashSet, 而它能维持元素的插入顺序的性质则继承自LinkedHashMap.

下面是一个LinkedHashSet维持元素插入顺序的例子

import java.util.LinkedHashSet;

import java.util.Set;

public class LinkedHashSets {

public static void main(String[] args) {

Set set = new LinkedHashSet();

set.add("abc");

set.add("efg");

set.add("hjk");

System.out.println(set);

set.remove(new String("abc"));

set.add("abc");

System.out.println(set);

}

}

输入如下

[abc, efg, hjk]

[efg, hjk, abc]

TreeSet类的特征

TreeSet实现了SortedSet接口，顾名思义这是一种排序的Set集合，查看jdk源码发现底层是用TreeMap实现的，本质上是一个红黑树原理。 正因为它是排序了的，所以相对HashSet来说，TreeSet提供了一些额外的按排序位置访问元素的方法，例如first(), last(), lower(), higher(), subSet(), headSet(), tailSet().

TreeSet的排序分两种类型，一种是自然排序，另一种是定制排序。

自然排序(在元素中写排序规则)

TreeSet 会调用compareTo方法比较元素大小，然后按升序排序。所以自然排序中的元素对象，都必须实现了Comparable接口，否则会抛出异常。对于TreeSet判断元素是否重复的标准，也是调用元素从Comparable接口继承而来额compareTo方法，如果返回0则是重复元素(两个元素I相等)。Java的常见类都已经实现了Comparable接口，下面举例说明没有实现Comparable存入TreeSet时引发异常的情况。

import java.util.Set;

import java.util.TreeSet;

public class TestSets{

public static void main(String[] args) {

Set set = new TreeSet();

set.add(new Err());

set.add(new Err());

set.add(new Err());

System.out.println(set);

}

}

class Err{

}

运行程序会抛出如下异常

Exception in thread "main" java.lang.ClassCastException: clc.Err cannot be cast to java.lang.Comparable

at java.util.TreeMap.compare(TreeMap.java:1294)

at java.util.TreeMap.put(TreeMap.java:538)

at java.util.TreeSet.add(TreeSet.java:255)

at clc.TestSets.main(TestSets.java:17)

将上面的Err类实现Comparable接口之后程序就能正常运行了

class Err implements Comparable{

@Override

public int compareTo(Object o) {

return 0;

}

}

还有个重要问题是，因为TreeSet会调用元素的compareTo方法，这就要求所有元素的类型都相同，否则也会发生异常。也就是说，TreeSet只允许存入同一类的元素。例如下面这个例子就会抛出类型转换异常

public static void main(String[] args) {

Set set = new TreeSet();

set.add(1);

set.add("2");

System.out.println(set);

}

运行结果

Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to java.util.Date

at java.util.Date.compareTo(Date.java:131)

at java.util.TreeMap.put(TreeMap.java:568)

at java.util.TreeSet.add(TreeSet.java:255)

at clc.TestSets.main(TestSets.java:19)

定制排序(在集合中写排序规则)

TreeSet还有一种排序就是定制排序，定制排序时候，需要关联一个Comparator对象，由Comparator提供排序逻辑。下面就是一个使用Lambda表达式代替Comparator对象来提供定制排序的例子。下面是一个定制排序的列子

import java.util.Comparator;

import java.util.Set;

import java.util.TreeSet;

public class TestSets {

public static void main(String[] args) {

Set set = new TreeSet(new MyCommpare());

set.add(new M(5));

set.add(new M(3));

set.add(new M(9));

System.out.println(set);

}

}

class M {

int age;

public M(int age) {

this.age = age;

}

}

class MyCommpare implements Comparator {

@Override

public int compare(Object o1, Object o2) {

M m1 = (M) o1;

M m2 = (M) o2;

return m1.age > m2.age ? 1 : m1.age < m2.age ? -1 : 0;

}

}

当然将Comparator直接写入TreeSet初始化中也可以。如下。

import org.junit.Test;

import java.util.Comparator;

import java.util.Set;

import java.util.TreeSet;

public class TestSets {

public static void main(String[] args) {

Set set = new TreeSet(new MyCommpare());

set.add(new M(5));

set.add(new M(3));

set.add(new M(9));

System.out.println(set);

}

@Test

public void testTreeSet() {

Set set = new TreeSet(new Comparator() {

@Override

public int compare(Object o1, Object o2) {

M m1 = (M) o1;

M m2 = (M) o2;

return m1.age > m2.age ? 1 : m1.age < m2.age ? -1 : 0;

}

});

set.add(new M(5));

set.add(new M(3));

set.add(new M(9));

System.out.println(set);

}

@Test

public void testTreeSetLam() {

Set set = new TreeSet((o1, o2) -> {

M m1 = (M) o1;

M m2 = (M) o2;

return m1.age > m2.age ? 1 : m1.age < m2.age ? -1 : 0;

});

set.add(new M(5));

set.add(new M(3));

set.add(new M(9));

System.out.println(set);

}

}

class M {

int age;

public M(int age) {

this.age = age;

}

}

class MyCommpare implements Comparator {

@Override

public int compare(Object o1, Object o2) {

M m1 = (M) o1;

M m2 = (M) o2;

return m1.age > m2.age ? 1 : m1.age < m2.age ? -1 : 0;

}

}

class Err implements Comparable {

@Override

public int compareTo(Object o) {

return 0;

}

TreeSet是依靠TreeMap来实现的。

TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口。

我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。

Comparable和Comparator

Comparable 接口以提供自然排序顺序。

对于那些没有自然顺序的类、或者当您想要一个不同于自然顺序的顺序时，您可以实现Comparator 接口来定义您自己的排序函数。可以将Comparator传递给Collections.sort或Arrays.sort。

Comparator接口

当一个类并未实现Comparable，或者不喜欢缺省的Comaparable行为。可以实现Comparator接口

直接实现Comparator的compare接口完成自定义比较类。

例：Arrays.sort(results, new Comparator() 数组排序 RepDataQueryExecutor

例：Collections.sort(lst,new Comparator()

EnumSet特征

EnumSet顾名思义就是专为枚举类型设计的集合，因此集合元素必须是枚举类型，否则会抛出异常。 EnumSet集合也是有序的，其顺序就是Enum类内元素定义的顺序。 EnumSet存取的速度非常快，批量操作的速度也很快。EnumSet主要提供以下方法，allOf, complementOf, copyOf, noneOf, of, range等。注意到EnumSet并没有提供任何构造函数，要创建一个EnumSet集合对象，只需要调用allOf等方法，下面是一个EnumSet的例子。

import java.util.EnumSet;

public class EnumSets {

public static void main(String[] args) {

EnumSet es1 = EnumSet.allOf(Season.class);

System.out.println(es1);

EnumSet es2 = EnumSet.noneOf(Season.class);

es2.add(Season.WINTER);

es2.add(Season.SUMER);

System.out.println(es2);

EnumSet es3 = EnumSet.of(Season.WINTER, Season.SUMER);

System.out.println(es3);

EnumSet es4 = EnumSet.range(Season.SUMER,Season.WINTER );

System.out.println(es4);

EnumSet es5 = EnumSet.complementOf(es4);

System.out.println(es5);

}

}

enum Season {

SPRING, SUMER, FALL, WINTER

}

执行结果

[SPRING, SUMER, FALL, WINTER]

[SUMER, WINTER]

[SUMER, WINTER]

[SUMER, FALL, WINTER]

[SPRING]

几种Set的比较：

HashSet外部无序地遍历成员。

成员可为任意Object子类的对象，但如果覆盖了equals方法，同时注意修改hashCode方法。

TreeSet外部有序地遍历成员；

附加实现了SortedSet, 支持子集等要求顺序的操作

成员要求实现Comparable接口，或者使用Comparator构造TreeSet。成员一般为同一类型。

LinkedHashSet外部按成员的插入顺序遍历成员

成员与HashSet成员类似

HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。

HashSet的元素存放顺序和我们添加进去时候的顺序没有任何关系，而LinkedHashSet 则保持元素的添加顺序。TreeSet则是对我们的Set中的元素进行排序存放。

一般来说，当您要从集合中以有序的方式抽取元素时，TreeSet实现就会有用处。为了能顺利进行，添加到 TreeSet 的元素必须是可排序的。 而您同样需要对添加到TreeSet中的类对象实现 Comparable 接口的支持。一般说来，先把元素添加到 HashSet，再把集合转换为 TreeSet 来进行有序遍历会更快。

各种Set集合性能分析

HashSet和TreeSet是Set集合中用得最多的I集合。HashSet总是比TreeSet集合性能好，因为HashSet不需要额维护元素的顺序。

LinkedHashSet需要用额外的链表维护元素的插入顺序，因此在插入时性能比HashSet低，但在迭代访问(遍历)时性能更高。因为插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。

EnumSet元素是所有Set元素中性能最好的，但是它只能保存Enum类型的元素

Map

集合框架的第二类接口树。

它提供了一组键值的映射。其中存储的每个对象都有一个相应的关键字(key)，关键字决定了对象在Map中的存储位置。

关键字应该是唯一的，每个key 只能映射一个value。

实现类：

HashMap、TreeMap、LinkedHashMap、Hashtable等

HashMap：键值对，key不能重复，但是value可以重复；key的实现就是HashSet；value对应着放；允许null的键或值；

Hashtable：线程安全的，不允许null的键或值；

Properties:：key和value都是String类型，用来读配置文件；

TreeMap：对key排好序的Map; key 就是TreeSet, value对应每个key; key要实现Comparable接口或TreeMap有自己的构造器；

LinkedHashMap： 此实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。存储的数据是有序的。

HashMap：

Map 主要用于存储键(key)值(value)对，根据键得到值，因此键不允许重复,但允许值重复。

HashMap 是一个最常用的Map,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。

HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;

HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力。

HashMap实现原理---散列

Hash哈希算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系。散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系(散列函数)计算出对应的函数值，以这个值作为该结点存储在散列表中地址。

当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子(load factor)来决定何时对散列表进行再散列。例如：如果负载因子0.75，当散列表中已经有75%位置已经放满，那么将进行再散列。

负载因子越高(越接近1.0)，内存的使用效率越高，元素的寻找时间越长。负载因子越低(越接近0.0)，元素的寻找时间越短，内存浪费越多。

何时需重写equals？

当一个类有自己特有的“逻辑相等”概念(不同于对象身份的概念)；

Object类仅仅提供了一个对引用的比较，如果两个引用不是同一个那就返回false，这是无法满足大多数对象比较的需要的，所以要覆盖；

使用==操作符检查实参是否为指向对象的引用”

使用instanceof操作符检查实参是否为正确的类型

把实参转换到正确的类型；

对于该类中每一个“关键”域，检查实参中的域与当前对象中对应的域值是否匹配。对于既不是float也不是double类型的基本类型的域，可以使用==操作符进行比较；对于对象引用类型的域，可以递归地调用所引用的对象的equals方法，对于float和double类型的域，先转换成int或long类型的值，然后使用==操作符比较；

当你编写完成了equals方法之后，应该问自己三个问题：它是否是对称的、传 递的、一致的？ 如果答案是否定的，那么请找到 这些特性未能满足的原因，再修改equals方法的代码

equals()和hashCode()同时覆写

尤其强调当一个对象被当作键值(或索引)来使用的时候要重写这两个方法；

覆写equals后，两个不同实例可能在逻辑上相等，但是根据Object.hashCode方法却产生不同的散列码，违反“相等的对象必须具有相等的散列码”。

导致，当你用其中的一个作为键保存到hashMap、hasoTable或hashSet中，再以“相等的”找另 一个作为键值去查找他们的时候，则根本找不到

不同类型的hashCode取值

如果该域是布尔型的，计算(f？0：1)

如果是char,short,byte或int，计算(int)f

如果是long类型，计算(int)(f^(f>>>32))

如果是float类型，计算Float.floatToIntBits(f)

如果是double类型，计算Dobule.doubleToLongBits(f)

如果该域是一个对象引用，递归调用hashCode

如果该域是一个数组，则把每个元素当做单独的域来处理，对每个重要的元素计算一个散列码

Map集合比较：

HashMap的存入顺序和输出顺序无关。

LinkedHashMap 则保留了键值对的存入顺序。

TreeMap则是对Map中的元素进行排序。

因为HashMap和LinkedHashMap 存储数据的速度比直接使用TreeMap 要快，存取效率要高。

当完成了所有的元素的存放后，我们再对整个的Map中的元素进行排序。这样可以提高整个程序的运行的效率，缩短执行时间。

注意：TreeMap中是根据键(Key)进行排序的。而如果我们要使用TreeMap来进行正常的排序的话，Key 中存放的对象必须实现Comparable 接口。

Map常用方法：

Object put(Object key,Object value)：用来存放一个键-值对Map中

Object remove(Object key)：根据key(键)，移除键-值对，并将值返回

void putAll(Map mapping) ：将另外一个Map中的元素存入当前的Map中

void clear() ：清空当前Map中的元素

Object get(Object key) ：根据key(键)取得对应的值

boolean containsKey(Object key) ：判断Map中是否存在某键(key)

boolean containsValue(Object value):判断Map中是否存在某值(value)

public Set keySet() ：返回所有的键(key)，并使用Set容器存放

public Collection values() ：返回所有的值(Value)，并使用Collection存放

public Set entrySet() ：返回一个实现 Map.Entry 接口的元素 Set

集合遍历

增强for循环 for(Obj o:c){syso(o)}

使用iterator ， Iterator it=c.iterator;

while(it.hasNext()){Object o = it.next()}

普通循环：for(Iterator it=c.iterator();it.hasNext();){it.next() }

总结

ArrayList: 元素单个，效率高，多用于查询

Vector: 元素单个，线程安全，多用于查询

LinkedList:元素单个，多用于插入和删除

HashMap: 元素成对，元素可为空

shTable: 元素成对，线程安全，元素不可为空

HashMap和Hashtable的区别：

HashMap和Hashtable都是java的集合类，都可以用来存放java对象，这是他们的相同点

以下是他们的区别：

历史原因：

Hashtable是基于陈旧的Dictionary类的，HashMap是java 1.2引进的Map接口的一个现实。

同步性：

hashtable是同步的，这个类中的一些方法保证了Hashtable中的对象是线程安全的，而HashMap则是异步的，因此HashMap中的对象并不是线程安全的，因为同步的要求会影响执行的效率，所以如果你不需要线程安全的结合那么使用HashMap是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销，从而提高效率，我们一般所编写的程序都是异步的，但如果是服务器端的代码除外。

值：

HashMap可以让你将空值作为一个表的条目的key或value

Hashtable是不能放入空值(null)的

ArrayList和Vector的区别：

ArrayList与Vector都是java的集合类，都是用来存放java对象，这是他们的相同点，

区别：

同步性：

Vector是同步的，这个类的一些方法保证了Vector中的对象的线程安全的，而ArrayList则是异步的，因此ArrayList中的对象并不 是线程安全的，因为同步要求会影响执行的效率，所以你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必 要的性能开销。

数据增长：

从内部实现的机制来讲，ArrayList和Vector都是使用数组(Array)来控制集合中的对象，当你向两种类型中增加元素的时候，如果元素的数目超过了内部数组目前的长度他们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%，所以最后你获得的这个集合所占的空间总是比你实际需要的要大，所以如果你要在集合中保存大量的数据，那么使用Vector有一些优势，因为你可以通过设置集合的初始大小来避免不必要的资源开销。

总结：

如果要求线程安全，使用Vector，Hashtable

如果不要求线程安全，使用ArrayList，LinkedList，HashMap

如果要求键值对，则使用HashMap，Hashtable

如果数据量很大，又要求线程安全考虑Vector

arraylist和linkedlist联系与区别

ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。 这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

HashMap与TreeMap联系与区别

HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。

在Map 中插入、删除和定位元素，HashMap是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。

两个map中的元素一样，但顺序不一样，导致hashCode()不一样。

同样做测试：

在HashMap中，同样的值的map,顺序不同，equals时，false;

而在treeMap中，同样的值的map,顺序不同,equals时，true，说明，treeMap在equals()时是整理了顺序了的。