源码阅读之Map和Set

HashSet是Set接口的实现，Set和List最明显的区别在于Set不允许重复元素，而List允许。Set为了做到不允许重复元素，采用的是基于HashMap来实现的
HashSet（）;
创建HashMap对象。
add(e);
调用HashMap的put(k,v);方法，将需要增加的元素作为map的key，而value则传入一个已有的Object常量。
remove（e）;
调用HashMap的remove方法
contains(e);
调用HashMap的containsKey（k）方法。
iterator();
调用HashMap的keySet方法来返回iterator，HashSet不能使用get(i)，来获取元素，只能通过iterator方式获得。

TreeSet和HashSet的主要区别在于，TreeSet对于排序的，TreeSet是基于TreeMap实现的。
TreeSet();
创建TreeMap对象。
add(e);
调用TreeMap的put(k,v);方法，将需要增加的元素作为map的key，而value则传入一个已有的Object常量。
remove（e）;
调用TreehMap的remove方法
contains(e);
调用TreeMap的containsKey（k）方法。
iterator();
调用TreeMap的keySet方法来返回iterator，HashSet不能使用get(i)，来获取元素，只能通过iterator方式获得。
可见，TreeSet和HashSet没有其他的区别。TreeSet在构建的时候，可以传入comparator接口的实现,descendingSet以及descendingIterator等类来自定义排序。
总结：
HashSet是基于HashMap实现，无限制容量
TreeSet是基于TreeMap实现，支持排序
HashSet，TreeSet都是非线程安全的





HashMap是Map中最常用的，具体实现方式如下。
HashMap();
将loadfactor设置成默认的0.75，threshold为12，并创建一个大小为16的Entry数组。可以通过HashMap的另外2个构造方法来控制初始化容量和loadfactor，至于创建的Entry数组的大小并非是初始化容量决定的，如下。

  // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

capacity才是真正的Entry数组的大小，即真实的Entry数组的大小应为大于initialCapacity的2的倍数。例如，调用new HashMap(5,0.6),那么按照HashMap的实现，则会将loadFactor的值设置为0.6，并且创建一个大小8的Entry数组threshold为4。

put（Object key,Object value）;
对于key为null的情况下，HashMap的做法是获取Entry数组的第一个对象，并基于Entry对象的next属性进行遍历，当找到其中的Entry对象的key为null时，则将其的value赋值成新的value，然后返回，如果没有Entry对象的key为null时，则增加一个Entry对象，增加时，先获取当前Entry数组的第一个Entry对象e,并创建Entry对象，key为null,value为新传入的对象，next为之前获得的e.如果此时的Entry数组已用的大小>=threshold，则将当前的数组，扩大为
当前大小的2倍，扩大时，为当前Entry的对象重新hash，并填充数组，重新设置threshold值。
对于Key不为null的情况下，首先获取当前对象的hashcode，然后在对hashcode进行hash操作，其代码为：

 static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

hash完毕后，将hash出来的值与当前Entry对象数组的大小减一的值进行按位与操作，从而得出当前key要存到数组的位置，从这个过程可以看出，可能会出现不用的key找到相同存储位置的问题，也就是数据结构中经典的hash冲突的问题。HashMap是这样解决的。
在找到要存储的目标数组的位置后，获取该数组的对应的Entry对象，通过Entry对象的next方法来遍历，寻找hash和计算出的hash值相等的，并且key相等或者equals的Entry对象。如果找到了，则替换该Entry的对象的值，完成put操作，返回oldValye。如果未找到，则往对应的数组对象添加新的Entry对象，增加时采取的方法和key为null的基本相同，只是它是替换指定位置的Entry对象，可以看出，hashMap解决hash冲突采取的是链表方式，而不是开放定址的方法。
get(Object key)
get的过程和put的一样，也是根据key是否为null来分别处理，对于key为null的情况，则直接获取数组的第一个Entry对象，并且基于next属性进行遍历，寻找key为null的Entry对象，如找到返回Entry对象的value,如未找到，返回null。
对于key不为null的情况，则对key进行hash按位于操作，找到其对象的存储位置，然后获取此位置的Entry对象，基于next属性进行遍历，寻找到hash值相等，并且key相等或者equals的Entry对象，返回其value,如未找到返回null。
remove(Object key)
remove的过程和get相似，只要在找到匹配的key后，如数组上的元素等于key，则将数组上元素的值改为其next元素的值；如数据上的元素不等于key，则对链表进行遍历，一直到找到匹配的key或链表为止。
containsKey（Object key）
通过调用getEntry方法来完成，getEntry方法和get方法相同，只是在找到匹配的key后，直接返回Entry对象，而containsKey判断返回的Entry对象是否为null,为null则返回false,反之返回true;
keySet();
在使用map时，经常会通过keySet来遍历hashMap，调用keySet方法会返回HashMap中定义的ketSet实例，此keySet继承了abstractSet。当调用iterator时，返回setIterator实例，调用next方法时，遍历整个数组以及Entry对象的链表。如果在遍历的过程中有添加和删除呀un苏会抛出，concurrentModificationException.
HashMap无法保证顺序，要保证顺序要使用TreeMap.
TreeMap是一个基于Map排序方式的实现，其实现方法和HashMap不同。
TreeMap()
此处的comparator的属性赋值为null，如希望控制TreeMap元素的存储顺序，可以使用带Comparator参数的构造器。
put(Object key,Object value)
当调用put方法时，首先判断root属性是否为null（root为TreeMap中维护的数组），如为空，则创建一个新的Entry对象，并且赋值给root属性，如果不为空，则首先判断是否传入了指定的Comparator实现，如已传入，则基于红黑树的方式遍历，基于comparator来判断key是应该放在树的左边还是右边，如找到相等的key，则直接替换其value,并返回结束操作，如没找到相等的key，则一直寻找从左边或者右边为null的元素。如Comparator实现为空，则判断key是否为null,是则抛出NullPoingException，并将key造型为Comparable，进行与上面同样的遍历和比较过程。通过以上步骤，如果未找到相同的key,则进入以下过程，创建一个新的Entry对象，并将其的parent设置成上面找到的元素，并根据和parent key比较的情况来设置parent的左右的属性。TreeMap是一个典型的基于红黑树的实现，因此他要求一定要有key的比较方法。要么传入comparator,要么key对象实现Comparable接口。
get(Object key)
treeMap在查找key的时就是一个典型的红黑树查找过程。从根对象开始比较，一直找到相等的key，并返回value.
和put时同样的处理方式，如未传入Comparator接口，当传入的Object为null时，在直接抛出NullPointException.
remove(Object key)
remove首先要做的是getEntry，然后则是将此Entry在红黑树上删除，并重新调整树上的相关的节点。
ContainsKey（object key）
和get一样，都通过getEntry方法，因此过程和get一样，只是containskey直接判断返回的Entry是否为null,为null则返回false,反之返回true.
keySet();
调用keySet方法后，返回TreeMap的内部类keySet对象的实例，iterator的遍历从根开始，基于红黑树的方式完成。
总结:
HashMap采取数组方式存取key，value构成Entry链表对象，无容量限制
HashMap基于key hash寻找Entry对象存到数组的位置，对于hash冲突采取链表方式来解决。
HashMap在插入数组时，可能要扩充容量，在扩大容量的时候必须要重新计算hash,并复制对象到新的数组中。
TreeMap基于红黑树实现，无容量限制。
HashMap，TreeMap是非线程安全的。
注意事项：
1. HashSet底层是使用HashMap实现的。当使用add方法将对象添加到Set当中时，实际上是将该对象作为底层所维护的Map对象的key，而value则都是同一个Object对象（该对象我们用不上）；
2. HashMap底层维护一个数组，我们向HashMap中所放置的对象实际上是存储在该数组当中；
3. 当向HashMap中put一对键值时，它会根据key的hashCode值计算出一个位置，该位置就是此对象准备往数组中存放的位置。
4. 如果该位置没有对象存在，就将此对象直接放进数组当中；如果该位置已经有对象存在了，则顺着此存在的对象的链开始寻找（Entry类有一个Entry类型的next成员变量，指向了该对象的下一个对象），如果此链上有对象的话，再去使用equals方法进行比较，如果对此链上的某个对象的equals方法比较为false，则将该对象放到数组当中，然后将数组中该位置以前存在的那个对象链接到此对象的后面。
5.

package com.collections;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class SetText {
	public static void main(String[] args) {
		Set set=new HashSet();
		System.out.println("Set第一次："+set.add("123"));
		System.out.println("Set第二次："+set.add("123"));
		System.out.println("=================");
		Map map=new HashMap();
		System.out.println("Map第一次:"+map.put("1", "1"));
		System.out.println("Map第二次:"+map.put("1", "1"));
	}
}

执行结果为：
Set第一次：true
Set第二次：false
=================
Map第一次:null
Map第二次:1
说明，如果把已有对象分别往Set和Map中放时，Set是不会继续放入，保留原有值，Map是覆盖原有值。

评论

1 楼 xiaguangme 2012-12-28  

“capacity才是真正的Entry数组的大小，即真实的Entry数组的大小应为大于initialCapacity的2的倍数。例如，调用new HashMap(5,0.6),那么按照HashMap的实现，则会将loadFactor的值设置为0.6，并且创建一个大小8的Entry数组threshold为4。 ”
创建的Entry的大小为10 吧