另 集合框架实际使用的思考：
http://www.tot.name/show/3/7/20060530161152.htm
原文出处 ： http://www.cnblogs.com/zhxxcq/archive/2012/03/11/2389611.html
另： 源码及原理分析 ： http://wiki.jikexueyuan.com/project/java-collection/linkedlist.html
要点1：
Java的集合类主要由两个接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口，这两个接口又包含了一些接口或实现类。
Set和List接口是Collection接口派生的两个子接口，Queue是Java提供的队列实现，类似于List。
Map实现类用于保存具有映射关系的数据（key-value）。
Set、List和Map可以看做集合的三大类。
List集合是有序集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问。
Set集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问（也是不能集合里元素不允许重复的原因）。
Map集合中保存Key-value对形式的元素，访问时只能根据每项元素的key来访问其value。
对于Set、List和Map三种集合，最常用的实现类分别是HashSet、ArrayList和HashMap三个实现类
要点2：
两种遍历集合的方法Iterator接口和foreach循环
Iterator it = books.iterator(); while(it.hasNext()) { //未使用泛型，需要强制转换 String book = (String)it.next(); System.out.println(book); if (book.equals("Struts2权威指南")) { it.remove(); //使用Iterator迭代过程中，不可修改集合元素,下面代码引发异常 //books.remove(book); } //对book变量赋值，不会改变集合元素本身 book = "测试字符串"; }
/** * 集合转换为一维数组 */ public void listToArray() { // 创建List并添加元素 List<String> list = new ArrayList<String>(); list.add("1"); list.add("3"); list.add("4"); // 利用froeach语句输出集合元素 System.out.println("----2----froeach语句输出集合元素"); for (String x : list) { System.out.println(x); } // 将ArrayList转换为数组 Object s[] = list.toArray(); // 利用froeach语句输出集合元素 System.out.println("----2----froeach语句输出集合转换而来的数组元素"); for (Object x : s) { System.out.println(x.toString()); // 逐个输出数组元素的值 } }
要点3： Set
Set集合不允许重复元素，是因为Set判断两个对象相同不是使用==运算符，而是根据equals方法。(不同子类还有新的扩展，例如HashSet比较元素还需要比较Hashcode)即两个对象用equals方法比较返回true，Set就不能接受两个对象。
public class TestSet { public static void main(String[] args) { Set<String> books = new HashSet<String>(); //添加一个字符串对象 books.add(new String("Struts2权威指南")); //再次添加一个字符串对象， //因为两个字符串对象通过equals方法比较相等，所以添加失败，返回false boolean result = books.add(new String("Struts2权威指南")); System.out.println(result); //下面输出看到集合只有一个元素 System.out.println(books); } }
结果：
false
[Struts2权威指南]
程序中，book集合两次添加的字符串对象明显不是一个对象（程序通过new关键字来创建字符串对象），当使用==运算符判断返回false，使用equals方法比较返回true，所以不能添加到Set集合中，最后只能输出一个元素。
要点4： HashSet :
HashSet按Hash算法来存储集合的元素，因此具有很好的存取和查找性能。
HashSet的特点：
（1）HashSet不是同步的，多个线程访问是需要通过代码保证同步
（2）集合元素值可以使null。
HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode（）方法返回值也相等。所以有必要对两个方法都重写，而且注意规则，equals方法比较的属性一定要是用常量属性，防止出现对象属性修改后，出现set集合中出现相同元素。
//类A的equals方法总是返回true,但没有重写其hashCode()方法 class A { public boolean equals(Object obj) { return true; } } //类B的hashCode()方法总是返回1,但没有重写其equals()方法 class B { public int hashCode() { return 1; } } //类C的hashCode()方法总是返回2,并重写其equals()方法 class C { public int hashCode() { return 2; } public boolean equals(Object obj) { return true; } } public class TestHashSet { public static void main(String[] args) { HashSet<Object> books = new HashSet<Object>(); //分别向books集合中添加2个A对象，2个B对象，2个C对象 books.add(new A()); books.add(new A()); books.add(new B()); books.add(new B()); books.add(new C()); books.add(new C()); System.out.println(books); } }
程序运行结果：
[B@1, B@1, C@2, A@b5dac4, A@9945ce]
说明：
（1）Object类提供的toString方法总是返回该对象实现类的类名+@+hashCode(16进制数）值，所以可以看到上面程序输出的结果。可以通过重写toString方法来输出自己希望的形式。
（2）即使2个A对象通过equals比较返回true，但HashSet依然把它们当成2个对象；即使2个B对象的hashCode（）返回相同值，但HashSet依然把它们当成2个对象。由于C即equals和hashCode都重写了，才能准确判断元素相同。如果把一个对象放入HashSet中时，如果重写该对象equals（）方法，也应该重写其hashCode（）方法。要不就都不重写 。
关于equals 和hashcode :http://blog.csdn.net/chinayuan/article/details/3345559
hash算法的功能：
它能保证通过一个对象快速查找到另一个对象。hash算法的价值在于速度，它可以保证查询得到快速执行。
当需要查询集合中某个元素时，hash算法可以直接根据该元素的值得到该元素保存位置，从而可以让程序快速找到该元素。
当从HashSet中访问元素时，HashSet先计算该元素的hashCode值（也就是调用该对象的hashCode（））方法的返回值），然后直接到该hashCode对应的位置去取出该元素。
即也是快速的原因。HashSet中每个能存储元素的“曹位（slot）”通常称为“桶（bucket）”，如果多个元素的hashCode相同，但它们通过equals（）方法比较返回false，就需要一个“桶”里放多个元素，从而导致性能下降。
注：当向HashSet中添加一个可变对象后，并且后面程序修改了该可变对象的属性，可能导致它与集合中其他元素相同，这就可能导致HashSet中包含两个相同的对象。
所以要注意规则，equals方法比较的属性一定要是用常量属性，防止出现对象属性修改后，出现set集合中出现相同元素。
要点5： TreeSet:
TreeSet 的排序 ：
1.TreeSet是SortedSet接口的唯一实现，TreeSet可以确保集合元素处于排序状态（元素是有序的,采用自然排序）。
2.TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间大小关系，然后将集合元素按升序排列，这种方式就是自然排序。
（例如obj1.comparTo(obj2),如果该方法返回0，则表明这两个对象相等；如果返回一个正整数，则表明obj1大于obj2；如果该方法返回一个负整数，则表明obj1小于obj2.）
TreeSet 的比较重复元素 ：
1. 两个对象通过equals方法比较返回false，或通过compareTo（Object obj）比较没有返回0 ,则TreeSet 会把两个元素看作不同的元素。
2. 总结：当需要把一个对象放入TreeSet中时，重写该对象对应类的equals()方法时，应保证该方法与compareTo(Object obj)方法有一致结果，其规则是：如果两个对象通过equals方法比较返回true时，这两个对象通过compareTo（Object obj）方法比较应返回0.
而且注意规则，equals方法比较的属性一定要是用常量属性，防止出现对象属性修改后，出现set集合中出现相同元素。
TreeSet提供的几个额外方法：
public class TestTreeSetCommon { public static void main(String[] args) { TreeSet<Integer> nums = new TreeSet<Integer>(); //向TreeSet中添加四个Integer对象 nums.add(5); nums.add(2); nums.add(10); nums.add(-9); //输出集合元素，看到集合元素已经处于排序状态 System.out.println(nums); //输出集合里的第一个元素 System.out.println(nums.first()); //输出集合里的最后一个元素 System.out.println(nums.last()); //返回小于4的子集，不包含4 System.out.println(nums.headSet(4)); //返回大于5的子集，如果Set中包含5，子集中还包含5 System.out.println(nums.tailSet(5)); //返回大于等于-3，小于4的子集。 System.out.println(nums.subSet(-3 , 4)); } } 程序运行结果： [-9, 2, 5, 10] -9 10 [-9, 2] [5, 10] [2]
TreeSet 添加元素过程：
1. 添加第一个元素，无须判断，直接加入。
2 . 添加第二个元素，先判断是否是于前一元素相同，相同则不插入。
3. 根据compareTo()判断插入位置，此时不应该出现等于0的情况，应该按照规则让compareTo和equals方法保持一直。
HashSet 和 TreeSet 使用选择：
哈希表在进行插入、删除、查找这样的操作是很快的，其时间复杂度是常数级O(1)；平衡二叉树虽然插入、删除操作比较麻烦（需要O(log n)的代价），但进行遍历和排序却很快。选择完全在于用户的侧重点，但由于类型转换的方便性，通常我们用哈希表构造一个集合以后，再把它转换成相应的树集进行遍历，以获得较好的效果。
Set set1 = new HashSet(); set1.add(elem1);// 通过插入元素构造集合 set1.add(elem2); set1.add(elem3); Set set2 = new TreeSet(set); Iterator all = set2.iterator(); while (all.hasNext()) {// 遍历集合 all.next(); ... }
要点6： List :
1、List接口和ListIterator接口
List作为Collection接口的子接口，可以使用Collection接口里的全部方法。List是有序集合，所以List集合里增加了一些根据索引来操作集合元素的方法：
-
void add(int index, Object element):将元素element插入在List集合的index处。
-
boolean addAll(int index, Collection c):将集合c所包含的所有元素都插入在List集合的index处。
-
Object get(int index):返回集合index索引处的元素。
-
int lastIndexOf(Object o):返回对象o在List集合中最后一次出现的位置索引。
-
Object remove(int index):删除并返回index索引处的元素。
-
Object set(int index, Object element):将index索引处的元素替换成element对象，返回新元素。
-
List subList(int fromIndex, int toIndex):返回从索引fromIndex（包含）到索引toIndex（不包含）处所有集合元素组成的子集合。
List集合可以根据索引来插入、替换和删除集合元素。
关于使用List集合的几点建议：
- 如果需要遍历List集合元素，对应ArrayList、Vector集合，则应该使用随机访问方法（get）来遍历集合元素，这样性能更好。对应LinkedList集合，则应采用迭代器（Iterator）来遍历集合元素。
- 如果需要经常执行插入、删除操作来改变Lst集合大小，则应该使用LinkedList集合，而不是ArrayList。
- 如果多条线程需要同时访问List集合中的元素，可以考虑使用Vector这个同步实现。
要点7：ArrayList和Vector实现类
ArrayList(线程不安全)和Vector(线程安全)作为List类的两个典型实现，完全支持前面介绍的List接口全部功能。
ArrayList和Vector类都是基于数组实现的List类，他们封装了一个动态再分配的Object[]数组。每个ArrayList或Vector对象有一个capacity属性，表示它们所封装的Object[]数组的长度。capacity会添加元素的个数而自动增加。当向集合中添加大量元素时，可以使用ensureCapacity方法一次性地增加capacity。这可以减少增加重分配次数，从而提供性能。capacity大小也可以在创建时就指定，该属性默认为10.
ArrayList和Vector提供如下两个方法来操作capacity属性：
- void ensureCapacity(int minCapacity):将ArrayList或Vector集合的capacity增加minCapacity。
- void trimToSize()：调整ArrayList或Vector集合的capacity为列表当前大小。程序可调用该方法来减少ArrayList或Vector集合对象存储空间。
Vector还提供了一个Stack子类，它用于模拟了”栈“这种数据结构，
- Object peek():返回”栈“的第一个元素，但并不将该元素”pop“出栈。
- Object pop():返回”栈“的第一个元素，并将该元素”pop“出栈。
- void push(Object item):将一个元素”push“进栈，最后一个进”栈“的元素总是位于”栈“顶。
Arraylist 线程不安全解释：
ArrayList 类，在添加一个元素的时候，它可能会有两步来完成：
1. 在 Items[Size] 的位置存放此元素；2. 增大 Size 的值。
要点8：LinkedList实现类
List还有一个LinkedList的实现，它是一个基于链表实现的List类，对于顺序访问集合中的元素进行了优化，特别是当插入、删除元素时速度非常快。因为LinkedList即实现了List接口，也实现了Deque接口（双向队列），Deque接口是Queue接口的子接口，它代表一个双向列表，Deque接口里定义了一些可以双向操作队列的方法：
- void addFirst(Object e)：将制定元素插入该双向队列的开头。
- void addLast(Object e)：将制定元素插入该双向队列的末尾。
- Iterator descendingIterator()：返回以该双向队列对应的迭代器，该迭代器将以逆向顺序来迭代队列中的元素。
- Object getFirst()：获取、但不删除双向队列的第一个元素。
- Object getLast(): 获取、但不删除双向队列的最后一个元素。
- boolean offerFirst(Object e): 将指定的元素插入该双向队列的开头。
- boolean offerLast(Object e): 将指定的元素插入该双向队列的末尾。
- Object peekFirst(): 获取、但不删除该双向队列的第一个元素：如果此双端队列为空，则返回null。
- Object peekLast()：获取、但不删除该双向队列的最后一个元素：如果此双端队列为空，则返回null。
- Object pollFirst()：获取、并删除该双向队列的第一个元素：如果此双端队列为空，则返回null。
- Object pollLast()：获取、并删除该双向队列的最后一个元素：如果此双端队列为空，则返回null。
- Object pop()：pop出该双向队列所表示的栈中第一个元素。
- void push(Object e):将一个元素push进该双向队列所表示的栈中（即该双向队列的头部）。
- Object removerFirst()：获取、并删除该双向队列的最后一个元素。
- Object removeFirstOccurrence(Object o)：删除该双向队列的第一次的出现元素o。
- Object removeLast():获取、并删除该双向队列的最后一个元素。
- Object removeLastOccurrence(Object o)：删除该双向队列的最后一次出现的元素o。
从上面方法中可以看出，LinkedList不仅可以当成双向队列使用，也可以当成“栈”使用。同时，LinkedList实现了List接口，所以还被当成List使用。
要点9：MAP接口的使用
Map用于保存具有映射关系的数据（key-vlaue）。Map的key不允许重复，即同一个Map对象的任何两个key通过equals方法比较总是返回false
put(Object key, Object value):添 加一个key-value对，如果当前Map中已有一个与该key相等的key-value对，则新的key-value对会覆盖原来的key-value对。
Map中包含了一个keySet()方法，用于返回Map所以key组成的Set集合。
Map中包括一个内部类：Entry。该类封装了一个key-value对，Entry包含三个方法：
- Object getkey():返回该Entry里包含的key值。
- Object getValue():返回该Entry里包含的value值。
- Object setValue():设置该Entry里包含的value值，并返回新设置的value值。
可以把Map理解成一个特殊的Set，只是该Set里包含的集合元素是Entry对象，而不是普通对象。
要点10：HashMap和Hashtable实现类
- Hashtable是一个线程安全的Map实现，但HashMap是线程不安全的实现，所以HashMap比Hashtable的性能高些；但如果多线程访问同一个Map对象，使用Hashtable实现类更好。
- Hashtable不允许使用null作为key和value，如果为null，则引发NullPointerException异常；但HashMap可以使用null作为key或value。
由于HashMap里的可以不能重复，所以HashMap里最多只有一对key-value值为null，但可以有无数多项key-value对的value为null。
HashMap、Hashtable判断两个key相等的标准是：两个key通过equasl方法比较返回ture,两个key的hashCode值相等。
HashMap 子类 --LinkedHashMap类
HashMap有一个子类：LinkedHashMap,它也是双向链表来维护key-value对的次序，该链表定义了迭代顺序，该迭代顺序与key-value对的插入顺序保持一致。
LinkedHashMap可以避免对HashMap、Hashtable里的key-value对进行排序（只要插入key-value对时保持顺序即可）。
LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能，但在迭代访问Map里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。
HashTble 子类--Properties类
Properties类是Hashtable类的子类，用于处理属性文件（例如Windows操作平台上的ini文件）。Properties类可以把Map对象和属性文件关联起来，从而可以把Map对象中的key-value对写入属性文件，也可以把属性文件中的属性名=属性值加载到Map对象中。由于属性文件里的属性名、属性值只能是字符串类型，所以Properties里的key、value都是字符串类型，该类提供了如下三个方法来修改Properties里的key、value值。
- String getProperty(String key):获取Properties中指定属性名对应的属性值，类似于Map的get(Object key)方法。
- String getProperty(String key, String defaultValue):该方法与前一个方法基本类似。该方法多一个功能，如果Properties中不存在指定key时，该方法返回默认值。
- Object setProperty(String key、String value):设置属性值，类似Hashtable的put方法。
提供两个读、写属性文件的方法：
- void load(InputStream inStream):从属性文件（以输入流表示）中加载属性名=属性值，把加载到的属性名=属性值对追加到Properties里（由于Properties是Hashtable)的子类，它不保证key-value对之间的次序）。
- void Store(OutputStream out, String comment):将Properties中的key-valu对写入指定属性文件（以输出流表示）。
HashMap和Hashtable 区别
1、 继承和实现区别
Hashtable是基于陈旧的Dictionary类，完成了Map接口；HashMap是Java 1.2引进的Map接口的一个实现（HashMap继承于AbstractMap,AbstractMap完成了Map接口）。
2、 线程安全不同
HashTable的方法是同步的，HashMap是未同步，所以在多线程场合要手动同步HashMap。
HashMap 线程安全问题：
http://www.iteye.com/topic/656670
3、 对null的处理不同
HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。即 HashTable不允许null值其实在编译期不会有任何的不一样，会照样执行，只是在运行期的时候Hashtable中设置的话回出现空指针异常。 HashMap允许null值是指可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断。
4、 方法不同
HashTable有一个contains(Object value)，功能和containsValue(Object value)功能一样。
5、HashTable使用Enumeration，HashMap使用Iterator。
6、HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
7、哈希值的使用不同，HashTable直接使用对象的hashCode，代码是这样的：
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
而HashMap重新计算hash值，而且用与代替求模：
int hash = hash(k);
int i = indexFor(hash, table.length);
static int hash(Object x) {
int h = x.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
static int indexFor(int h, int length) {
return h & (length-1);
}
要点11：SortedMap接口和TreeMap实现类
Map接口派生了一个SortedMap子接口，TreeMap为其实现类。类似TreeSet排序，TreeMap也是基于红黑树对TreeMap中所有key进行排序，从而保证TreeMap中所有key-value对处于有序状态。TreeMap两种排序方法：
- 自然排序：TreeMap的所有key必须实现Comparable接口，而且所有key应该是同一个类的对象，否则将会抛出ClassCastExcepiton异常。
- 定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeＭap中所有key进行排序。采用定制排序时不要求Map的key实现Comparable接口。
TreeMap中判断两个key相等的标准也是两个key通过equals比较返回true，而通过compareTo方法返回0，TreeMap即认为这两个key是相等的。
如果使用自定义的类作为TreeMap的key，应重新该类的equals方法和compareTo方法时应有一致的返回结果：即两个key通过equals方法比较返回true时，它们通过compareTo方法比较应该返回0。如果equals方法与compareTo方法的返回结果不一致，要么该TreeMap与Map接口的规则有出入（当equals比较返回true,但CompareTo比较不返回0时），要么TreeMap处理起来性能有所下降（当compareTo比较返回0，当equals比较不返回true时）
要点12： java泛型的使用
集合中存储的数据必须是对象，不能存基本数据类型，所以引入泛型，可以具体说明存的对象类型具体是什么？
泛型（Generic type 或者 generics）是对 Java 语言的类型系统的一种扩展，以支持创建可以按类型进行参数化的类。可以把类型参数看作是使用参数化类型时指定的类型的一个占位符，就像方法的形式参数是运行时传递的值的占位符一样。
可以在集合框架（Collection framework）中看到泛型的动机。例如，Map 类允许您向一个 Map 添加任意类的对象，即使最常见的情况是在给定映射（map）中保存某个特定类型（比如 String）的对象。
因为 Map.get() 被定义为返回 Object，所以一般必须将 Map.get() 的结果强制类型转换为期望的类型，如下面的代码所示：
Map m = new HashMap();
m.put("key", "blarg");
String s = (String) m.get("key");
要让程序通过编译，必须将 get() 的结果强制类型转换为 String，并且希望结果真的是一个 String。但是有可能某人已经在该映射中保存了不是 String 的东西，这样的话，上面的代码将会抛出 ClassCastException。
理想情况下，您可能会得出这样一个观点，即 m 是一个 Map，它将 String 键映射到 String 值。这可以让您消除代码中的强制类型转换，同时获得一个附加的类型检查层，该检查层可以防止有人将错误类型的键或值保存在集合中。这就是泛型所做的工作。
泛型的好处
Java 语言中引入泛型是一个较大的功能增强。不仅语言、类型系统和编译器有了较大的变化，以支持泛型，而且类库也进行了大翻修，所以许多重要的类，比如集合框架，都已经成为泛型化的了。这带来了很多好处：
类型安全。 泛型的主要目标是提高 Java 程序的类型安全。通过知道使用泛型定义的变量的类型限制，编译器可以在一个高得多的程度上验证类型假设。没有泛型，这些假设就只存在于程序员的头脑中（或者如果幸运的话，还存在于代码注释中）。
Java 程序中的一种流行技术是定义这样的集合，即它的元素或键是公共类型的，比如“String 列表”或者“String 到 String 的映射”。通过在变量声明中捕获这一附加的类型信息，泛型允许编译器实施这些附加的类型约束。类型错误现在就可以在编译时被捕获了，而不是在运行时当作 ClassCastException 展示出来。将类型检查从运行时挪到编译时有助于您更容易找到错误，并可提高程序的可靠性。
消除强制类型转换。 泛型的一个附带好处是，消除源代码中的许多强制类型转换。这使得代码更加可读，并且减少了出错机会。
尽管减少强制类型转换可以降低使用泛型类的代码的罗嗦程度，但是声明泛型变量会带来相应的罗嗦。比较下面两个代码例子。
该代码不使用泛型：
List li = new ArrayList();
li.put(new Integer(3));
Integer i = (Integer) li.get(0);
该代码使用泛型：
List<Integer> li = new ArrayList<Integer>();
li.put(new Integer(3));
Integer i = li.get(0);
泛型类：
public class Test<T> { private T name; public T getName() { return name; } public void setName(T name) { this.name = name; } public static void main(String[] args) { Test<String> stringTest = new Test<String>(); stringTest.setName("aaa"); System.out.println(stringTest.getName()); Test<Integer> integerTest = new Test<Integer>(); integerTest.setName(1111); System.out.println(integerTest.getName()); } }
要点13： ArrayList , HashMap , HashSet 源代码及详解
http://zhangshixi.iteye.com/blog/674856
1. ArrayList概述：
ArrayList是List接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。
每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。
注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。
2. ArrayList的实现：
对于ArrayList而言，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。
HashpMap 原理
参考：http://www.importnew.com/7099.html
- hashing的概念
- HashMap中解决碰撞的方法
- equals()和hashCode()的应用，以及它们在HashMap中的重要性
- 不可变对象的好处
- HashMap多线程的条件竞争
- 重新调整HashMap的大小
1. HashMap概述：
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
2. HashMap的数据结构：
在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
源码如下：
可以看出，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。
3. HashMap的存取实现：
1) 存储：
从上面的源代码中可以看出：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。
addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的i索引处。addEntry 是HashMap 提供的一个包访问权限的方法，代码如下：
当系统决定存储HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。
另一种解释：http://jingyan.baidu.com/article/90895e0f92777e64ec6b0b92.html
（PUT）
现在我们一步一步来分析上面的代码。
对key做null检查。如果key是null，会被存储到table[0]，因为null的hash值总是0。
key的hashcode()方法会被调用，然后计算hash值。hash值用来找到存储Entry对象的数组的索引。有时候hash函数可能写的很不好，所以JDK的设计者添加了另一个叫做hash()的方法，它接收刚才计算的hash值作为参数。如果你想了解更多关于hash()函数的东西，可以参考：hashmap中的hash和indexFor方法
indexFor(hash,table.length)用来计算在table数组中存储Entry对象的精确的索引。
在我们的例子中已经看到，如果两个key有相同的hash值(也叫冲突)，他们会以链表的形式来存储。所以，这里我们就迭代链表。
· 如果在刚才计算出来的索引位置没有元素，直接把Entry对象放在那个索引上。
· 如果索引上有元素，然后会进行迭代，一直到Entry->next是null。当前的Entry对象变成链表的下一个节点。
· 如果我们再次放入同样的key会怎样呢？逻辑上，它应该替换老的value。事实上，它确实是这么做的。在迭代的过程中，会调用equals()方法来检查key的相等性(key.equals(k))，如果这个方法返回true，它就会用当前Entry的value来替换之前的value
(GET)
当你理解了hashmap的put的工作原理，理解get的工作原理就非常简单了。当你传递一个key从hashmap总获取value的时候：
对key进行null检查。如果key是null，table[0]这个位置的元素将被返回。
key的hashcode()方法被调用，然后计算hash值。
indexFor(hash,table.length)用来计算要获取的Entry对象在table数组中的精确的位置，使用刚才计算的hash值。
在获取了table数组的索引之后，会迭代链表，调用equals()方法检查key的相等性，如果equals()方法返回true，get方法返回Entry对象的value，否则，返回null。
要牢记以下关键点：
· HashMap有一个叫做Entry的内部类，它用来存储key-value对。
· 上面的Entry对象是存储在一个叫做table的Entry数组中。
· table的索引在逻辑上叫做“桶”(bucket)，它存储了链表的第一个元素。
· key的hashcode()方法用来找到Entry对象所在的桶。
· 如果两个key有相同的hash值，他们会被放在table数组的同一个桶里面。
· key的equals()方法用来确保key的唯一性。
· value对象的equals()和hashcode()方法根本一点用也没有。
1. HashSet概述：
HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。
2. HashSet的实现：
对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成，
未完 ： 集合框架的底层实现， 与array的关系。 效率比较， 实战使用情况。