1 /**
2 * Description:新建一个类作为map的key
3 */
4 public class Groundhog
5 {
6 protected int number;
7
8 public Groundhog(){
9 }
10 public Groundhog(int number)
11 {
12 this.number = number;
13 }
14
15 @Override
16 public String toString()
17 {
18 return "Groundhog{" + "number=" + number + '}';
19 }
20 }
21
22 /**
23 * Description:新建一个类作为map的value
24 */
25 public class Prediction
26 {
27 private boolean shadow=Math.random() > 0.5;
28
29 @Override
30 public String toString()
31 {
32 if (shadow) return "Six more weeks of Winter";
33 else return "Early Spring!";
34 }
35 }
36
37 /**
38 * Description:测试类
39 */
40 public class SpringDetector
41 {
42 public static void detectSpring(Class grondHotClass) throws Exception{
43 Constructor constructor = grondHotClass.getConstructor(new Class[]{int.class});
44 Map map=new HashMap();
45 for (int i=0;i<10;i++){
46 map.put(constructor.newInstance(new Object[]{new Integer(i)}),new Prediction());
47 }
48 System.out.println("map="+map);
49
50 Groundhog groundhog=(Groundhog)constructor.newInstance(new Object[]{new Integer(3)});
51 System.out.println(groundhog);
52
53 if (map.containsKey(groundhog)) {//查找这个key是否存在
54 System.out.println((Prediction)map.get(groundhog));
55 }else {
56 System.out.println("key not find:"+groundhog);
57 }
58
59 }
60 public static void main(String[] args)
61 {
62 try {
63 detectSpring(Groundhog.class);
64 } catch (Exception e) {
65 e.printStackTrace();
66 }
67 }
68 }
看这个结果,问题就来了,map中明明存在Groudhog{number=3},为什么结果显示的是Key not find呢??问题出在哪里呢?原来是Groudhog类没有重写hashCode()方法,所以这里是使用Object的hashCode()方法生成散列码,而他默认是使用对象的地址计算散列码。因此,由Groudhog(3)生成的第一个实例的散列码与Groudhog(3)生成的散列码是不同的,所以无法查找到 key。但是仅仅重写hashCode()还是不够的,除非你重写equals()方法。原因在于不同的对象可能计算出同样的hashCode的值,hashCode 的值并不是唯一的,当hashCode的值一样时,就会使用equals()判断当前的“键”是否与表中的存在的键“相同”,即“
如果两个对象相同,那么他们的hashCode值一定相同。
如果两个对象的hashCode值相同,他们不一定相同。
正确的equals()方法必须满足下列5个条件:
1、自反性: x.equals(x) 一定成立。
2、对称性: 如果x.equals(y)成立,那么y.equals(x)也一定成立。
3、传递性:如果x.equals(y)=true ,y.equals(z)=true,那么x.equals(z)=true也成立。
4、一致性:无论调用x.equal(y)多少次,返回的结果应该保持一致。
5、对任何不是null的x,x.equals(null)一定返回false。
散列的价值在于速度:散列使得查询得以快速执行。由于速度的瓶颈是对“键”进行查询,而存储一组元素最快的数据结构是数组,所以用它来代表键的信息,注意:数组并不保存“键”的本身。而通过“键”对象生成一个数字,将其作为数组的下标索引。这个数字就是散列码,由定义在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原理的精髓所在啊!哈哈、纠结我一天。
容量(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()有些影响)
现在的IDE工具中,一般都能自动的帮我们重写了hashCode()和equals()方法,但那或许并不是最优的,重写hashCode()有两个原则:
下面是怎么写出一份像样的hashCode()的基本指导:
1、给int变量result 赋予某个非零值常量,例如 17。
2、为每个对象内每个有意义的属性f (即每个可以做equals()的属性)计算出一个 int 散列码c:
3、合并计算得到的散列值:result=37*result+c;
4、返回 result;
5、检查hashCode()最后生成的结果,确保相同的对象有相同的散列码。
下面我们将自己写一个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);
}
}
不知道大家理解了没?整了我一天,终于还算大概理解了其中的原理了。文笔比较粗糙,大家凑活看吧,毕竟,不会做饭的作家不是好程序员啊!哈哈...... 或者,可能我有很多理解的不到位的地方,还请大家不吝指教!
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有