源码随记

近来研究了下struts2.2.1的源码，底层看到许多集合的应用，惊觉自己的Set和Map实在是理解的不到位，什么Set、Entry之类的都啥啥啥嘛，好了翻开书补补课，最后还是打开了jdk中HashMap的源码读了起来，这里简单记录下自己现下的理解。
首先我想从hashcode即散列码记起，援引Thinking in java作者的解释，使用散列码的目的是使用一个对象来查找另一个对象，其价值在于让查询得以快速进行，它是相对唯一的，用以代表对象的int值，它应是通过对象的某些信息进行转换生成的数值。
  HashMap应为Map实现中的默认选择主要是因为其对速度进行了优化，查询速度优于其他Map实现类。HashMap使用了散列码取代了对键的线性搜索（很慢）。

。。。我还是直接记录代码理解吧。。抄书好烦（虽然加深印象，抄给自己看的）

先看看属性

//默认的初始容量，需是2的次方
    static final int DEFAULT_INITIAL_CAPACITY = 16;

//最大容量，如果在构造中显式的指定此属性则必须小于1<<30 (2的30次方)
    static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

//Entry[]数组，个人理解为桶，当必要时会resize，长度必须是2的次方
    transient Entry[] table;

//map中存储的键值对数量
    transient int size;

//map中存储键值对的最大个数
    int threshold;

//负载因子
    final float loadFactor;

/**
*表示map被结构式修改的次数，结构式修改是指改变map中键值对的个数或者改变map的内部
*结构（例如调用rehash）。这个属性适用于HashMap的视图做迭代器时使用。
**/
    transient volatile int modCount;

HashMap提供了四个构造器

//这个构造器会被其他构造器调用。
    public HashMap(int initialCapacity, float loadFactor) {
//容量若小于零则抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
//容量若超过最大容量则按照最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
//判断负载因子，小于等于零或非数字，则抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
//通过迭代得到大于initialCapacity的最小的2的次方数
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        this.loadFactor = loadFactor;
//通过capacity和loadFactor得到threshold，可存储的键值对数量
        threshold = (int)(capacity * loadFactor);
//创建Entry数组，长度为capacity
        table = new Entry[capacity];
        init();
    }
//使用默认的负载因子调用上面构造方法
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

//使用默认的容量值和负载因子值得到threshold并创建Entry数组
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

//使用默认的负载因子，容量通过比较获得。调用putAllCreate()
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }

总结看来，构造中主要是为了得到threshold并且创建桶(Entry数组)。默认值在多构造器中的使用值得我学习。。

init()方法在每个构造其中都会被调用，这在HashMap源码中是个空实现方法。目前理解为子类设计的钩子方法，子类只需重写init()方法即可完成自定义的初始化行为。

有两个在类内被多次调用的方法hash()和indexFor()

//对传入的散列码进行位运算，以期能得到散列度更好的散列码
    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);
    }

//通过散列码和Entry数组的长度进行与运算得到该散列码对应的下标
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

hash()应该是对key的散列值进行进一步的散列，使得map中的value能够更好的分散在桶中，避免桶中个别Entry中value过多，而其他Entry中value很少的不相对均匀的情况，这样在查询也会降低查询速度。而这个方法的算法。。一堆移位、异或的位运算，我已经懒得细看或者看不懂了。。现下先理解到这个程度吧。注意：null的散列总是0，这样得到的数组下标也总是0

indexFor()的参数是hash(key.hashCode())和table.length，即key的散列码和Entry数组的长度，进行与运算后返回，保证返回的值不会发生数组下标越界这样的情况。

在学习put()和get()方法之前应该先了解下Entry，Entry是定义在接口Map中的接口，这样要使用Entry就要先实现写一个Entry的实现类，这个实现类在HashMap中是以静态内部类的形式出现的，因为后续的put和get方法都涉及到Entry的实现，这里应该先了解下这个实现类。

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

这个Entry类有四个属性和一个全参构造。key和value是要存储的键值对，hash应为key的散列码。next这个属性比较关键，它是Entry本身，即以本身的一个实例作为属性，这是之所以能形成Entry链的关键。这样在table中宏观看来只保存了个table.length个Entry实例，而实际每个Entry实例都可以看做是一个Entry链。保存了散列码相同但是key不相同（equals返回false或者!=）的若干Entry。

下面来看看比较关键的方法addEtry()

//添加Entry实例到table中的方法
    void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];//取出table中现有的Entry实例
//在该位置添加新的Entry实例
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//判断map中键值对的个数是否达到边界
        if (size++ >= threshold)
            resize(2 * table.length);//给table扩容并给threshold重新定义值
    }

从这段代码中可以看到Entry链的实现，取出该位置原有的Entry实例，将此实例作为参数传入Entry的构造中，这样原实例就成新实例的属性。这样的模式在put,get方法中被用来设计循环条件。参数中hash应为key的散列码。

put()方法以及put()中调用的私有方法putForNullKey()

    public V put(K key, V value) {
        if (key == null)//key==null的处理
            return putForNullKey(value);
        int hash = hash(key.hashCode());//得到key的散列码
        int i = indexFor(hash, table.length);//得到散列码应对应的数组下标
//遍历该Entry链进行判断处理
        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;
    }

/**
*遍历table[0],判断是否有key==null的Entry实例,若存在则用传入value替换原value并将
*原有value返回,若不存在null key则通过调用addEntry()将键值对放入table[0]的Entry链
**/
    private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

通过key的散列码得到应遍历的Entry链（Entry链全部置于数组table中），判断该key是否已经存在，若存在则取出原有的value，将传入的value赋给对应Entry，并将原有的value返回；若链中该key不存在，则通过调用addEntry()创建Entry实例，将实例加入到Entry链，返回null。

get()方法以及get()中调用的私有方法getForNullKey()

    public V get(Object key) {
        if (key == null) //key的空值判断
            return getForNullKey();
        int hash = hash(key.hashCode());//得到更完美的key的散列码
//调用indexFor()方法得到要查询的Entry遍历查询
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k; 
//判断散列码与key对象本身是否相等。
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

//key==null时调用，查询table[0]
    private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

通过getForNullKey()可以知道，HashMap中只会有一个key==null的键值对存在。
而循环中的判断条件e.hash == hash目前觉得不是很有必要，在同一个Entry链中所有的Entry的hash应该都是相同的，正因为相同才会被链在一起。。也可能是为了线程安全考虑。

。。先到这里了，类中方法很多，本人是初学者，读到哪里写到哪里。纯粹是写给自己加深印象的。
有心情了再写吧。。懒人确实不适合写blog，sigh..