java 容器

Java Collections框架是什么

Java Collections框架中包含了大量集合接口以及这些接口的实现类和操作它们的算法(例如排序、查找、反转、替换、复制、取最小元素、取最大元素等)，具体而言，主要提供了List (列表)、Queue (队列)、Set (集合)、Stack (栈)和Map (映射表，用于存放键值对)等数据结构。其中，List、 Queue、 Set、 Stack 都继承自Collection接口。
Collection是整个集合框架的基础，它里面储存一组对象，表示不同类型的Collections,它的作用只是提供维护一-组对象的基本接口而已。

下面分别介绍Set、List 和Map3个接口。

1) Set表示数学意义上的集合概念。其最主要的特点是集合中的元素不能重复，因此存入Set的每个元素都必须定义equals( )方法来确保对象的唯一性。该接口有两个实现类: Hash-Set和TreeSet。其中TreeSet实现了SortedSet 接口，因此TreeSet容器中的元素是有序的。

2) List 又称为有序的Collection。它按对象进人的顺序保存对象，所以它能对列表中的每个元素的插人和删除位置进行精确的控制。同时，它可以保存重复的对象。LinkedList、 Array-List和Vector都实现了List 接口。

3) Map提供了一个从键映射到值的数据结构。它用于保存键值对，其中值可以重复，但键是唯一的，不能重复。Java 类库中有多个实现该接口的类: HashMap、 TreeMap、Linked-HashMap、WeakHashMap 和IdentityHashMap。虽然它们都实现了相同的接口，但执行效率却不是完全相同的。具体而言，HashMap 是基于散列表实现的，采用对象的HashCode可以进行快速查询。LinkedHashMap采用列表来维护内部的顺序。TreeMap 基于红黑树的数据结构来实现的，内部元素是按需排列的。

什么是迭代器？

迭代器(Iterator)是个对象，它的工作是遍历并选择序列中的对象，它提供了一种切问一个容器(container) 对象中的各个元素，而又不必暴露该对象内部细节的方法。通过迭代器，开发人员不需要了解容器底层的结构，就可以实现对容器的遍历。由于创建迭代器的代价小，因此迭代器通常被称为轻量级的容器。
迭代器的使用主要有以下3个方面的注意事项:

1)使用容器的iterator( )方法返回一个Iterator, 然后通过Iterator 的next( )方法返回第1个元素。

2)使用Iterator的hasNext( )方法判断容器中是否还有元素，如果有，可以使用next()方法获取下一个元素。

3)可以通过remove()方法删除迭代器返回的元素。
Iterator支持派生的兄弟成员。ListIterator 只存在于List中，支持在迭代期间向List中添加或删除元素，并且可以在List 中双向滚动。
Iterator的使用方法如下例所示:

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class IteratorTest {
	public static void main(String[] args) {
		List<String> list=new LinkedList<String>();
		list.add("first");
		list.add("second");
		list.add("third");
		list.add("forth");
		for(Iterator<String> iter=list.iterator();iter.hasNext();){
			String str=iter.next();
			System.out.println(str);
		}
	}
}

运行结果：

first
second
third
forth

在使用Iterator（）方法中会遇到ConcurrentModificationException 异常，这通常是因为在Iterator遍历容器的同时又对容器进行增加或者删除导致的，或者由于多线程所致，当一个线程进行迭代器遍历容器的同时，另一个线程对这个容器进行增加或者删除操作。下例主要介绍单线程抛出ConcurrentModificationException的情况：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;


public class IteratorTest {
	public static void main(String[] args) {
		List<String> list=new LinkedList<String>();
		list.add("first");
		list.add("second");
		list.add("third");
		list.add("fourth");
		for(Iterator<String> iter=list.iterator();iter.hasNext();){
			String str=iter.next();
			System.out.println(str);
			if(str.equals("second")){
				list.add("five");
			}
		}
	}
}

运行结果：

first
second
Exception in thread “main” java.util.ConcurrentModificationException
at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761)
at java.util.LinkedList$ListItr.next(LinkedList.java:696)
at IteratorTest.main(IteratorTest.java:14)

抛出上述异常的主要原因是当调用容器的iterator( )方法返回Iterator 对象时，把容器中包含对象的个数赋值给了一个变量expectedModCount,在调用next( )方法时会比较变量expectedModCount与容器中实际对象的个数modCount的值是否相等，若二者不相等，则会抛出ConcurrentModificationException异常，因此在使用Iterator遍历容器的过程中，如果对容器进行增加或删除操作，就会改变容器中对象的数量，从而导致抛出异常。

解决方法如下:在遍历的过程中把需要删除的对象保存到一个集合中，等遍历结束后在调用removeAll( )方法来删除，或者使用iter. remove( )方法。

以上主要介绍了单线程的解决方案，那么多线程访问容器的过程中抛出ConcurrentModificationException异常又该怎么解决呢?
1)在JDK 1.5版本引人了线程安全的容器，比如ConcurrentHashMap和CopyOnWriteArray-List等。可以使用这些线程安全的容器来代替非线程安全的容器。
2)在使用迭代器遍历容器时对容器的操作放到synchronized代码块中，但是当引用程序并发程度比较高时，这会严重影响程序的性能。

引申: Iterator 与Listlterator有什么区别?
Iterator 只能正向遍历集合，适用于获取移除元素。Lsterator 继承自Iterator, 专门针对Lis,可以从两个方向来遍历List,同时支持元素的修改。

ArrayList ，Vector和LinkedList有什么区别

这三者都是实现集合框架中的List，也就是所谓的有序集合，因此具体功能也比较近似，比如都提供按照位置进行定位、添加或者删除的操作，都提供迭代器以遍历其内容等。但因为具体的设计区别，在行为、性能、线程安全等方面，表现又有很大不同。

Vector 是 Java 早期提供的线程安全的动态数组，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。

ArrayList 是应用更加广泛的动态数组实现，它本身不是线程安全的，所以性能要好很多。与 Vector近似，ArrayList 也是可以根据需要调整容量，不过两者的调整逻辑有所区别，Vector 在扩容时会提高 1 倍，而 ArrayList 则是增加 50%。

LinkedList 顾名思义是 Java 提供的双向链表，所以它不需要像上面两种那样调整容量，它也不是线程安全的。

谈谈不同容器类型适合的场景：

Vector 和 ArrayList 作为动态数组，其内部元素以数组形式顺序存储的，内存为一连续的区域，所以非常适合随机访问的场合。除了尾部插入和删除元素，往往性能会相对较差，比如我们在中间位置插入一个元素，需要移动后续所有元素。数组大小固定，不适合动态存储，不方便动态添加。
LinkedList 进行节点插入、删除却要高效得多，大小可变，内存可能是不连续内存，链式存储。但是只能通过顺次指针访问，查询效率低，随机访问性能则要比动态数组慢。
因此，在应用开发中，如果事先可以估计到，应用操作是偏向于插入、删除，还是随机访问较多，就可以针对性的进行选择。

总结：

快速插入、删除元素，使用LinkedList
快速随机访问元素，使用ArrayList
单线程，使用List，比如ArrayList
多线程，使用Vector

HashMap、Hashtable、TreeMap、和WeakHashMap有什么区别

Java为数据结构中的映射定义了一个接口java. uil Map,它包括3个实现类: HahMap、Hashtable和TreeMep. Map 是用来存储键值对的数据结构，在数组中通过数组下标来对其内容索引的，而在Map中，则是通过对象来进行索引，用来索引的对象叫做key,其对应的对象叫做value。
HashMap是一个最常用的Map,它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。由于HashMap与Hashtable都采用了hash法进行索引，因此二者具有许多相似之处，它们主要有如下的一些区别:
1) HashMap 是Hashtable的轻量级实现( 非线程安全的实现)，它们都完成了Map 接口，主要区别在于HashMap允许空(null) 键值(key) (但需要注意，最多只允许一条记录的键为null,不允许多条记录的值为null),而Hashtable不允许。

2) HashMap 把Hashtable的contains 方法去掉了，改成containsvalue和containsKey.因为contains方法容易让人引起误解。Hashtable 继承自Dictionary 类，而HashMap是Java 1.2引进的Map interface的一个实现。

3) Hashtable 的方法是线程安全的，而HashMap不支持线程的同步，所以它不是线程安全的。在多个线程访问Hashtable时，不需要开发人员对它进行同步，面对于HashMap, 开发人员必须提供额外的同步机制。所以，就效率而言，HashMap 可能高于Hashtable

4) Hashable使用Enumeration, HashMap 使用lterator

5) Hashable和HashMap采用的hash/ rehash算法都几乎一样，所以性能不会有很大的差异。

6)在Hashtable 中，hash 数组默认大小是11,增加的方式是oldx2+1。在HeshMap中，hash数组的默认大小是16，而且一定是2的指数。

7) hash值的使用不同，Hashtable直接使用对象的hashCode。

以上3种类型中，使用最多的是HashMap, HashMap 里面存人的键值对在取出时没有固定的顺序，是随机的。一般而言，在Map中插人、删除和定位元素，HashMap 是最好的选择。由于TreeMap实现了SortMap 接口，能够把它保存的记录根据键排序，因此，取出来的是排序后的键值对，如果需要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。LinkedHash-Map是HashMap的一个子类，如果需要输出的顺序和输人的相同，那么用LinkedHashMap可以实现，它还可以按读取顺序来排列。
WeakHashMap与HashMap类似，二者的不同之处在于WeakHashMap 中key采用的是“弱引用”的方式，只要WeakHashMap中的key不再被外部引用，它就可以被垃圾回收器回收。而HashMap中key采用的是“强引用的方式”，当HashMap中的key没有被外部引用时，只有在这个key从HashMap中删除后，才可以被垃圾回收器回收。
常见笔试题:
1.在Hashtable. 上下文中，同步指的是什么?
答案:同步意味着在一个时间点只能有一个线程可以修改hash表、任何线程在执行Hashtable 的更新操作前都需要获取对象锁，其他线程则等待锁的释放。
2.如何实现HashMap的同步?
答案: HashMap 可以通过Map m = Collections.synchronizedMap(new HashMap())达到同步的效果。具体而言，该方法返回一个同步的Map.该Map封装了底层的HashMap的所有方法，使得底层的HashMap即使是在多线程的环境中也是安全的。

用自定义类型作为HashMap或者Hashtable的key需要注意哪些问题

用自定义类作为key，必须重写equals()和hashCode()方法。

自定义类中的equals() 和 hashCode()都继承自Object类。

Object类的hashCode()方法返回这个对象存储的内存地址的编号。

而equals()比较的是内存地址是否相等。

以下是没有重写equals()和hashCode()方法；

自定义 PhoneNumber类

public class PhoneNumber {
  private int prefix; //区号
   private int phoneNumber; //电话号
public int getPrefix() {
return prefix;
}
public void setPrefix(int prefix) {
this.prefix = prefix;
}
public int getPhoneNumber() {
return phoneNumber;
}
public void setPhoneNumber(int phoneNumber) {
this.phoneNumber = phoneNumber;
}


}


 public static void main(String[] args) {

 Map<PhoneNumber, String> map =new  HashMap<PhoneNumber, String>();
 PhoneNumber phoneNumber1=new PhoneNumber();
 phoneNumber1.setPhoneNumber(111);
 phoneNumber1.setPrefix(111);
 PhoneNumber phoneNumber2=new PhoneNumber();
 phoneNumber2.setPhoneNumber(222);
 phoneNumber2.setPrefix(222);
 map.put(phoneNumber1, "111");
 map.put(phoneNumber2, "222");

 System.out.println(map.get(phoneNumber1));
 System.out.println(map.get(phoneNumber2));

 PhoneNumber phoneNumber3=new PhoneNumber();
 //参数内容和phoneNumber2一样
 phoneNumber3.setPhoneNumber(222);
 phoneNumber3.setPrefix(222);
 System.out.println(map.get(phoneNumber3));

   }

输出结果

111
222
null

在PhoneNumber 类中重写equals()和hashCode()方法；



@Override
 public boolean equals(Object o)
 {
     if(this == o)
     {
         return true;
     }
     if(!(o instanceof PhoneNumber))
     {
         return false;
     }
     PhoneNumber pn = (PhoneNumber)o;
     return pn.prefix == prefix && pn.phoneNumber == phoneNumber;
 }

 @Override
 public int hashCode()
 {
     int result = 17;
     result = 31 * result + prefix;
     result = 31 * result + phoneNumber;
     return result;
 }

输出结果

111
222
222