一、为什么要有Hash算法
Java中的集合有两类,一类是List,一类是Set。List内的元素是有序的,元素可以重复。Set元素无序,但元素不可重复。要想保证元素不重复,两个元素是否重复应该依据什么来判断呢?用Object.equals方法。但若每增加一个元素就检查一次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。也就是说若集合中已有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。于是Java采用了哈希表的原理。哈希(Hash)是个人名,由于他提出哈希算法的概念就以他的名字命名了。
二、Hash算法原理
当Set接收一个元素时根据该对象的内存地址算出hashCode,看它属于哪一个区间,在这个区间里调用equeals方法。
确实提高了效率。但一个面临问题:若两个对象equals相等,但不在一个区间,根本没有机会进行比较,会被认为是不同的对象。所以Java对于eqauls方法和hashCode方法是这样规定的:
1 如果两个对象相同,那么它们的hashCode值一定要相同。也告诉我们重写equals方法,一定要重写hashCode方法。
2 如果两个对象的hashCode相同,它们并不一定相同,这里的对象相同指的是用eqauls方法比较。
三、例子
1 没有重写hashCode和equals的方法
package cn.xy.test;
public class Point1
{
private int x;
private int y;
public Point1(int x, int y)
{
super();
this.x = x;
this.y = y;
}
public int getX()
{
return x;
}
public void setX(int x)
{
this.x = x;
}
public int getY()
{
return y;
}
public void setY(int y)
{
this.y = y;
}
}
public class HashSetAndHashCode
{
public static void main(String[] args)
{
HashSet<Point1> hs1 = new HashSet<Point1>();
Point1 p11 = new Point1(3, 3);
Point1 p12 = new Point1(3, 3);
Point1 p13 = new Point1(3, 5);
hs1.add(p11);
hs1.add(p11);
hs1.add(p12);
hs1.add(p13);
System.out.println(hs1.size());
}
}
答案是3
2 重写hashCode和equals的方法
package cn.xy.test;
public class Point2
{
private int x;
private int y;
public Point2(int x, int y)
{
super();
this.x = x;
this.y = y;
}
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj)
{
if (this == obj) return true;
if (obj == null) return false;
if (getClass() != obj.getClass()) return false;
Point2 other = (Point2) obj;
if (x != other.x) return false;
if (y != other.y) return false;
return true;
}
public int getX()
{
return x;
}
public void setX(int x)
{
this.x = x;
}
public int getY()
{
return y;
}
public void setY(int y)
{
this.y = y;
}
}
public class HashSetAndHashCode
{
public static void main(String[] args)
{
HashSet<Point2> hs2 = new HashSet<Point2>();
Point2 p21 = new Point2(3, 3);
Point2 p22 = new Point2(3, 3);
Point2 p23 = new Point2(3, 5);
hs2.add(p21);
hs2.add(p22);
hs2.add(p23);
System.out.println(hs2.size());
}
}
答案是2。p21和p22被认为是同一个对象。
3 没有重写hashCode的方法,但重写equals的方法
package cn.xy.test;
public class Point3
{
private int x;
private int y;
public Point3(int x, int y)
{
super();
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj)
{
if (this == obj) return true;
if (obj == null) return false;
if (getClass() != obj.getClass()) return false;
Point3 other = (Point3) obj;
if (x != other.x) return false;
if (y != other.y) return false;
return true;
}
public int getX()
{
return x;
}
public void setX(int x)
{
this.x = x;
}
public int getY()
{
return y;
}
public void setY(int y)
{
this.y = y;
}
}
public class HashSetAndHashCode
{
public static void main(String[] args)
{
HashSet<Point3> hs3 = new HashSet<Point3>();
Point3 p31 = new Point3(3, 3);
Point3 p32 = new Point3(3, 3);
Point3 p33 = new Point3(3, 5);
hs3.add(p31);
hs3.add(p32);
hs3.add(p33);
System.out.println(hs3.size());
}
}
可能是2,可能是3。因为根据内存地址算出的hashcode不知道是否在一个区域。
分享到:
相关推荐
主要给大家介绍了关于Java中HashCode方法的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用Java具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧
java中Hashcode的作用
实际上,hashcode根本不能代表object的内存地址。
对于java的hashCode,以前到现在也一直没有了解过其算法,不过猜想应该也不会太难,于是现在java中写了这段代码进行测试: 运行结果:899755 按下Ctrl键点击hashCode方法名跟进去看了下其算法,发现是很简单的几句...
java中的哈希算法和hashcode深入讲解1
主要介绍了java 中HashCode重复的可能性的相关资料,这里提供实例及测试代码,需要的朋友可以参考下
java中hashcode和equals的详解.pdf
NULL 博文链接:https://songjianyong.iteye.com/blog/1676894
Java重写equals同时需要重写hashCode的代码说明,以及如何重写hashCode方法,此代码演示按照effective java书籍说明的重写思路。代码中演示了使用集合存储对象,并且对象作为key,需重写equals和hashCode.
java中hashcode()和equals()的详解.docx
有许多人学了很长时间的Java,但一直不明白hashCode...首先,想要明白hashCode的作用,你必须要先知道Java中的集合。总的来说,Java中的集合(Collection)有两类,一类是List,再有一类是Set。你知道它们的区别吗?
主要介绍了Java 中HashCode作用以及hashcode对于一个对象的重要性,对java中hashcode的作用相关知识感兴趣的朋友一起学习吧
hash表和hashCode1
在Java应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上equals比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需...
更清楚的了解hashcode()和equals()方法。
主要介绍了深入理解Java中HashCode方法,具有一定借鉴价值,需要的朋友可以参考下
Java基础加强_ArrayList_HashSet的比较及Hashcode分析