JAVA collection

Collection接口

• Collection是一个集合，它是一个interface，List和Set都是它的subinterface。

Set接口

• set是Collection的子接口，它不能有重复元素，不能以自身为set内的元素。

  HashSet

• 散列码（hash code）是一个表示对象某些相对位移特性的整数值。散列码由hashcode方法生成，该方法返回基于内存对象地址返回的一个值。对象经常覆盖hashcode方法，以获得更合适的表现自身的值。

• 散列码通过散列法的过程快速找到存储在散列表中的对象键值对。HashSet内部是有HashMap实现的。

• 建议添加到集合的对象一定要实现hashcode和equals方法。

  TreeSet

List接口

• List包含了添加、删除和获取集合内部特定位置元素的附加方法。

  ArrayList

  LinkedList

Map

• Map接口并不是一个Collection，他没有对Collection接口进行扩展。Map内有一个方法entrySet()方法，这个方法返回的是一个set，set里面的元素是Entry内部接口。Entry(K，V)是一个元组里面放的是Key和Value，把他们变成一个对象。

  HashMap

• HHashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

• 往hashmap里面放键值对的时候先得到key的hashcode，然后重新计算hashcode，（让1分布均匀因为如果分布不均匀，低位全是0，则后来计算数组下标的时候会冲突），然后与length-1按位与，计算数组出数组下标如果该下标对应的链表为空，则直接把键值对作为链表头结点，如果不为空，则遍历链表看是否有key值相同的，有就把value替换，没有就把该对象最为链表的第一个节点，原有的节点最为他的后续节点

• 值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

• Map map = Collections.synchronizedMap(new HashMap());

• 参数:初始容量16，达到阀值扩容，阀值等于最大容量*负载因子，扩容每次2倍，总是2的n次方.

  HashMap的数据结构:

• HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。

  HashTable

  TreeMap

• TreeMap是继承自AbstractMap，AbstractMap实现了Map接口。它的实现是通过红黑树。它自定义了自己的Entry<K,V>。这个Entry里包含的元素有Key,Value,parent,left child,color等成员变量。根据算法维持红黑树的特性。

• 可以接受一个Comparator对象作为构造函数。

Iterator,ListIterator和Enumeration接口

• Iterator接口提供迭代和删除集合内元素的能力。List和Set实现提供了各种返回Iterator实现的方法。这些迭代器是故障快速修复的（fail-fast），这以为这如果在迭代过程中试图从迭代器外部修改底层对象，他们会立刻失效。
• ListIterator是一个对Iterator的一个扩展，它提供了向后移动以及添加和替换列表元素的功能。ListIterator也是快速修复的。

Iterator，ListIterator与Enumeration接口的区别：

作为集合框架的一部分，Iterator和ListIterator旨在替换以前的Enumeration接口，该接口最初由Vector和HashTable类支持。他们本质上都具有相同功能。除了下面几项以外：

• Iterator提供集合删除元素的功能
• Iterator和ListIterator是故障快速修复的，Enumeration实现不是故障快速修复的，因此如果枚举过程中对集合进行修复，可能会产生不可预知的和不想得到的结果。
• ListIterator为操作列表提供了一些附加方法。
• Iterator和ListIterator提供较短的方法名称。
• Enumeration方法包括hasMoreElements()和nextElement()
• Iterator提供方法：hasNext()，next()，remove()
• ListIterator除了Iterator以外还提供：nextIndex()，previousIndex(),hasPrevious()，previous()，add()， set().
• vector和HashTable都它支持在元素总进行枚举（enumeration）的功能。

Java中的同步容器类

在Java中，同步容器主要包括2类：

1）Vector、Stack、HashTable

2）Collections类中提供的静态工厂方法创建的类

Vector实现了List接口，Vector实际上就是一个数组，和ArrayList类似，但是Vector中的方法都是synchronized方法，即进行了同步措施。

Stack也是一个同步容器，它的方法也用synchronized进行了同步，它实际上是继承于Vector类。

HashTable实现了Map接口，它和HashMap很相似，但是HashTable进行了同步处理，而HashMap没有。

Collections类是一个工具提供类，注意，它和Collection不同，Collection是一个顶层的接口。在Collections类中提供了大量的方法，比如对集合或者容器进行排序、查找等操作。最重要的是，在它里面提供了几个静态工厂方法来创建同步容器类。