JAVA 集合类

Set,List,Map的区别
java集合的主要分为三种类型：
Set（集）
List（列表）
Map（映射）

Collection接口

Collection是最基本的集合接口，声明了适用于JAVA集合(只包括Set和List)的通用方法。Set和List都继承了Collection,Map

Collection接口的方法：
boolean add(Object o)      ：向集合中加入一个对象的引用   
void clear()：删除集合中所有的对象，即不再持有这些对象的引用   
boolean isEmpty()    ：判断集合是否为空   
boolean contains(Object o) ： 判断集合中是否持有特定对象的引用   
Iterartor iterator()  ：返回一个Iterator对象，可以用来遍历集合中的元素   
boolean remove(Object o) ：从集合中删除一个对象的引用   
int size()   ：返回集合中元素的数目   
Object[] toArray()  ： 返回一个数组，该数组中包括集合中的所有元素 </SPAN>  


Iterator接口声明了如下方法： 

hasNext()：判断集合中元素是否遍历完毕，如果没有，就返回true
next() ：返回下一个元素  
remove()：从集合中删除上一个有next()方法返回的元素。
------------------------------------------------------------------------------------------------------------------------------------
List

List接口主要实现类包括:

ArrayList() : 代表长度可以改变得数组。ArrayList在Java内部实现也是进行封装的数组，当增加的元素后个数大于当前数组个数，ArrayList会重新创建新的数组。
因为数组是一段连续的内存，那么意味着可以对元素很快速的利用下标进行访问(ArrayList.get(index))，但如果向ArrayList()中间插入与删除元素的速度慢，因为它要将后面的元素向后移动。



LinkedList(): 在实现中采用链表数据结构，每个元素中不仅包括元素本身的值，还包含指向下个元素的内存地址的指针，各个元素之间通过指针进行串联起来。
由于这种结构设计，LinkedList插入和删除速度快，它可以直接改变指向下个元素的指针内存地址即可，但如果通过下标访问，则访问速度慢。(通过一个个指针查找)


对于List的随机访问来说，就是只随机来检索位于特定位置的元素。 List 的 get(int index) 方法放回集合中由参数index指定的索引位置的对象，
下标从“0” 开始。最基本的两种检索集合中的所有对象的方法： 


检索list的方法：

for (int i = 0; i < list.size(); i++) {
  System.out.println(list.get(i));  
}

使用 迭代器（Iterator）: 

Iterator it = list.iterator();
while(it.hasNext()){
  System.out.println(it.next());
}


Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承于Collection接口 从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。 

Map 的常用方法： 

1 添加，删除操作： 


Object put(Object key, Object value)： 向集合中加入元素 
Object remove(Object key)： 删除与KEY相关的元素 
void putAll(Map t)：  将来自特定映像的所有元素添加给该映像 
void clear()：从映像中删除所有映射 

2 查询操作： 

Object get(Object key)：获得与关键字key相关的值 。Map集合中的键对象不允许重复，也就说，任意两个键对象通过equals()方法比较的结果都是false.
但是可以将任意多个键独享映射到同一个值对象上。 

方法put(Object key, Object value)添加一个“值”(想要得东西)和与“值”相关联的“键”(key)(使用它来查找)。方法get(Object key)返回与给定“键”相关联的“值”。
可以用containsKey()和containsValue()测试Map中是否包含某个“键”或“值”。
 
--HashMap
Map<Integer,Student> stuMap = new HashMap<Integer,Student>();
stuMap.put(1234, new Student(1234,"yange"));
stuMap.put(1235, new Student(1235,"xiaowang"));
stuMap.put(1236, new Student(1236,"xiaoli"));
for(Map.Entry<Integer, Student> en:stuMap.entrySet()){//循环Map中的每个键值对, hashmap的内部实现为数组保存，保存的元素为entry
  System.out.println(en.getKey()+ " "+en.getValue());
}

HashMap不保证查询遍历顺序，无论不插入顺序或者Key值大小排序顺序。
无论HashMap保存的元素上W个或者百万级别，通过Key值访问的消耗是固定的，因为Key值通过Hash运算后得出的数组下标，通过下标可以直接访问到元素。



--LinkedHashMap

LinkedHashMap 是HashMap的一个子类，保证查询的顺序，可以按照插入顺序输出

--TreeMap
TreeMap，采用二叉树，保证插入的顺序是按照key插入的。查询也是按照key大小顺序输出。


------------------------------------------------------------------------------------------------------------------------------------
Set(集合)

Set是最简单的一种集合。集合中的对象不按特定的方式排序，并且没有重复对象。 Set接口主要实现了两个实现类：

HashSet： HashSet类按照哈希算法来存取集合中的对象，存取速度比较快 
TreeSet ：TreeSet类实现了SortedSet接口，能够对集合中的对象进行排序。

Set 的用法：存放的是对象的引用，没有重复对象

Set set = new HashSet();
String s1 = new String("hello");
String s2 = s1;
String s3 = new String("world");
set.add(s1);
set.add(s2);
set.add(s3);
System.out.println(set.size());//打印集合中对象的数目 为 2。


Set 的 add()方法是如何判断对象是否已经存放在集合中？ 

boolean isExists = false;
Iterator it = set.iterator();
while(it.hasNext()){
String oldstr = (String)it.next();
if(s2.equals(oldstr)){
  isExists = true;
}
}

Set : 存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。
Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。 



HashSet：为快速查找设计的Set。
HashSet不能添加重复的元素，当调用add（Object）方法时候，
首先会调用Object的hashCode方法判hashCode是否已经存在，如不存在则直接插入元素；
hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值
如果已存在则调用Object对象的equals方法判断是否返回true， 如果为true则说明元素已经存在，如为false则插入元素。



TreeSet： 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。 
LinkedHashSet：具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。

遍历Set的方法

Set<String> set = new HashSet<String>();  
Iterator<String> it = set.iterator();  
while (it.hasNext()) {  
  String str = it.next();  
  System.out.println(str);  
}  
  
2.for循环遍历：  
for (String str : set) {  
     System.out.println(str);  
}
------------------------------------------------------------------------------------------------------------------------------------

Queue
保证先进先出，后进后出，不能插入到中间，或取中间的元素

REMOVE() 方法：取出并移走队列的头部，当队列为空时，返回一个异常。
POLL()方法： 取出并移走队列的头部，当队列为空时，返回NULL。
PEEK()方法：获取队列的头部元素，但并不移走。当队列为空时，返回NULL。

public static void main(String args[]){
  Queue<String> strSet = new LinkedList<String>();
  strSet.add("2");
  strSet.add("1");
  strSet.add("3");
  strSet.add("4");
  while(!strSet.isEmpty()){
    System.out.println(strSet.peek()); // 2 1 3 4
  }
}   
Deque
双端队列，可以选择从队列的头部或者尾部插入元素


FileIterator 类，利用队列一层层从外向里打印文件名称，先打印当前层次的所有文件后，再进入下一层

public List<String> listFiles(String dir){
    File fdir = new File(dir);
    List<String> subfiles = new ArrayList<String>();
    Queue<File> fileQueue = new ConcurrentLinkedQueue<File>();
    fileQueue.add(fdir);
    while(!fileQueue.isEmpty()){
      File file = fileQueue.poll();
      subfiles.add(file.getAbsolutePath());
      if(file.isFile()){
        continue;
      }
      File[] files = file.listFiles();
      for(File f:files){
        fileQueue.add(f);
      }
    }
    return subfiles;
  }



Stack 栈
最先进的元素，一定是在最后面，拿的话只能是拿最近进入的。
push()
增加一个元素压到栈中。
pop()
从栈中弹出一个元素

public static void main(String args[]){
   Stack<String> stackSet = new Stack<String>();
   stackSet.push("2");
   stackSet.push("1");
   stackSet.push("3");
   stackSet.push("4");
   while(!stackSet.isEmpty()){
     System.out.println(stackSet.pop());// 4 3 1 2
   }
 }


public List<String> listFiles(String dir){
    File fdir = new File(dir);
    List<String> subfiles = new ArrayList<String>();
    Stack<File> fileQueue = new Stack<File>();
    fileQueue.push(fdir);
    while(!fileQueue.isEmpty()){
      File file = fileQueue.pop();
      subfiles.add(file.getAbsolutePath());
      if(file.isFile()){
        continue;
      }
      File[] files = file.listFiles();
      for(File f:files){
        fileQueue.push(f);
      }
    }
    return subfiles;
  }
}
------------------------------------------------------------------------------
任何集合类都可以通过使用同步包装器变成线程安全的：

List<E> synchArrayList = Collections.synchronizedList(new ArrayList<E>());
Map<K,V> synchMap = Collections.synchronizedMap(new HasMap<K,V>());

其他常用的线程安全集合类

Vector
与ArrayList的线程安全类，但各个方法都有添加Synchronized关键字

Hashtable
是HashMap的线程安全类
它把所有方法都加上synchronized关键字来实现线程安全


注意：
如果使用for each 循环必须使用同步锁锁。

为什么线程安全的Vector也不能线程安全地遍历呢？其实道理也很简单，看Vector源码可以发现它的很多方法都加上了synchronized来进行线程同步，例如add()、remove()、set()、get()，
但是Vector内部的synchronized方法无法控制到遍历操作，所以即使是线程安全的Vector也无法做到线程安全地遍历。
如果想要线程安全地遍历Vector，需要我们去手动在遍历时给Vector加上synchronized锁，防止遍历的同时进行remove操作。

示例：
import java.util.Vector;

public class TestConcurrentModifyException implements Runnable {
	Vector<String> synchArrayList = new Vector<String>();
	public static void main(String args[]) throws InterruptedException{
		TestConcurrentModifyException test =  new TestConcurrentModifyException();
		test.synchArrayList.add("a");
		test.synchArrayList.add("b");
		test.synchArrayList.add("c");
		test.synchArrayList.add("d");
		test.synchArrayList.add("e");
		Thread tr = new Thread(test);
		tr.start();
		Thread.sleep(500);
		test.synchArrayList.add("f");
		Thread.sleep(500);
		test.synchArrayList.add("g");
		Thread.sleep(500);
		test.synchArrayList.add("h");
	}

	@Override
	public void run() {
		for(String str:synchArrayList){
			System.out.println("线程安全List Size："+synchArrayList.size());
			try {
				Thread.sleep(500);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			System.out.println(str);
		}		
	}
}

线程安全List Size：5
a
Exception in thread "Thread-0" java.util.ConcurrentModificationException
	at java.util.Vector$Itr.checkForComodification(Vector.java:1156)
	at java.util.Vector$Itr.next(Vector.java:1133)
	at TestConcurrentModifyException.run(TestConcurrentModifyException.java:26)
	at java.lang.Thread.run(Thread.java:745)

解决方案:

public void run() {
synchronized (synchArrayList) {
	for (String str : synchArrayList) {
		System.out.println("线程安全List Size：" + synchArrayList.size());
		try {
			Thread.sleep(100);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println(str);
	}
}
}

CopyOnWriteArrayList
CopyOnWrite的意思是在写时拷贝，也就是如果需要对CopyOnWriteArrayList的内容进行改变，首先会拷贝一份新的List并且在新的List上进行修改，最后将原List的引用指向新的List。
使用CopyOnWriteArrayList可以线程安全地遍历，因为如果另外一个线程在遍历的时候修改List的话，实际上会拷贝出一个新的List上修改，而不影响当前正在被遍历的List。

ConcurrentHashMap
ConcurrentHashMap的设计有点特别，表现在多个线程操作上。它不用做外的同步的情况下默认同时允许16个线程读和写这个Map容器。因为其内部的实现剥夺了锁，
使它有很好的扩展性。不像HashTable和Synchronized Map，ConcurrentHashMap不需要锁整个Map，相反它划分了多个段(segments)，要操作哪一段才上锁那段数据。

悲观锁：
总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁。
传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。再比如Java里面的同步原语synchronized关键字的实现也是悲观锁。

乐观锁：
顾名思义，就是很乐观，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，
可以使用版本号等机制。乐观锁适用于多读的应用类型，这样可以提高吞吐量，像数据库提供的类似于write_condition机制，其实都是提供的乐观锁。
在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS实现的