浅谈HashMap以及重写hashCode()和equals()方法

简介

HashMap是JAVA中一个很重要的集合类型。用于存储Key-Value对。
所谓Key-Value对就是一个键对应一个值，Key和Value之间是映射关系。比如我们查询英汉词典的时候，一个中文词语对应一个英文单词(假设只有一个)。
HashMap原型如下
HashMap<K，V>
K和V分别是表示Key和Value的泛型。所以创建一个新的HashMap的时候可以传进去任何类(不能是基本类型)。
HashMap能够提供快速的随机访问能力，即通过key查询到相应的value。HashMap是基于哈希函数来存储键值对的。意思就是说，有一个哈希函数决定每个键值对应该放在什么位置。如果能做到完美哈希的话，也就是不会出现碰撞（两个键值对的哈希函数的结果一样）情况的话，访问任意一个键值对或者添加一个新的键值对的时间复杂度都是O(1)，是相当理想的性能。
当然，一般是做不到完美哈希的。HashMap的实现使用了开散列方法方法来解决冲突。也就是，对应一个特定hash值的位置存储的是一个链表头，指向hash到同一个位置的多个键值对组成的链表。这种情况下，访问键值对和添加键值对的时间复杂度肯定就不是O(1)了。随着HashMap中键值对的增多，发生碰撞的情况肯定会加剧。根据文档的说明，HashMap有一个加载因子，用来控制当HashMap达到多满的程度的时候要执行refresh操作，使得容量变为原来的大约两倍。

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

常用的操作

一般使用HashMap的时候，最常用的方法就是V get(Object key) 和V put(K key, V value) 这两个方法了。get方法是根据Key返回相应的Value，put方法是向HashMap中添加新的键值对。
具体怎么实现的？
前面说到HashMap采用开散列方法解决冲突。大概是这个样子

put

put的源码的关键部分

        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;

先定位位置，定位位置的方法是先得到Key的hashCode，然后对HashMap的实际大小求余得到确切位置，源码是这样写的

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

还有一点，位置0上存放的一定是null。
因为支撑hashMap的底层数据结构的大小一定是2的平方（每次增大也是i增大两倍），所以这里求余用了一个小技巧（这个方法不适用与对非2的次方的数求余）。
然后在遍历这个位置上的链表的过程中，如果发现在已经存在由equal函数确定的相等的Key，那么用新的Value替换掉老的Value，并返回老的Value。不然就在链表最后添加结点，并返回null。

get

看一下get的源码

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

再看getEntry的源码

  final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        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;
        }
        return null;
    }

意思很明确，就是先用hash函数确定在哪个位置，然后遍历这个位置上对应的链表，直到找到这个Key，然后返回value
这里有个地方很关键，那就是如何判判断相等我们看到这里是靠equal函数来判断的，equal函数是所有类都会从Object类处继承的函数，当我们在HashMap中存储我们自己定义的类的时候，默认的equal函数的行为可能不能符合我们的要求，所以需要重写。

其他函数

clear()
从此映射中移除所有映射关系。
Object clone()
返回此 HashMap 实例的浅表副本：并不复制键和值本身。
boolean containsKey(Object key)
如果此映射包含对于指定键的映射关系，则返回 true。
boolean containsValue(Object value)
如果此映射将一个或多个键映射到指定值，则返回 true。
Set< Map.Entry < K,V > > entrySet()
返回此映射所包含的映射关系的 Set 视图。
V get(Object key)
返回指定键所映射的值；如果对于该键来说，此映射不包含任何映射关系，则返回 null。
boolean isEmpty()
如果此映射不包含键-值映射关系，则返回 true。
Set< K > keySet()
返回此映射中所包含的键的 Set 视图。
V put(K key, V value)
在此映射中关联指定值与指定键。
void putAll(Map < ? extends K,? extends V> m)
将指定映射的所有映射关系复制到此映射中，这些映射关系将替换此映射目前针对指定映射中所有键的所有映射关系。
V remove(Object key)
从此映射中移除指定键的映射关系（如果存在）。
int size()
返回此映射中的键-值映射关系数。
Collection < V > values()
返回此映射所包含的值的 Collection 视图。

重写hashCode()和equal()

前面说到了，HashMap的很多函数要基于equal()函数和hashCode()函数。hashCode()用来定位要存放的位置，equal()用来判断是否相等。
那么，相等的概念是什么？
Object版本的equal只是简单地判断是不是同一个实例。但是有的时候，我们想要的的是逻辑上的相等。比如有一个学生类student，有一个属性studentID，只要studentID相等，不是同一个实例我们也认为是同一学生。当我们认为判定equals的相等应该是逻辑上的相等而不是只是判断是不是内存中的同一个东西的时候，就需要重写equal()。而涉及到HashMap的时候，重写了equals()，就需要重写hashCode()

我们总结一下几条基本原则
1. 同一个对象（没有发生过修改）无论何时调用hashCode()得到的返回值必须一样。
如果一个key对象在put的时候调用hashCode()决定了存放的位置，而在get的时候调用hashCode()得到了不一样的返回值，这个值映射到了一个和原来不一样的地方，那么肯定就找不到原来那个键值对了。
2. hashCode()的返回值相等的对象不一定相等，通过hashCode()和equals()必须能唯一确定一个对象
不相等的对象的hashCode()的结果可以相等。hashCode()在注意关注碰撞问题的时候，也要关注生成速度问题，完美hash不现实
3. 一旦重写了equals()函数（重写equals的时候还要注意要满足自反性、对称性、传递性、一致性），就必须重写hashCode()函数。而且hashCode()的生成哈希值的依据应该是equals()中用来比较是否相等的字段
如果两个由equals()规定相等的对象生成的hashCode不等，对于hashMap来说，他们很可能分别映射到不同位置，没有调用equals()比较是否相等的机会，两个实际上相等的对象可能被插入不同位置，出现错误。其他一些基于哈希方法的集合类可能也会有这个问题
Effective Java Programming Language Guide中建议的hashCode写法
1. 给int变量result赋予某个非零整数值，例如17
2. 位对象内每个有意义的域f(即每个可以做equals()操作的域)计算出一个int散列值c：

域类型	计算
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,其equals()调用这个域的equals()	c = f.hashCode()
数组	对每个元素应用上述规则

3. 合并计算得到的散列值：
result = 37 * result + c
4. 返回result
5. 检查hashCode()最后生成的结果，确保相同的对象有相同的散列值

至于为什么选择37、17这种数据，我也不太明白

举个例子

假设需要记录学生的成绩，每个学生本身有姓名，年龄，性别几个属性，把姓名、性别、年龄都一样的当成是同一个人（虽然不严谨）。学生对象自然就是key，成绩是Value

class Student {
    String name;
    int age;
    //true表示男，false表示女
    boolean sex;


    @Override
    public int hashCode() {
        int result = 17;
        result = 37*result+name.hashCode();
        result = 37*result+age;
        result = 37*result+(sex ? 0 : 1);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Student &&
                this.name.equals(((Student)obj).name) &&
                this.age ==  ((Student)obj).age &&
                this.sex == ((Student)obj).sex;
    }
}