散列算法与散列码(实例讲解)
一、引入
/**
* description:新建一个类作为map的key
*/
public class groundhog
{
protected int number;
public groundhog(){
}
public groundhog(int number)
{
this.number = number;
}
@override
public string tostring()
{
return "groundhog{" + "number=" + number + '}';
}
}
/**
* description:新建一个类作为map的value
*/
public class prediction
{
private boolean shadow=math.random() > 0.5;
@override
public string tostring()
{
if (shadow) return "six more weeks of winter";
else return "early spring!";
}
}
/**
* description:测试类
*/
public class springdetector
{
public static void detectspring(class grondhotclass) throws exception{
constructor constructor = grondhotclass.getconstructor(new class[]{int.class});
map map=new hashmap();
for (int i=0;i<10;i++){
map.put(constructor.newinstance(new object[]{new integer(i)}),new prediction());
}
system.out.println("map="+map);
groundhog groundhog=(groundhog)constructor.newinstance(new object[]{new integer(3)});
system.out.println(groundhog);
if (map.containskey(groundhog)) {//查找这个key是否存在
system.out.println((prediction)map.get(groundhog));
}else {
system.out.println("key not find:"+groundhog);
}
}
public static void main(string[] args)
{
try {
detectspring(groundhog.class);
} catch (exception e) {
e.printstacktrace();
}
}
}
看这个结果，问题就来了，map中明明存在groudhog{number=3},为什么结果显示的是key not find呢？？问题出在哪里呢？原来是groudhog类没有重写hashcode()方法，所以这里是使用object的hashcode()方法生成散列码，而他默认是使用对象的地址计算散列码。因此，由groudhog(3)生成的第一个实例的散列码与groudhog(3)生成的散列码是不同的，所以无法查找到 key。但是仅仅重写hashcode()还是不够的，除非你重写equals()方法。原因在于不同的对象可能计算出同样的hashcode的值，hashcode 的值并不是唯一的，当hashcode的值一样时，就会使用equals()判断当前的“键”是否与表中的存在的键“相同”，即“
二、理解hashcode()
散列的价值在于速度：散列使得查询得以快速执行。由于速度的瓶颈是对“键”进行查询，而存储一组元素最快的数据结构是数组，所以用它来代表键的信息，注意：数组并不保存“键”的本身。而通过“键”对象生成一个数字，将其作为数组的下标索引。这个数字就是散列码，由定义在object的hashcode()生成(或成为散列函数)。同时，为了解决数组容量被固定的问题，不同的“键”可以产生相同的下标。那对于数组来说？怎么在同一个下标索引保存多个值呢？？原来数组并不直接保存“值”，而是保存“值”的 list。然后对 list中的“值”使用equals()方法进行线性的查询。这部分的查询自然会比较慢，但是如果有好的散列函数，每个下标索引只保存少量的值，只对很少的元素进行比较，就会快的多。
不知道大家有没有理解我上面在说什么。不过没关系，下面会有一个例子帮助大家理解。不过我之前一直被一个问题纠结：为什么一个hashcode的下标存的会有多个值？因为hashmap里面只能有唯一的key啊，所以只能有唯一的value在那个下标才对啊。这里就要提出一个新的概念哈希冲突的问题，借用网上的一个例子：
比如：数组的长度是5。这时有一个数据是6。那么如何把这个6存放到长度只有5的数组中呢。按照取模法，计算6％5，结果是1，那么就把6放到数组下标是1的位置。那么，7就应该放到2这个位置。到此位置，哈希冲突还没有出现。这时，有个数据是11，按照取模法，11％5＝1，也等于1。那么原来数组下标是1的地方已经有数了，是6。这时又计算出1这个位置，那么数组1这个位置，就必须储存两个数了。这时，就叫哈希冲突。冲突之后就要按照顺序来存放了。所以这里java中用的解决方法就是在这个hashcode上存一个list，当遇到相同的hashcode时，就往这个list里add元素就可以了。这才是hash原理的精髓所在啊！哈哈、纠结我一天。
三、hashmap的性能因子
容量(capacity):散列表中的数量。
初始化容量(initial capacity):创建散列表时桶的数量。hashmap 和 hashset都允许你在构造器中制定初始化容量。
尺寸(size):当前散列表中记录的数量。
负载因子(load factor):等于"size/capacity"。负载因子为0，表示空的散列表，0.5表示半满的散列表，依次类推。轻负载的散列表具有冲突少、适宜插入与适宜查询的特点(但是使用迭代器遍历会变慢)。hashmap和hashset的构造器允许你制定负载因子。这意味着，当负载达到制定值时，容器会自动成倍的增加容量，并将原有的对象重新分配，存入新的容器内(这称为“重散列”rehashing)。hashmap默认的负载因子为0.75，这很好的权衡了时间和空间的成本。
备注：为使散列分布均衡，java的散列函数都使用2的整数次方来作为散列表的理想容量。对现代的处理器来说，除法和求余是最慢的动作。使用2的整数次方的散列表，可用掩码代替除法。因为get()是使用最多的操作，求余数的%操作是其开销的大部分，而使用2的整数次方可以消除此开销(也可能对hashcode()有些影响)
四、怎么重写hashcode()
现在的ide工具中，一般都能自动的帮我们重写了hashcode()和equals()方法，但那或许并不是最优的，重写hashcode()有两个原则:
必须速度快，并且必须有意义。也就是说，它必须基于对象的内容生成散列码。
应该产生分布均匀的散列码。如果散列码都集中在一块，那么在某些区域的负载就会变得很重。
下面是怎么写出一份像样的hashcode()的基本指导：
1、给int变量result 赋予某个非零值常量，例如 17。
2、为每个对象内每个有意义的属性f (即每个可以做equals()的属性)计算出一个 int 散列码c:
3、合并计算得到的散列值：result=37*result+c；
4、返回 result；
5、检查hashcode()最后生成的结果，确保相同的对象有相同的散列码。
五、自定义hashmap
下面我们将自己写一个hashmap，便于了解底层的原理，大家如果看的懂下面的代码，也就很好的理解了hashcode的原理了。
/**
* description:首先新建一个类作为map中存储的对象并重写了hashcode()和equals()方法
*/
public class mpair implements map.entry,comparable
{
private object key,value;
public mpair(object key,object value)
{
this.key = key;
this.value=value;
}
@override
public int compareto(object o)
{
return ((comparable)key).compareto(((mpair)o).key);
}
@override
public object getkey()
{
return key;
}
@override
public object getvalue()
{
return value;
}
@override
public int hashcode()
{
int result = key != null ? key.hashcode() : 0;
result = 31 * result + (value != null ? value.hashcode() : 0);
return result;
}
@override
public boolean equals(object o)
{
return key.equals(((mpair)o).key);
}
@override
public object setvalue(object v)
{
object result=value;
this.value=v;
return result;
}
@override
public string tostring()
{
return "mpair{" + "key=" + key + ", value=" + value + '}';
}
public class simplehashmap extends abstractmap
{
private static final int sz=3;//定一个初始大小的哈希表容量
private linkedlist[] linkedlists=new linkedlist[sz];//建一个hash数组，用linkedlist实现
public object put(object key,object value){
object result=null;
int index=key.hashcode() % sz;//对key的值做求模法求出index
if (index<0) index=-index;
if (linkedlists[index]==null) linkedlists[index]=new linkedlist();//如果这个index位置没有对象，就新建一个
linkedlist linkedlist = linkedlists[index];//取出这个index的对象linkedlist
mpair mpair = new mpair(key,value);//新建要存储的对象mpair
listiterator listiterator = linkedlist.listiterator();
boolean found =false;
while (listiterator.hasnext()){//遍历这个index位置的list,如果查找到跟之前一样的对象(根据equals来比较)，则更新那个key对应的value
object next = listiterator.next();
if (next.equals(mpair)){
result = ((mpair) next).getvalue();
listiterator.set(mpair);//更新动作
found=true;
break;
}
}
if (!found) linkedlists[index].add(mpair);//如果没有找到这个对象，则在这index的list对象上新增一个元素。
return result;
}
public object get(object key){
int index = key.hashcode() % sz;
if (index<0) index=-index;
if (linkedlists[index]==null) return null;
linkedlist linkedlist = linkedlists[index];
mpair mpair=new mpair(key,null);//新建一个空的对象值，因为equals()的比较是看他们的key是否相等，而在list中的遍历对象的时候，是通过key来查找对象的。
listiterator listiterator = linkedlist.listiterator();
while (listiterator.hasnext()){
object next = listiterator.next();
if (next.equals(mpair)) return ((mpair)next).getvalue();//找到了这个key就返回这个value
}
return null;
}
@override
public set<entry> entryset()
{
set set=new hashset();
for (int i=0;i<linkedlists.length;i++){
if (linkedlists[i]==null) continue;
iterator iterator = linkedlists[i].iterator();
while (iterator.hasnext()){
set.add(iterator.next());
}
}
return set;
}
public static void main(string[] args)
{
simplehashmap simplehashmap=new simplehashmap();
simplehashmap.put("1", "1");
simplehashmap.put("2", "2");
simplehashmap.put("3","3");
simplehashmap.put("4","4");//这里有四个元素，其中key是1和key是4的index是一样的，所以index为1的list上面存了两个元素。
system.out.println(simplehashmap);
object o = simplehashmap.get("1");
system.out.println(o);
object o1 = simplehashmap.get("4");
system.out.println(o1);
}
}
六、结语
不知道大家理解了没？整了我一天，终于还算大概理解了其中的原理了。文笔比较粗糙，大家凑活看吧，毕竟，不会做饭的作家不是好程序员啊！哈哈...... 或者，可能我有很多理解的不到位的地方，还请大家不吝指教！