浅析java的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还是比较好的想法。

您可能喜欢:
我猜您可能还喜欢:
,