浅析HashMap

HashMap是面试官很喜欢问的一个问题，这里简单的分析一下。

HashMap继承自AbstractMap类，实现了Map,Cloneable,Serializable接口。

它的基础是hashing,要了解hashMap,我们需要弄明白几个概念：

• hashFunction
• hashValue
• bucket

1.hashFunction:返回一个integer值的方法.

2.hashValue,hashFunction返回的integer值.

3.bucket(Entry[]table),它是用来存储键值对链表的集合.

接下来我们进一步了解HashMap

public V get(Object key) {
 //假如key存在于map里面，则返回value,否则返回null 
}

在HashMap中有个内部类，叫Entry(Map.Entry),键值对就是以Entry<K,V>的链表结构存放在map中，HashMap的get(Key K)方法通过对Key对象调用hash方法，得到其的hashValue,然后通过indexFor(hashValue)找到bucket对应的entry对象。

值得注意的一点是，null亦可以作为key,它的hashValue总是0,对应到的bucket的下标总是第一个table[0].

可能会有人问，如果两个key对象的hashValue一样怎么办？
这里我们就需要用到equals方法，之前提到bucket是一个键值对的链表集合，当我们通过index找到entry对象，我们需要对entry这个链表对象进行遍历，直到key.equals(entry.key)返回true.

Entry<K,V> getEntry(Object k){
int hash = k==null?0:hash(k);
for(Entry e = table[indexFor(hash,table.length)];e!=null;e.next){
    object key;
    if(e.hash == hash && ((key = e.key) == k || (k!=null && k.equals(key) ){
      return e;
    }
}
return null;
}

也许有人要问，那如果两个key对象的hashValue和hashCode都一样怎么处理？
这里，HashMap会用后加入的entry对象覆盖掉之前的entry对象。

在HashMap中有两个重要的参数，capacity & load factor,
capacity,定义bucket的大小，必须是2的倍数(默认16)
load factor是用来限定当bucket里面的entry对象的数量增长超过一定限度的时候，HashMap将会对bucket的size * 2处理（默认.75）

最后HashMap的get和put方法都是很快的，时间复杂度是o(1).