第四章 HashSet 在 Java 中的工作原理


在这篇文章中,我们将了解 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 接口。它不是同步的,也不是线程安全的。 有时重复的定义可能非常棘手。让我们在这里考虑两种情况。

  1. 对于原始类型(如整数、字符串)
  2. 如果是自定义对象。

在原始类型的情况下:

在原始类型的情况下,它非常简单。让我们借助示例来看看:

让我们创建一个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 中添加元素。


原文链接:https://codingdict.com/