hash table

1.介绍 匹配key->value（即为将一个对象映射为一个值，key不需要有序），hash table可以进行常数时间查询，提供equals和hashCode方法。 2.工作机制 一个数组，大小和要插入元素个数一样。先计算要插入key的hash code，再将hash code转化为数组索引（modulo division），然后将这个key匹配的value插入到这个索引的位置上。(hashcode决定key在哪个槽中)。

hashCode()&&hash code(散列值)

1.注意 (1)、程序的一次执行过程中，多次调用hashCode都应该返回相同的数值，程序的不同次执行过程，hashcode返回值不需要保持相同的数值。 2.和equals的联系 （1）等价的对象必须有相同的hash code。(相同的key必须放进同一个槽中) 原因：当我们要查询一个key匹配的value时，我们是用的与该key等价的key去找的槽号，如果这两个等价的key放进不同的槽中，那么我们就找不到那个key对应的value值了。 （2）不等价的对象不一定在不同的槽中。如果在一个槽中就是链表结构但是性能会变差，因为每一次查找都会沿着一个链表搜索。 3.重写hashCode (1)默认的hashcode和equals是一致的。

public class object{ ... public boolean equals(Object that){ return this == that;//默认的equals实质上是引用等价性 } public int hashCode(){ return //this对象的内存地址 } }

没有重写的equals比较是内存地址相同是两个对象，也就是引用相同指向同一内存空间-------引用等价性 （2）重写了equals就必须重写hashCode，否则就会出现两个对象equals了我们认为是等价的两个对象了但调用hashCode方法返回的时两个不同的地址。 （3）重写方案 方案一：hashCode永远返回一个值，一定保证了返回值相等，但性能极差因为每次查找都会沿着一个长链表结构搜索。 方案二：调用对象的不同成员变量的hashCode方法计算这些成员变量的hash code（散列值），然后通过算术计算组合这些hash code作为返回值。(选择哪些成员变量，和重写的equals相对应；如果已经是数值性成员变量则直接算数运算不用再看hash code)。

应用

set集合去重原理：加入set的元素先要调用hashCode方法，看hash code是否相同，不相同则两个对象一定不相等直接插入集合中;如果hashcode相等，则调用equals方法，如果返回true就说明这两个对象一样不能插入达到去重的目的，如果返回false则说明不相等，可以插入，hashcode相同的也有可能是不同对象。