一、引入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
/** * 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的原理了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
/** * 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 + '}' ; } |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
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); } } |
六、结语
不知道大家理解了没?整了我一天,终于还算大概理解了其中的原理了。文笔比较粗糙,大家凑活看吧,毕竟,不会做饭的作家不是好程序员啊!哈哈...... 或者,可能我有很多理解的不到位的地方,还请大家不吝指教!
原文链接:http://www.cnblogs.com/jmcui/p/7419779.html