在Java面试过程中，最常见到的问题当属HashMap的那些知识点。它的底层是什么结构？什么是Hash排序？发生了碰撞会怎样？它跟HashTable，ConcurrentHashMap有什么区别？现有的数组存储满了会发生什么？...很多时候，它就是一场面试的起点。所以源码阅读的第一站选择了这个类，从这里能够解析出来的东西还是很多。
阅读源码也是需要耐心和策略的，每个人目的不一样，有的人带着bug来看源码，有的人就带着面试的问题来找答案，我是想自己能够尽量地深入这个类，以此作为起点，挖掘出更多相关联点，再用关联到的点继续挖掘其它的点，以此类推，这很像一个爬虫的过程。说个题外话，阅读源码也需要基础，技巧和经验，就目前我的感觉，初看源码时，先不必过多属性和方法的修饰关键词，先看结构，看流程，到看细节时，根据规范和多线程的环境，再去分析为什么有这些修饰符；另外，在做一个问题的研究，必然会牵扯到很多其它的问题，那么在查找解决方案和问题的解释时，分支搜索必须为主搜索的理解做服务，不能过于深入搜索，必须要以研究的问题为核心，不能被带偏，分支中理出来的问题可以记下，后续研究时再做深入地解读。
在这里，我选择先看jdk1.7中的HashMap，之后再看1.8中的HashMap来进行对比。对它的整体结构，属性，方法，内部类，api实现，和一些常见的面试问题做个分析之后，再对这两个版本的jdk做个比较。这一遍，重在理解过程，要搞清楚发生了什么，并记录下关联的点，作为后续研究的目录。
>>首先，看几个构造函数，HashMap()，HashMap(int initialCapacity)都指向到了HashMap(int initialCapacity, float loadFactor)。
- DEFAULT_INITIAL_CAPACITY表示Map的初始容量，DEFAULT_LOAD_FACTOR为负载因子。除了对不符合要求的参数做了抛出异常的处理外，注意到初始容量专门用位运算保证了必为2的幂次方，这对后期的扩容判定是有影响的。
- threshold定义了一个界限，一般是Capacity*laoder的计算结果，Loader实际上是一个平衡哈希算法对于空间大小和散列度的参数（loader太小，则少量的元素就要求扩容，不容易发生碰撞；而loader太大，则大量的元素会堆积在小空间里，空间节省了，但是散列碰撞发生频率会变高；官方推荐使用默认值0.75f），超过了这个界限，底层的数组Entry[capacity]就需要进行一次扩容；当期元素个数到达最大容量1<<30时，直接将threshold设置为Integer.MAX_VALUE，不再进行扩容。
- useAltHashing是一个布尔参数，当满足条件时（默认为VM已启动且数组容量大于Holder.ALTERNATIVE_HASHING_THRESHOLD，默认为最大int值，即不会使用该算法），会针对字符型的key值使用专门的哈希算法以降低碰撞几率。
>>接着，看看上文提到的Holer类。
- 从提供给其它方法的参数来看，它只提供了ALTERNATIVE_HASHING_THRESHOLD与HASHSEED_OFFSET。前者用于判断是否使用AltHashing，从代码上看，应该可以通过设置一个系统变量jdk.map.althashing.threshold的值来影响它的大小，但没有实践过，后续可以做个测试；后者是计算hash值的种子。关于该类的作用，有解释为：由于虚拟机启动时类太多，如果内部类引用了还未被载入的类或者值会报错，holder即先赋予他们值，等虚拟机加载完成，用isBooted()去覆盖这部分值。这个过程牵扯到JVM的启动，暂时不做深入讨论。
>>另一个构造函数，HashMap(Map<? extends K, ? extends V> m)。
- 首先是根据m的容量来确定新的数组的容量，根据HashMap中默认的负载因子来计算新的capacity大小，由于int型变量会将计算的小数直接舍掉，为了保证capacity*loader能够满足m的元素个数，需要加1。容量计算好了，后续就不存在扩容的问题，所以第二步直接采用了putAllForCreate(m)方法将原有的每一对键值进行插放。
在putAllForCreate(m)中需要重点关注几个问题，一是对key==null时的处理，二是数组下标的计算indexFor(hash, table.length)函数，三是链表数组中元素的遍历逻辑以及跳过resize判断的插入createEntry(int hash, K key, V value, int bucketIndex)。
- 在HashMap中对key==null的Entry做了一系列特殊处理（putForNullKey,getForNullKey），hash值直接置为0。要注意的是，在hash==0的处理策略下，key==null的元素一定置于table[0]的位置，但不一定在链表第一的位置。
- 在indexfor中，根据key计算的hash值与table.length-1做了一次与运算。由于table.length是2的幂次方，所以减一必定为一个全位为1，大小为length-1的二进制数，hash(key)与这样的数进行与运算，结果会保留table.length-1最大长度的原始hash结果，并且小于这个数组的size，设计地很巧妙。
- 由于indexFor函数已经确定了一个元素置于当前数组的具体位置，所以接下来就是将该元素插进链表。分为两步，第一是判断该链表中是否有相同元素的存在，如果有，直接返回该元素的value；第二步即加入链表，这里看createEntry(int hash, K key, V value, int bucketIndex)比较清楚的是，新的元素进入被直接放入了表头的位置，原先该位置的元素table[index]被放在了新元素的后面，与新元素的next相关联。
>>其实，上述的几个函数已经包含了put的主要逻辑，接下来就看看put与addEntry与之前的不同，以及resize的主要过程。
- put中，逻辑与putForCreate基本相同，但增加的元素是通过addEntry函数来加入，与createEntry相比，主要多的就是一个resize的判断和实现。
- resize中，有个判断，就是现有的这个数组容量是否已经达到上限，如果是，返回，并将threshold调置最大，这样之后的扩容判断size>=threshold就不会通过，避免了后续调用。接下来useAltHashing，capacity以及ALTERNATIVE_HASHING_THRESHOLD共同决定了是否需要对新数组的key进行key的hash重算，如果useAltHashing值由false变为true，那么当次重算，但下一次扩容操作中，就不会发生重算（（rehase=true^true）==false），这也是需要注意的（在useAltHashing为true之前与之后各用了不同的hash算法，而且只在useAltHashing变化的那一次改变了hash算法，所以这里用异或进行判断也是比较巧妙的）。重排需要将之前所有的index重新计算，并安放Entry，所以说，如果预先知道这个hashmap的规模，最好给定一个大概的初始值，不至于在不断put的过程中多次扩容，损失性能。
>>关于put还有一个putAll(Map<? extends K, ? extends V> m)函数。
- 用m的size与当前的threshold进行比对，如果大于这个界限，则主动调整数组的大小，其中对newCapacity的移位翻倍，并与targetCapacity比较，调整到合适的大小，再进行依次存放。这样做的目的，是避免了新map元素个数远大于当前HashMap的大小带来的多次扩容，这种写法，扩容最多发生1次。
>>在put过程中，有个参数modCount，它的作用是为了触发fast-fail
- 可以看到，put,remove以及衍生出来的方法中都会有modCount++这个操作，modCount被拿来比对是在HashIterator<E>中，这样做的目的是当发现在采用迭代器进行遍历的时候，如果有存，删等操作，不必等到迭代完全结束再返回错误，而是立即抛出异常(ConcurrentModificationException)。容易想到，多线程中如果一个线程对该HashMap对象进行增，删，另一个线程对其进行迭代遍历就会触发这个异常。单线程中，如果一边迭代，一边进行增删操作，也是会触发到这个异常的：
HashMap<String, String> hmp = new HashMap<>(); hmp.put("1", "yi"); hmp.put("2", "er"); hmp.put("3", "san"); for (Map.Entry<String, String> entry : hmp.entrySet()) { hmp.remove(entry.getKey()); }
- 这个机制广泛存在于集合框架中。
>>get，contains系列相对比较简单，这里就不做赘述。
>>Entry<K,V>这个结构就是个链表，而HashMap中底层的结构就是一个数组，数组中要么为null，要么是这种链表。来一张图就可以说明（JDK1.7中的结构，在JDK1.8中的元素已经变为红黑树）
- 明白了底层的结构，基本就能够看着源码清楚它的插入，删除，遍历等流程。Entry中的属性，唯一不会变的就是key值，next在插入时都有可能变化，value在相同key值进入HashMap时会被新值覆盖，hash值会在hash算法发生更改时变化，唯一不会变的就是key值。
- HashMap提供了entrySet()方法，追溯到HashIterator类的nextEntry()，可以遍历出不包含空值的Entry<K,V>。而Entry<K,V>中有些public修饰的方法，可以拿来灵活使用。
>>HashMap提供了三种view的方法，一个是键keySet()，一个是values()，还有就是entrySet()。都在底层构造中继承了HashIterator类，而HashIterator又实现了Iterator接口，所以这几种集合都可以进行迭代。关于涉及到的Set,AbstractSet,以及Collection会在后续源码阅读中进行研究。而剩余的比较重要的readObject，writeObject以及clone方法会在研究序列化，克隆等问题中进行解读。
接下来的任务是阅读JDK1.8中的HashMap，并对其中重要的方法进行解读。