Map有几种基本实现，包括HashMap,TreeMap,LinkedHashMap,WeakHashMap,ConcurrentHashMap,IdentityHashMap。它们都有同样的基本接口Map，但是行为特性各不相同，这表现在效率、键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作和判定“键”等价的策略等方面。
对Map中键的要求：1 任何键都必须具有一个equals()方法
2 如果键被用于散列Map，那么它必须还具有恰当的hashCode()方法，不同的键可以生成相同的散列码3 如果键被用于TreeMap，那么它必须实现Comparable。
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 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;
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry 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;
}
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
可以看到，HashMap使用equals()判断当前的键是否与表中存在的键相同，HashMap是通过数组存储键的信息，使用hashCode()计算键的信息并作为存储键信息的数组下标，这个数字就是散列码，查找键对象的存储位置时会用到hashCode()方法，具有相同散列码的对象建立关系，存在在类似链表的结构中。通过键获取对象时总是先根据散列码查找实体对象，在调用equals()方法比较键对象是否相等。所以用作HashMap的键对象必须同时实现equals()方法和hashCode()方法，否则会导致找不到已经存储在Map中的对象。get()方法与put()方法按照相同的方式计算索引。
看下面的代码，首先会使用Groundhog和与之相关联的Prediction填充HashMap，然后打印HashMap，最后使用标识数字为3的Groundhog作为键，查找与之对应的预报内容。
public classGroundhog {
protectedintnumber;
publicGroundhog(intn) { number= n; }
publicString toString() {
return"Groundhog #" + number;
}
}
public classPrediction {
privatestaticRandom rand= newRandom(47);
privatebooleanshadow= rand.nextDouble() > 0.5;
publicString toString() {
if(shadow)
return"Six more weeks of Winter!";
else
return"Early Spring!";
}
}
public classSpringDetector {
// Uses a Groundhog or class derived from Groundhog:
publicstaticextendsGroundhog>
voiddetectSpring(Class type) throws Exception {
Constructor ghog = type.getConstructor(int.class);
Map map =
newHashMap();
for(int i = 0; i < 10; i++)
map.put(ghog.newInstance(i), new Prediction());
print("map = " + map);
Groundhog gh = ghog.newInstance(3);
print("Looking up prediction for " + gh);
if(map.containsKey(gh))
print(map.get(gh));
else
print("Key not found: " + gh);
}
publicstaticvoidmain(String[] args) throws Exception {
detectSpring(Groundhog.class);
}
}
结果发现，无法通过数字3这个键找到其预报的内容，问题出在Groundhog自动的继承自基类Object，所以这里使用Object的hashCode()方法生成散列码，而它默认是使用对象的地址计算散列码。由Goundhog(3)生成的第一个实例的散列码与由Goundhog(3)生成的第二个实例的散列码是不同的，所以就找不到。
转载自：http://blog.sina.com.cn/s/blog_494755fb0101g4kn.html
----------------------------------------------------------------------------------------------------
附：这两条语句：int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); 实现了哈希算法，算出了散列位置下标。
分析一下hash方法：
- h ^= (h >>> 20) ^ (h >>> 12);
- return h ^ (h >>> 7) ^ (h >>> 4);
假设key.hashCode()的值为：0x7FFFFFFF，table.length为默认值16。
上面算法执行如下：
得到i=15
其中h^(h>>>7)^(h>>>4) 结果中的位运行标识是把h>>>7 换成 h>>>8来看。
即最后h^(h>>>8)^(h>>>4) 运算后hashCode值每位数值如下：
8=8
7=7^8
6=6^7^8
5=5^8^7^6
4=4^7^6^5^8
3=3^8^6^5^8^4^7
2=2^7^5^4^7^3^8^6
1=1^6^4^3^8^6^2^7^5
结果中的1、2、3三位出现重复位^运算
3=3^8^6^5^8^4^7 -> 3^6^5^4^7
2=2^7^5^4^7^3^8^6 -> 2^5^4^3^8^6
1=1^6^4^3^8^6^2^7^5 -> 1^4^3^8^2^7^5
算法中是采用(h>>>7)而不是(h>>>8)的算法，应该是考虑1、2、3三位出现重复位^运算的情况。使得最低位上原hashCode的8位都参与了^运算，所以在table.length为默认值16的情况下面，hashCode任意位的变化基本都能反应到最终hash table 定位算法中，这种情况下只有原hashCode第3位高1位变化不会反应到结果中，即：0x7FFFF7FF的i=15。
分析indexFor方法：
Java代码
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
首先算得key得hashcode值，然后跟数组的长度-1做一次“与”运算（&）。看上去很简单，其实比较有玄机。比如数组的长度是2的4次方，那么hashcode就会和2的4次方-1做“与”运算。很多人都有这个疑问，为什么hashmap的数组初始化大小都是2的次方大小时，hashmap的效率最高，我以2的4次方举例，来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。
看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！
所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
说到这里，我们再回头看一下hashmap中默认的数组大小是多少，查看源代码可以得知是16，为什么是16，而不是15，也不是20呢，看到上面annegu的解释之后我们就清楚了吧，显然是因为16是2的整数次幂的原因，在小数据量的情况下16比15和20更能减少key之间的碰撞，而加快查询的效率。
所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)：
- // Find a power of 2 >= initialCapacity
- int capacity = 1;
- while (capacity < initialCapacity)
- capacity <<= 1;
总结：
本文主要描述了HashMap的结构，和hashmap中hash函数的实现，以及该实现的特性，同时描述了hashmap中resize带来性能消耗的根本原因，以及将普通的域模型对象作为key的基本要求。尤其是hash函数的实现，可以说是整个HashMap的精髓所在，只有真正理解了这个hash函数，才可以说对HashMap有了一定的理解。
--------------------------------------------------------
java中hashcode的作用
摘录自 http://blog.csdn.net/fenglibing/article/details/8905007
1、hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的；
2、如果两个对象相同，就是适用于equals(Java.lang.Object) 方法，那么这两个对象的hashCode一定要相同；
3、如果对象的equals方法被重写，那么对象的hashCode也尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违反上面提到的第2点；
4、两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里”。