HashMap底层实现

话说java的hashmap很好用啊，看了java的源代码之后其实发现实现也蛮简单的，map的用法就是key-value的用法，然后对于每一个对象都有一个hashcode，在hashmap内部就是利用这个hashcode来找到value的。

那么hashcode一般而言是对象的在jvm中的一个32位的地址，所以不会重复，可能有人注意到，这样的话如果用string做key那么两个内容相同的串其地址不同，那么hashcode也不同，这样就不合理了，所以实际上在String.java里是override了hashcode的方法的。

1. public int hashCode() {
2.     int h = hash;
3.     if (h == 0) {
4.         int off = offset;
5.         char val[] = value;
6.         int len = count;
7.  
8.         for (int i = 0; i < len; i++) {
9.             h = 31*h + val[off++];
10.         }
11.         hash = h;
12.     }
13.     return h;
14. }

其实这就是BKDRHash，详细可以看这里，话说31也是个magic number 呢。

有了这个可以作为主键的值，剩下的问题就是hash函数和冲突处理了。

1. static int indexFor(int h, int length) {
2.     return h & (length-1);
3. }

hash函数用了位运算里常用的&操作，而这里的length是2的幂，这样比一般的取模操作快了很多。

我们再看get里冲突是如何处理的（put同理）

1. public V get(Object key) {
2.     if (key == null)
3.         return getForNullKey();
4.     int hash = hash(key.hashCode());
5.     for (Entry<K,V> e = table[indexFor(hash, table.length)];
6.         e != null;
7.         e = e.next) {
8.         Object k;
9.         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
10.             return e.value;
11.     }
12.     return null;
13. }

一般处理冲突的方法有两种，一个是开散列，就是如果这个位置被占了就换个位置。另一个是hash链表，对于每个位置都创建链表来存储所有hash值相同的，而java里就是用了第二种方案。

注意到还有个hash函数，这是为了让所有位都能够影响到index的计算

1. static int hash(int h) {
2.     // This function ensures that hashCodes that differ only by
3.     // constant multiples at each bit position have a bounded
4.     // number of collisions (approximately 8 at default load factor).
5.     h ^= (h >>> 20) ^ (h >>> 12);
6.     return h ^ (h >>> 7) ^ (h >>> 4);
7. }

ok，基本就是这样了，道理还是比较好懂的，利用hashcode使得所有对象都可以作为key还是比较好的想法。