HashMap来自互联网的小结

 

        HashMap毋庸置疑，一定是我们这些Java程序员第一大实用工具，因为其在存储数据方面，有些“无所不能”哈，而且效率与性能都合我们的意。也是因为这个HashMap在应用程序中应用过多，所以网上出现了针对HashMap的各种剖析，呵呵，鄙人也看过其源码！了解过其具体的实现，所以此时有意来总结一下在网路上的一些对HashMap的各种解析。

HashMap中的Hash算法
      HashMap使用了散列表，而散列表中要关注的问题是，如何尽可能地减少散列值的冲突，通常有两种方法，链表法和开放地址法。（嗯！数据结构的书上会有更详尽的解释）
【链表法】将相同hash值的对象组织成为一个链表放在hash值对应的槽位；
【开放地址法】通过一个探索算法，当某个槽位已经被占据的情况下继续查找下一个可以被使用的槽位。
【负载因子和容量】：在JDK中，一个HashMap的实际容量就为 【因子】*【容量】，
   JDK提供的默认值为：16*   0.75=12；
【负载因子】，负载因子a = 散列表的实际元素数目(n)/散列表的容量(m)
  在此，负载因子衡量的是一个散列表的空间使用程度，负载因子越大表示散列表的装填程度越高，反之越少。
  在JDK中，HashMap采用的是链表法的方式，而链表为单向链表，在删除过程中要自己维护previous节点
【SourceCode】
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;
}
HashMap的数据结构：数组和链表的结合体（被称为“链表散列）。如下图所示：

 

从这张图，可得到一些有用信息，HashMap中get方法的高效率，因为在HashMap中，数据时保存在数组上，从而就利用了数据的天生优点——可直接通过索引定位元素的位置。当然，在HashMap中的实现中，这个过程并不是像平常那样直接使用，看看HashMap中get方法实现吧
public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        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.equals(k)))
                return e.value;
        }
        return null;
    }
在方法体中，真正定位元素的存放位置也是通过hash值的。
每个元素上的链表存放，利用put方法塞元素时，先根据key的hash值得到这个元素在数组上的位置（下标），然后就可以把这个元素放在对应的位置上，若是，这个位置上已有其他元素，那么就会在同一个位置上将元素以链表的形式存放。新的加入放在链头，最先加入的放在链尾。HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置

HashMap中的resize的实现
当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容。在这个过程中，最消耗性能的关键点出现：原数组中的数据必须重新计算在新数组中的位置，并放进去。
这个问题，就要我们在开发过程中，要预知一下HashMap的可能大小，再给它初始化为离这个大小的接近2的整数次幂次方吧！但，这个并不是最完美的解决之道。看某位仁兄的：
比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap( 1024)更合适，不过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。

HashMap的有效使用
如果你想有效的使用HashMap，你就必须重写在其的HashCode()！
覆盖hashCode方法，使相同内容的对象来说它们的hashcode也就相同了（这样就能迅速的定位某个元素的位置）
覆盖equals方法，为了在HashMap中判断两个key是否相等时使结果有意义。
在改写equals方法的时候，需要满足以下三点：
(1) 自反性：就是说a.equals(a)必须为true。
(2) 对称性：就是说a.equals(b)=true的话，b.equals(a)也必须为true。
(3) 传递性：就是说a.equals(b)=true，并且b.equals(c)=true的话，a.equals(c)也必须为true。

两条重写建议牢记的原则：
"不为一原则"，不必对每个不同的对象都产生一个唯一的hashcode，只要你的HashCode方法使get()能够得到put()放进去的内容就可以了。
"分散原则"，生成hashcode的算法尽量使hashcode的值分散一些，不要很多hashcode都集中在一个范围内，这样有利于提高HashMap的性能。

【参考的原文章出处，非常感谢大伙们的好文】
http://www.iteye.com/topic/368087
http://www.iteye.com/topic/539465