HashSet工作原理_动力节点Java学院整理

对于 HashSet 而言,它是基于 HashMap 实现的,HashSet 底层采用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,查看 HashSet 的源代码,可以看到如下代码:

public class HashSet<E>
 extends AbstractSet<E>
 implements Set<E>, Cloneable, java.io.Serializable
 {
 // 使用 HashMap 的 key 保存 HashSet 中所有元素
 private transient HashMap<E,Object> map;
 // 定义一个虚拟的 Object 对象作为 HashMap 的 value
 private static final Object PRESENT = new Object();
 ...
 // 初始化 HashSet,底层会初始化一个 HashMap
 public HashSet()
 {
 map = new HashMap<E,Object>();
 }
 // 以指定的 initialCapacity、loadFactor 创建 HashSet
 // 其实就是以相应的参数创建 HashMap
 public HashSet(int initialCapacity, float loadFactor)
 {
 map = new HashMap<E,Object>(initialCapacity, loadFactor);
 }
 public HashSet(int initialCapacity)
 {
 map = new HashMap<E,Object>(initialCapacity);
 }
 HashSet(int initialCapacity, float loadFactor, boolean dummy)
 {
 map = new LinkedHashMap<E,Object>(initialCapacity
 , loadFactor);
 }
 // 调用 map 的 keySet 来返回所有的 key
 public Iterator<E> iterator()
 {
 return map.keySet().iterator();
 }
 // 调用 HashMap 的 size() 方法返回 Entry 的数量,就得到该 Set 里元素的个数
 public int size()
 {
 return map.size();
 }
 // 调用 HashMap 的 isEmpty() 判断该 HashSet 是否为空,
 // 当 HashMap 为空时,对应的 HashSet 也为空
 public boolean isEmpty()
 {
 return map.isEmpty();
 }
 // 调用 HashMap 的 containsKey 判断是否包含指定 key
 //HashSet 的所有元素就是通过 HashMap 的 key 来保存的
 public boolean contains(Object o)
 {
 return map.containsKey(o);
 }
 // 将指定元素放入 HashSet 中,也就是将该元素作为 key 放入 HashMap
 public boolean add(E e)
 {
 return map.put(e, PRESENT) == null;
 }
 // 调用 HashMap 的 remove 方法删除指定 Entry,也就删除了 HashSet 中对应的元素
 public boolean remove(Object o)
 {
 return map.remove(o)==PRESENT;
 }
 // 调用 Map 的 clear 方法清空所有 Entry,也就清空了 HashSet 中所有元素
 public void clear()
 {
 map.clear();
 }
 ...
 }

由上面源程序可以看出,HashSet 的实现其实非常简单,它只是封装了一个 HashMap 对象来存储所有的集合元素,所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则存储了一个 PRESENT,它是一个静态的 Object 对象。

HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的,因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。

HashMap 的 put 与 HashSet 的 add

由于 HashSet 的 add() 方法添加集合元素时实际上转变为调用 HashMap 的 put() 方法来添加 key-value 对,当新放入 HashMap 的 Entry 中 key 与集合中原有 Entry 的 key 相同(hashCode() 返回值相等,通过 equals 比较也返回 true),新添加的 Entry 的 value 将覆盖原来 Entry 的 value,但 key 不会有任何改变,因此如果向 HashSet 中添加一个已经存在的元素,新添加的集合元素(底层由 HashMap 的 key 保存)不会覆盖已有的集合元素。

掌握上面理论知识之后,接下来看一个示例程序,测试一下自己是否真正掌握了 HashMap 和 HashSet 集合的功能。
主要说明的就是重写equals()方法时,就必须重写hashCode()方法。

 class Name
{
 private String first;
 private String last;
 public Name(String first, String last)
 {
  this.first = first;
  this.last = last;
 }
 public boolean equals(Object o)
 {
  if (this == o)
  {
   return true;
  }
 if (o.getClass() == Name.class)
  {
   Name n = (Name)o;
   return n.first.equals(first)
    && n.last.equals(last);
  }
  return false;
 }
}
public class HashSetTest
{
 public static void main(String[] args)
 {
  Set<Name> s = new HashSet<Name>();
  s.add(new Name("abc", "123"));
  System.out.println(
   s.contains(new Name("abc", "123")));
 }
}

上面程序中向 HashSet 里添加了一个 new Name("abc", "123") 对象之后,立即通过程序判断该 HashSet 是否包含一个 new Name("abc", "123") 对象。粗看上去,很容易以为该程序会输出 true。

实际运行上面程序将看到程序输出 false,这是因为 HashSet 判断两个对象相等的标准除了要求通过 equals() 方法比较返回 true 之外,还要求两个对象的 hashCode() 返回值相等。而上面程序没有重写 Name 类的 hashCode() 方法,两个 Name 对象的 hashCode() 返回值并不相同,因此 HashSet 会把它们当成 2 个对象处理,因此程序返回 false。

由此可见,当我们试图把某个类的对象当成 HashMap 的 key,或试图将这个类的对象放入 HashSet 中保存时,重写该类的 equals(Object obj) 方法和 hashCode() 方法很重要,而且这两个方法的返回值必须保持一致:当该类的两个的 hashCode() 返回值相同时,它们通过 equals() 方法比较也应该返回 true。通常来说,所有参与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的标准。

如下程序就正确重写了 Name 类的 hashCode() 和 equals() 方法,程序如下:

class Name
{
 private String first;
 private String last;
 public Name(String first, String last)
 {
  this.first = first;
  this.last = last;
 }
 // 根据 first 判断两个 Name 是否相等
 public boolean equals(Object o)
 {
  if (this == o)
  {
   return true;
  }
  if (o.getClass() == Name.class)
  {
   Name n = (Name)o;
   return n.first.equals(first);
  }
  return false;
 }
 // 根据 first 计算 Name 对象的 hashCode() 返回值
 public int hashCode()
 {
  return first.hashCode();
 }
 public String toString()
 {
  return "Name[first=" + first + ", last=" + last + "]";
 }
 }
 public class HashSetTest2
 {
 public static void main(String[] args)
 {
  HashSet<Name> set = new HashSet<Name>();
  set.add(new Name("abc" , "123"));
  set.add(new Name("abc" , "456"));
  System.out.println(set);
 }
}

上面程序中提供了一个 Name 类,该 Name 类重写了 equals() 和 toString() 两个方法,这两个方法都是根据 Name 类的 first 实例变量来判断的,当两个 Name 对象的 first 实例变量相等时,这两个 Name 对象的 hashCode() 返回值也相同,通过 equals() 比较也会返回 true。

程序主方法先将第一个 Name 对象添加到 HashSet 中,该 Name 对象的 first 实例变量值为"abc",接着程序再次试图将一个 first 为"abc"的 Name 对象添加到 HashSet 中,很明显,此时没法将新的 Name 对象添加到该 HashSet 中,因为此处试图添加的 Name 对象的 first 也是" abc",HashSet 会判断此处新增的 Name 对象与原有的 Name 对象相同,因此无法添加进入,程序在①号代码处输出 set 集合时将看到该集合里只包含一个 Name 对象,就是第一个、last 为"123"的 Name 对象。

以上所述是小编给大家介绍的HashSet工作原理_动力节点Java学院整理,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!

时间: 2017-04-24

HashSet工作原理_动力节点Java学院整理

对于 HashSet 而言,它是基于 HashMap 实现的,HashSet 底层采用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,查看 HashSet 的源代码,可以看到如下代码: public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { // 使用 HashMap 的 key 保存 HashSet 中

Java中HashMap和Hashtable及HashSet的区别

Hashtable类   Hashtable继承Map接口,实现一个key-value映射的哈希表.任何非空(non-null)的对象都可作为key或者value. 添加数据使用put(key,value),取出数据使用get(key),这两个基本操作的时间开销为常数. Hashtable通过initial   capacity和load   factor两个参数调整性能.通常缺省的load   factor   0.75较好地实现了时间和空间的均衡.增大load   factor可以节省空间但

Java编程中的HashSet和BitSet详解

Java编程中的HashSet和BitSet详解 我在Apache的开发邮件列表中发现一件很有趣的事,Apache Commons包的ArrayUtils类的removeElements方法,原先使用的HashSet现在换成了BitSet. HashSet<Integer> toRemove = new HashSet<Integer>(); for (Map.Entry<Character, MutableInt> e : occurrences.entrySet()

浅析Java中Map与HashMap,Hashtable,HashSet的区别

HashTable和HashMap区别 第一,继承的父类不同.Hashtable继承自Dictionary类,而HashMap继承自AbstractMap类.但二者都实现了Map接口. 复制代码 代码如下: public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, Serializable public class HashMap<K,V>extends

Java中HashSet和HashMap的区别_动力节点Java学院整理

什么是HashSet? HashSet实现了Set接口,它不允许集合中有重复的值,当我们提到HashSet时,第一件事情就是在将对象存储在HashSet之前,要先确保对象重写equals()和hashCode()方法,这样才能比较对象的值是否相等,以确保set中没有储存相等的对象.如果我们没有重写这两个方法,将会使用这个方法的默认实现.. public boolean add(Object o)方法用来在Set中添加元素,当元素值重复时则会立即返回false,如果成功添加的话会返回true. 什

java 中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较

java 中HashMap.HashSet.TreeMap.TreeSet判断元素相同的几种方法比较 1.1     HashMap 先来看一下HashMap里面是怎么存放元素的.Map里面存放的每一个元素都是key-value这样的键值对,而且都是通过put方法进行添加的,而且相同的key在Map中只会有一个与之关联的value存在.put方法在Map中的定义如下. V put(K key, V value); 它用来存放key-value这样的一个键值对,返回值是key在Map中存放的旧va

Java中HashMap和TreeMap的区别深入理解

首先介绍一下什么是Map.在数组中我们是通过数组下标来对其内容索引的,而在Map中我们通过对象来对对象进行索引,用来索引的对象叫做key,其对应的对象叫做value.这就是我们平时说的键值对. HashMap通过hashcode对其内容进行快速查找,而 TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的). HashMap 非线程安全 TreeMap 非线程安全 线程安全 在Java里,线程安全一般体

Java中的HashSet详解和使用示例_动力节点Java学院整理

第1部分 HashSet介绍 HashSet 简介 HashSet 是一个没有重复元素的集合. 它是由HashMap实现的,不保证元素的顺序,而且HashSet允许使用 null 元素. HashSet是非同步的.如果多个线程同时访问一个哈希 set,而其中至少一个线程修改了该 set,那么它必须 保持外部同步.这通常是通过对自然封装该 set 的对象执行同步操作来完成的.如果不存在这样的对象,则应该使用 Collections.synchronizedSet 方法来"包装" set.

java 中HashMap实现原理深入理解

1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端.       数组 数组存储区间是连续的,占用内存严重,故空间复杂的很大.但数组的二分查找时间复杂度小,为O(1):数组的特点是:寻址容易,插入和删除困难: 链表 链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N).链表的特点是:寻址困难,插入和删除容易. 哈希表 那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提

JAVA中数组插入与删除指定元素的实例代码

今天学了Java的数组,写了数组的插入和删除,本人小白,写给不会的小白看,大神请忽略,有错请大家指出来: /** 给数组指定位置数组的插入 */ import java.util.*; public class ArrayInsert{ public static void main(String []args){ System.out.println("请用键盘输入5个数:"); int [] array =new int[10]; Scanner sc=new Scanner(Sy

C# 中Excel导入时判断是否被占用三种方法

C# 中Excel导入时 判断是否被占用三种方法 Excel导入时 判断是否被占用,三种方法: 1:Win7可以,WIN10不可以 try { //原理,如果文件可以被移动,说明未被占用 string strPath = "C:\\123OK.Excel"; string strPath2 = "C:\\123OK22.Excel"; File.Move(strPath, strPath2); File.Move(strPath2, strPath); } catc

python修改list中所有元素类型的三种方法

修改list中所有元素类型: 方法一: new = list() a = ['1', '2', '3'] for x in a: new.append(int(x)) print(new) 方法二: a = ['1', '2', '3'] b = [int(x) for x in a] print(b) 方法三: a = ['1', '2', '3'] print(map(int, a)) 以上这篇python修改list中所有元素类型的三种方法就是小编分享给大家的全部内容了,希望能给大家一个参

Java实现储存对象并按对象某属性排序的几种方法示例

本文实例讲述了Java实现储存对象并按对象某属性排序的几种方法.分享给大家供大家参考,具体如下: 在编程的时候,经常会出现对某一种类的对象们按照某属性进行自定义的排序,比如:学生对象按照age大小排序. 有一种方法就是把age单独提出来排好序,然后按照ages数组的顺序把students重存一次.但是这样太繁琐了,有没有更好的方法呢? 有滴~ 第一种,可以实现边添加边排序,需要用到TreeSet. 第二种,用数组存放对象们,但是不需单独取出某属性排列好再重存,而是在原数组上用比较器重新排一次序.

Python中的is和==比较两个对象的两种方法

Python中的is和==比较两个对象的两种方法 在Python中有两种方式比较两个对象是否相等,分别是is和==,两者之间是不同的 ==比较的是值(如同java中的equals方法) is比较的是引用(可以看作比较内存地址, 类似于java中的==) 对于: >>> n = 1 >>> n is 1 True >>> b = '1' >>> b is 1 False >>> n == b False 由于1和'1'

在Qt中正确的设置窗体的背景图片的几种方法总结

Qt中正确的设置窗体的背景图片的方法大致有两种,下面将逐个讲解: 一. 利用styleSheet设置窗体的背景图片 使用stylesheet设置窗体的背景图片的时候,可以直接按照下图的操作去进行即可,如下图所示: 但是,需要注意的是: 1.在QWidget中这种方法是不行的,如果你足够细心的话,你会发现使用同样的设置背景图片的方法,背景图片其实并没有发生真实改变,但是它的子窗体背景图片是会发生改变的. 其实我们可以通过在添加一个i额QWidget来解决这个问题,即在QtDesigner中添加一个