在这篇文章中,我们将了解 Java 中的 Hashset
Java HashSet:
Part-1:<a href="http://www.java2blog.com/2014/07/how-hashset-works-in-java.html">HashSet in java</a>
Part-2:<a href="http://www.java2blog.com/2013/02/difference-between-hashmap-and-hashset.html">Difference between HashMap and HashSet</a>
Part-3:<a href="http://www.java2blog.com/2014/02/hashcode-and-equals-method-in-java.html">hashcode and equals method in jav</a>a
这是 Java 核心面试中经常被问到的问题之一,所以在这篇文章中,我们将了解 HashSet 在 Java 中的工作原理。
让我们先看看 Hashset 的介绍,然后我们将介绍它的内部。
HashSet:
HashSet 实现了不允许重复值的 Set 接口。它不是同步的,也不是线程安全的。 有时重复的定义可能非常棘手。让我们在这里考虑两种情况。
-
对于原始类型(如整数、字符串)
-
如果是自定义对象。
在原始类型的情况下:
在原始类型的情况下,它非常简单。让我们借助示例来看看:
让我们创建一个java程序:
package org.arpit.java2blog;
import java.util.HashSet;
public class HashSetMain {
public static void main(String[] args) {
HashSet nameSet=new HashSet();
nameSet.add("Arpit");
nameSet.add("Arpit");
nameSet.add("john");
System.out.println("size of nameSet="+nameSet.size());
System.out.println(nameSet);
}
}
当你运行上面的程序时,你会得到以下输出:
size of nameSet=2
[Arpit, john]
所以我们尝试了两次添加字符串“Arpit”,但是由于HashSet不允许重复值,它会在HashSet中添加一次“Arpit”
在自定义对象的情况下: 要了解 HashSet 在自定义对象的情况下如何工作,您需要了解java 中的 hashcode 和 equals 方法。让我们创建一个名为 Country 的类并在其中只实现 equals 方法。
package org.arpit.java2blog;
public class Country {
String name;
long population;
public String getName() {
return name;
}
public void setName(String name){
this.name = name;
}
public long getPopulation() {
return population;
}
public void setPopulation(long population) {
this.population = population;
}
public String toString()
{
return name;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Country other = (Country) obj;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
创建主类:
package org.arpit.java2blog;
import java.util.HashSet;
public class HashSetCountryMain {
public static void main(String[] args)
{
HashSet countrySet=new HashSet();
Country india1=new Country();
india1.setName("India");
Country india2=new Country();
india2.setName("India");
countrySet.add(india1);
countrySet.add(india2);
System.out.println("size of nameSet="+countrySet.size());
System.out.println(countrySet);
}
}
当你运行上面的程序时,你会得到以下输出:
size of nameSet=2
[India, India]
现在您一定想知道即使两个对象相等,为什么 HashSet 包含两个值而不是一个。这是因为 First HashSet 计算该键对象的哈希码,如果哈希码相同,则仅检查 equals 方法,并且因为上述两个国家/地区的哈希码对象使用默认的哈希码方法,两者都有不同的内存地址,因此有不同的哈希码。 现在让我们在上面的 Country 类中添加 hashcode 方法
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
再次运行上面的主程序,你将得到以下输出:
size of nameSet=1
[India]
所以现在我们对 HashSet 有了很好的理解,让我们看看它的内部表示:
HashSet的内部工作:
当您向 HashSet 添加任何重复元素时,add() 方法返回 false,并且不会向 HashSet 添加重复元素。
如何添加方法返回false?为此,我们需要查看JavaAPI中HashSet的add方法
public class HashSet
extends AbstractSet
implements Set, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
// PRESENT is dummy value which will be used as value in map
private static final Object PRESENT = new Object();
/**
* Constructs a empty map.so hash
*
*/
public HashSet() {
map = new HashMap<E,Object>();
}
// return false if e is already present in HashSet
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// other HashSet methods
}
所以从上面的代码中,很明显 HashSet 使用HashMap来检查重复元素。我们知道在 HashMap 中,key 应该是唯一的。所以 HashSet 使用了这个概念,当元素添加到 HashSet 时,它作为 Key 添加到内部 HashMap 中。这个 HashMap 需要一些值,所以在这个 HashMap 中使用一个虚拟对象(PRESENT)作为值。 PRESENT 是用于内部映射的虚拟值。 让我们看看添加方法:
// return false if e is already present in HashSet
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
所以这里会有两种情况
-
如果该地图中不存在元素,map.put(e,PRESENT) 将返回 null。因此 map.put(e, PRESENT) == null 将返回 true ,因此 add 方法将返回 true 并且元素将添加到 HashSet 中。
-
map.put(e,PRESENT) 将返回旧值,如果元素已经存在于该地图中。因此 map.put(e, PRESENT) == null 将返回 false,因此 add 方法将返回 false 并且不会在 HashSet 中添加元素。
|