HashMap简介以及hashCode写法的建议

映射表Map

Map也叫映射表或者字典，Map中存储的元素是一个键值对key-value，他们共同包装在Entry<K,V>对象中。我们能通过key直接获取value，就像查字典一样。

JDK中，Map有两种实现方式，一是散列技术，二是红黑树。

常见的Map实现

HashMap通过散列技术实现。Map中的key对象必须定义equals以及hashCode方法。该容器的访问效率很高，几乎等同于数组。一般情况下，没有特殊需求，这应该是默认选项。

LinkedHashMap是HashMap的子类，性能略差于HashMap。相比HashMap，该容器能以插入的顺序遍历元素。实现原理是使用链表将各个Node串起来，因此，其迭代效率比HashMap更加高效。他的key要求同HashMap一样。

TreeMap通过红黑树结构实现，因此，其内元素是有序的。元素的key对象必须实现Comparable接口，这样红黑树才能对元素进行排序。由于TreeMap是有序的，也就多出了一些与有序性相关的方法，比如firstKey、lastKey、subMap(fromKey,toKey)、headMap(toKey)等等。他的查询效率比散列低很多，为$log(n)$。

ConcurrentHashMap是一种线程安全的HashMap，主要通过synchronized同步块和CAS的方式实现，不涉及同步锁

WeakHashMap中,如果某个键没有被引用，那么该键可以被GC回收。用于特殊用途。

IdentityHashMap，在进行对比key的时候，使用==而不是equals。用于特殊用途。

小结一下，散列的效率比红黑树要高，但是红黑树的元素是有序的。使用散列Map的key必须覆盖equals和hashCode，使用红黑树Map必须实现Comparable接口

散列技术与hashCode

前面说过，Map的实现方式之一是利用散列技术，HashMap、LinkedHashMap都使用的散列技术。

数组的索引访问时间为 $O(1)$ ,因为数组的内存是连续的且类型固定。因此，只要获取数组首地址和偏移量(索引)，即可直接计算出元素的地址。

散列就是利用数组这一特点，如图1，他将数组作为存储元素的基础。通过使用给定函数 $f(n)$ 计算出key的hashcode，之后再对hashcode二次处理，一般是对数组长度取模，便可得到数组的索引。

另外，不同的key可以计算出相同的hashcode，但是散列函数最好能做到散列值均匀分布在数组中。最差的情况是所有散列值都一样，这将严重拖垮Map的存取速度。

综上，我们可以这样描述HashMap的存取过程。

在调用put(key,value)时，key-value首先会包装在Node<K,V>中。对key调用hash(key)计算散列值，之后散列值对数组长度取模，算得一个数组的索引位置，称为插槽(slot)。插槽位不装实际的数据，而是哨兵节点head。之后每一个相同hashCode的Node都会插入该head的链表中。同时，为了优化查询速度，当链表节点过多的时候，会将链表转化为红黑树。

注意，当元素数超过$arr-length*load-factor$的时候，会触发Map的resize。这时候，数组拓展一倍，所有的元素重新散列。因此，这也是HashMap中最损害性能的一部分。为了减少这种情况的发生，最好在最初就对Map的容量需求有个大致的估计。

查询即get(key)的过程和put是相似的。首先通过hashCode拿到元素的插槽位，然后遍历链表或者红黑树，通过equals方法逐个对比。这也是，为什么散列一定要覆盖hashCode和equals的原因。hashCode和equals必须唯一确定一个元素。

图1 HashMap的数据结构

hashCode的写法

前面说过，散列的核心步骤就是计算key的hashCode，因此设计好的hash方法也就非常的必要了。

hashCode的结果具有一致性，即无论何时计算得到的结果都一样。这就要求，计算hashCode依赖的值是不可变的
hashCode不该依赖具有唯一性的对象信息，如果hashCode依赖的信息每个对象只此一份，我们就永远无法在外部创造一个相同的key来获取value了
hashCode必须基于对象的内容生成散列码
hashCode产生的散列码最好能均匀分布

以上hashCode设计的几点原则，一下给出Josh Bloch给出的重写hashCode的建议

域类型	计算
boolean	`c = (f? 0 : 1)`
byte/char/short/int	`c = (int)f`
long	`c = (int)(f ^ f>>>32)`
float	`c = Float.floatToIntBits(f)`
double	`long l = Double.doubleToLongBits(f); c = (int)(l ^ l>>>32)`
Object	`c = f.hashCode()`
数组	每个元素使用以上规则

以上是基本类型和对象转换hashCode的方法，当我们计算一个对象hashCode的时候因该将他的每一个域(不可变)都考虑进去。将result初始化为17，result乘以37再加上当前域的hash值再赋予result，即：

result = 37 * result +c

比如我们自定义对象CountingString作为key，hashCode便如下定义

public class CountedString {

    private static List<String> created = new ArrayList<>();

    private String s;

    private int id = 0;

    public CountedString(String s) {

        this.s = s;

        created.add(s);

        for (String ss : created) {

            if (ss.equals(s))//如果s，则他们的id编号必不相同

                id++;

        }

    }

    @Override

    public String toString() {

        return "[s:"+s+"],[id:"+id+"],[hashCode:"+hashCode()+"]";

    }

    @Override

    public int hashCode() {

        int result = 17;

        result = result * 37 + s.hashCode();

        result = result * 37 + id;

        return result;

    }

    @Override

    public boolean equals(Object obj) {

        return obj instanceof CountedString &&

                (s.equals(((CountedString) obj).s)) &&

                (id == ((CountedString) obj).id);

    }

}

借助框架

最后，实现好hashCode和equals是很需要技巧的，我们可以借助Apache Commons3等一类的框架，他们都自带了不错的工具。

参考

Effective Java 3
Java编程思想

巴特西