HashSet，存储object的集合，既然是集合，就不允许有重复元素。判断两个元素是否相同，是由hashCode与equals方法共同完成的。如果集合中对象的类没有重写这两个方法，那么就会使用从object继承的来的方法，即比较两个对象的引用是否相同，即比较地址。
HashSet使用什么数据结构来存储对象的呢，需要看一下源码
- private transient HashMap<E,Object> map;
- // Dummy value to associate with an Object in the backing Map
- private static final Object PRESENT = new Object();
- /**
- * Constructs a new, empty set; the backing HashMap instance has
- * default initial capacity (16) and load factor (0.75).
- */
- public HashSet() {
- map = new HashMap<E,Object>();
- }
这里可以看到，HashSet类维护了一个HashMap引用作为自己的成员变量。并在其构造方法中将其实例化。
另一个成员变量是一个静态，final的object，后面就看到它的作用是什么了。
HashMap表达了一种映射，即关键字key到值value的映射，其中key的值唯一，即一个key某一时刻只能映射到唯一的值。
之前在分析HashSet时，提出一个问题，如何保证元素的唯一性？我们知道要通过使用两个方法来实现，但是，最终是哪里使用的这两个方法呢？
现在来看一下HashSet的add方法
- public boolean add(E e) {
- return map.put(e, PRESENT)==null;
- }
正如我们看到的，add方法调用了HashMap的put方法。这里我们看到了之前的成员变量PRESENT，即，我们存入到HashSet的对象作为key传给了map，而我们不关心这个key对应的value，所以才定义了一个静态final的object对象。
而保证集合中元素的唯一性的工作，也就顺理成章的交给了HashMap对完成。
至此，我们可以大概明白HashSet的实现本质，它封装了一个HashMap。
------------------------------------------------------------------------------------------------
看来，重点还是在HashMap这个类上。
先看看其成员变量
- static final int DEFAULT_INITIAL_CAPACITY = 16;
- static final int MAXIMUM_CAPACITY = 1 << 30;
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- transient Entry[] table;
- transient int size;
- int threshold;
- final float loadFactor;
这个比起HashSet，成员变量多出不少。。
再对比下构造方法，先看下无参的
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
- table = new Entry[DEFAULT_INITIAL_CAPACITY];
- init();
- }
先不管这个loadFactor是神马，第四行我们可以看到，实例化了一个Entry型的数组，table是这个类里面为一个数组结构，我们有理由猜想，每对映射就是放在这里了。大小为默认初始大小。这个Entry是什么类型？
- static class Entry<K,V> implements Map.Entry<K,V> {
- final K key;
- V value;
- Entry<K,V> next;
- final int hash;
- /**
- * Creates new entry.
- */
- Entry(int h, K k, V v, Entry<K,V> n) {
- value = v;
- next = n;
- key = k;
- hash = h;
- }
-首先呢，这个Entry是HashMap的内部类。
如果看下他的成员变量，我们发现有key，value，还有一个Entry型引用next，这个next暂时不用管是做什么的。最后有一个final的int型变量hash。
-至此，我么知道Entry就是之前说的映射的具体实现。这个变量hash应该也是和key的hashcode有关的。下面我们就会看到。
我们现在最关心的方法是put。下面来分析。
- public V put(K key, V value) {
- if (key == null)
- return putForNullKey(value);
- int hash = hash(key.hashCode());
- int i = indexFor(hash, table.length);
- for (Entry<K,V> e = table[i]; e != null; e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- modCount ;
- addEntry(hash, key, value, i);
- return null;
- }
-貌似有些复杂，先看第4行，这里用到了key对象的hashCode，之后又用了一个叫做hash的方法对获得的key的hashcode又处理了一下
- 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其实是一个哈希函数。至于为什么这么定义，不知道了。。。。经验吧。
再回头看put方法，第五行，用了个indexFor方法，来获取一个下标，这个下标就是要放在table里的位置。
至此，我们可以马上想到数据结构中的哈希表了。哈希表中，用来计算某个元素将存在表里的位置的函数叫做哈希函数，但是，这里，indexFor并不是那个哈希函数，虽然它是最直接算出table中存储位置的函数。
-其实这个哈希函数由3部分共同完成，首先，是hashCode方法，然后通过hash方法，最后由indexFor算出数组中的下标.
- //找到对应链表
- for (Entry<K,V> e = table[i]; e != null; e = e.next) {
- Object k;
- //如果要插入的entry的key出现过，则替换成新插入entry的value，并返回oldValue
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- //为什么后面有个或？因为key类可能重写了hashcode与euqls方法
- //若果没有重写，那就是默认的用引用作为hashcode，即第一个判断
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
-代码这段，说明这里使用了链地址法作为处理冲突的方法。
不同key值可能计算出相同的哈希表下标，即位置，这是即产生了冲突。
如果算出的下标相同，那就加到对应的链表里。
-这里有个疑问，为什么不适用再哈希法来处理冲突呢？-
-前面提到的loadFactor就是我们数据结构课中提到的填充因子。即，当前填充率达到这个数值时，一般会增加哈希表的大小，这样做的目的是降低产生冲突的概率。
-所以在put方法中的add方法中，我们可以看到，当table里面填入的entry数量到达threshold时，table会被resize
resize中有个transfer方法，用来将旧的table的内容拷贝到新的table中。新的table的大小事旧的大小的2倍。
- void addEntry(int hash, K key, V value, int bucketIndex) {
- Entry<K,V> e = table[bucketIndex];
- table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
- if (size++ >= threshold)
- resize(2 * table.length);//扩容
- }
追踪resize方法
- void resize(int newCapacity) {
- Entry[] oldTable = table;
- int oldCapacity = oldTable.length;
- if (oldCapacity == MAXIMUM_CAPACITY) {//如果已达到 1 << 30,就无法再扩容了
- threshold = Integer.MAX_VALUE;
- return;
- }
- Entry[] newTable = new Entry[newCapacity];
- transfer(newTable); // 把当前table内容拷贝到新的table里
- table = newTable;
- threshold = (int)(newCapacity * loadFactor);//重新计算threshold
- }
由于还很菜，就只能分析到这里了。
总结下我的感想
其实，这是第一次去学习源码，虽然只是看懂了个皮毛，但是收获还是很大的。
仅仅停留在知道如何使用一个类，是不够的，因为如果你不了解他实现的原理，你就无法真正的用好它，因为你不确定在一些场景是否可以使用。
其次，研究源码真的是一个优秀程序员必须培养的习惯，通过阅读这些代码，可以学到很多东西，对自己的进步起着很大最用。无论是设计思路，或者是优秀的编程风格，都是值得学习的。
虽然以现在的水平，我仅仅能看个大概，但是只要这么一点一滴的积累，总会有很大进步的，不能着急。
--------------------
先写到这里吧，出去跑跑步，身体是革命的本钱.
