上两篇介绍的是List,从这一篇开始介绍Map，这个估计要写的比较多，这篇文章介绍一下HashMap.
HashMap是非常重要的，为什么呢？
将对象映射到其他对象的能力是一种解决问题的杀手锏。
根据马克思哲学原理，万事万物是具有普遍联系性的，加入我们需要联系两个事物，而且可以在众多同样的联系中快速定位到我们要找的那一个。
这是一个极其频繁的应用场景，而HashMap则就此应运而生。
(1)先看一下HashMap的成员吧(具体意思见注释)：
//默认初始容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //默认装载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //空表 static final Entry<?,?>[] EMPTY_TABLE = {}; //映射表，我们要操作的核心本体 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; //当前大小 transient int size; //临界值 int threshold; //装载因子 final float loadFactor; //修改次数 transient int modCount; //对于key是String的情况的默认临界值 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; //private static class Holder{}，这个东西再Java 8中被删除了 //一个随机值用来尽量避免哈希冲突 transient int hashSeed = 0;
说几个关键的：
第一：
Entry<K,V>.这个是Map容器的单元，也就是一个键值对(映射项)。Map.entrySet 方法返回映射的 collection 视图，其中的元素属于此类。获得映射项引用的唯一 方法是通过此 collection 视图的迭代器来实现。这些 Map.Entry 对象仅 在迭代期间有效。
通过查看Enrty接口的源码可以看到它的基本操作，可以通过EntrySet进行HashMap的遍历：
interface Entry<K,V> { K getKey(); V getValue(); V setValue(V value); boolean equals(Object o); int hashCode(); }
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } //后面的省略 }
再结合transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE，可知HashMap的底层是一个Entry<K,V>的数组，每个元素都是一个链表，由此可见JDK采用链地址法来避免哈希冲突。
这个可以从查找动作的源码中看出
final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }
根据hashcode定位到底层数组的元素，然后在以该元素为头结点的链表中查找Key.
第二：
影响HashMap性能的两个重要变量：初始容量和负载因子。
初始容量是指创建哈希哈希表中桶的位数，默认初始容量为16.
负载因子：当前尺寸/容量。空表的负载因子是0，而半满表的负载因子是0.5，以此类推。负载轻的表产生冲突的可能性小。HashMap提供了指定负载因子大小的构造器，当负载情况达到该负载因子的水平时，容器将自动增加其容量(桶的位数),实现的方法是使容量加倍，并重新将现有对象分布到新的桶位集中，这个过程称为再散列。
HashMap的默认负载因子是0.75，这个因子在时间和空间代价之间达到了平衡，更高的负载因子可以降低表所需的空间，但是会增加查找代价，这很重要，因为查找使我们最常用的操作。
如果你知道将要在HashMap中存储多少项，那么创建一个具有恰当大小的初始容量将可以避免自动再散列的开销。
接下来让我们看一下插入一个新元素的过程：
首先是put()操作：先在当前表中查找，如果有则返回，如果没有，则执行addEnrty()操作：
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); 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; }
addEnrty()函数：如果容量达到临界值，则执行resize()操作，此处传入的参数是resize(2 * table.length);从这里开始再散列的过程。完成后，执行createEntry()，该动作源码省略。
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }
resize()函数，建立一个容量为newCapacity的新的表，然后调用transfer()函数将所有元素从当前表移动到新的表，更新临界值：
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
此处体现了负载因子的作用。(transfer()函数非常简单，此处省略。)
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
(2)散列过程。
散列，为了更快速地查找。那么什么样的方法是一个好的哈希方法(散列方法)呢？
1.必须速度快
2.对于同一个对象，始终生成同一个哈希码，因此不要依赖于对象中的易变数据。
3.必须根据对象有代表意义的特征来进行哈希，
4.好的哈希方法产生的哈希码是分布均匀的，这样可以均衡负载，提高速度。
5.散列码没有必要是独一无二的，我们第一要求是速度而不是唯一性，因为我们可以通过hashcode()和equals()方法来完全确定对象身份。这点后面细说一下。
看一下HashMap()源码中的hash()方法：
final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // 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); }
从这里可以看出来：
String是调用特殊方法处理的，其余对通过hashcode()方法进行哈希。
至于后面的>>>运算(高位补零的右移运算)，是为了是哈希码中的1分布的更为均匀(满足上面第四点)，位运算体现了对快速的要求但是为什么选取20,12,7,4这四个参数，我没想清楚，也没查到，但相比一定是JDK研发人员精心设计的。
大家可以根据下面贴出的这段代码的注释思考一下，这是之前写“玩具编译器”时用到的哈希方法：UNIX系统中的elf_hash
// ELF Hash Function unsigned int ELFHash(char *str) { unsigned int hash = 0; unsigned int x = 0; while (*str) { hash = (hash << 4) + (*str++);//hash左移4位，把当前字符ASCII存入hash低四位。 if ((x = hash & 0xF0000000L) != 0) { //如果最高的四位不为0，则说明字符多余7个，现在正在存第7个字符，如果不处理，再加下一个字符时，第一个字符会被移出，因此要有如下处理。 //该处理，如果最高位为0，就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位 //因为1-4位刚刚存储了新加入到字符，所以不能>>28 hash ^= (x >> 24); //上面这行代码并不会对X有影响，本身X和hash的高4位相同，下面这行代码&~即对28-31(高4位)位清零。 hash &= ~x; } } //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负) return (hash & 0x7FFFFFFF); } //(此处引用自博客：http://blog.csdn.net/zhccl/article/details/7826137/）
不过没有必要太纠结，如何设计一个好的哈希方法，是数学家和计算机科学家的问题，我们主要是在合适的情境下选择合适的哈希函数即可。
(3)在每个覆盖了equals()的方法的类中，也必须复盖hashcode()方法。
因为相等的对象必须具有相等的散列码，
但根据类的equals()方法，两个截然不同的实例在逻辑上有可能相等的，不过，根据Object类的hashcode方法，它们仅仅是两个没有任何共同之处的对象。
因此会违反上面的要求。
看下面这段代码：
public class PhoneNumber { private final short areaCode; private final short prefix; private final short lineNmber; public PhoneNumber(int areaCode,int prefix,int lineNumber){ this.areaCode = (short)areaCode; this.prefix = (short)prefix; this.lineNmber = (short)lineNumber; } @Override public boolean equals(Object o){ if(o==this) return true; if(!(o instanceof PhoneNumber)) return false; PhoneNumber pn = (PhoneNumber)o; return pn.lineNmber==lineNmber && pn.prefix==prefix&&pn.areaCode==areaCode; } public static void main(String[] args){ Map<PhoneNumber,String> m = new HashMap<PhoneNumber,String>(); m.put(new PhoneNumber(707, 867, 5309),"Jenny"); System.out.println(m.get(new PhoneNumber(707, 867, 5309))); } }
输出会是诡异的null
为什么我们搜索的号码和表里的号码一致居然找不到呢？
这是因为Object类中默认的hash方法是基于地址的，即使两个实例内容相同，根据地址得到的哈希码也不相同，而如果哈希码不匹配，就不会进入到验证对象等同性的步骤。
而如果我们用添加一个保证“相同对象，相同哈希码”的hash方法覆盖原有的hash方法，如下所示：
public volatile int hashCode; @Override public int hashCode(){ int result = hashCode; if(result == 0){ result = 17; result = 31*result+areaCode; result = 31*result+prefix; result = 31*result+lineNmber; hashCode = result; } return result; }
程序如我们所愿的输出Jenny.
关于HashMap,还有好多的东西可以说，但是就到这里了，因为剩下的都是关于Hash算法本身的问题了，而这篇博客主要分析Java集合类。
好好看书，《Java编程思想》和《Effective Java》真的很精彩，结合JDK源码看，更精彩，以前怎么没这个觉悟呢？
还有，要爱惜眼睛，尤其是编程的同学。