Java集合 HashSet底层详解_hqshset的底层实现-程序员宅基地

技术标签: Java面试  Java集合  HashSet底层原理  

前几篇文章已经介绍了关于List集合的讲解,今天学习Set集合相关的实现类。
Set集合常用的如:HashSet、TreeSet。HashSet是Set集合的典型实现,HashSet按照Hash算法来存储集合中的元素,存在以下特点:

  • 不能保证元素的顺序,元素是无序的
  • HashSet是不同步的,需要外部保持线程之间的同步问题,Collections.synchronizedSet(new XXSet());
  • 集合元素值允许为null

继承关系

 java.util.Collection
    | java.util.AbstractCollection<E> 
        | java.util.AbstractSet<E> 
             | java.util.HashSet<E> 

实现接口

Serializable, Cloneable, Iterable, Collection, Set

基本属性

private transient HashMap<E,Object> map; //map集合,HashSet存放元素的容器
private static final Object PRESENT = new Object(); //map,中键对应的value值

重要方法解析

构造方法

//无参构造方法,完成map的创建
public HashSet() {
    
    map = new HashMap<>();
}
//指定集合转化为HashSet, 完成map的创建
public HashSet(Collection<? extends E> c) {
    
   map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
   addAll(c);
}
//指定初始化大小,和负载因子
public HashSet(int initialCapacity, float loadFactor) {
    
    map = new HashMap<>(initialCapacity, loadFactor);
}
//指定初始化大小
public HashSet(int initialCapacity) {
    
    map = new HashMap<>(initialCapacity);
}
//指定初始化大小和负载因子,dummy 无实际意义
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

通过构造函数可以发现,HashSet底层是采用HashMap实现的。

Add()方法

public boolean add(E e) {
    
    return map.put(e, PRESENT)==null;
}

PRESENT为HashSet类中定义的一个使用static final修饰的常量,其实无实际意义,HashSet的add()方法调用HashMap的put()方法实现,如果键已经存在,map.put()放回的是旧值,添加失败。如果添加成功map.put()方法返回的是null,HashSet.add()方法返回的true,则添加的元素可以作为map中的key。

简单例子:

/**
 * 测试:
 *    1、hashSet不存重复元素
 *    2、存和取是无序的
 * @author Microtao
 *
 */
public class HashSetTest {
    

	public static void main(String[] args) {
    
		Set hs = new HashSet();
		hs.add("a");
		hs.add("b");
		hs.add("1");
		hs.add("2");
		hs.add("e");
		hs.add("e");
		Iterator it = hs.iterator();
		while(it.hasNext()) {
    
			System.out.println(it.next());
		}
	}
}
运行结果:a 1 b 2 e

HashSet存放的是哈希值,Hashset存储元素的顺序并不是按照存入时的顺序(和List显然不同),是按照哈希值来存的,所以取数据也是按照哈希值取的。HashSet不存入重复元素的规则:使用hashcode和equals。 那么HashSet是如何检查重复?其实原理:HashSet会通过元素的hashcode()和equals()方法进行判断,当试图将元素加入到Set集合中,HashSet首先会使用对象的hashcode来判断对象加入的位置。同时也会与其他已经加入的对象的hashcode进行比较,如果没有相等的hashcode,HashSet就认为这个对象之前不存在,如果之前存在同样的hashcode值,就会进一步的比较equals()方法,如果equals()比较返回结果是true,那么认为该对象在集合中的对象是一模一样的,不会将其加入;如果比较返回的是false,那么HashSet认为新加入的对象没有重复,可以正确加入。 如图所示:当两个对象的hashcode不一样时,说明两个对象是一定不相等的,在存储时如左图所示,当两个对象的hashcode相等,但是equals()不相等,在实际中,会在同一个位置,用链式结构来保存多个对象,而HashSet访问集合元素时也是根据元素的hashCode值快速定位,如果HashSet中两个以上的元素具有相同的hashCode值,将会导致性能下降。
在这里插入图片描述hash算法的功能是能保证快速查找被检索的对象,hash算法的价值在于速度,当需要查询集合中某个元素时,hash算法可以直接根据该元素的hashCode值计算出该元素的存储位置,从而快速定位该元素。
简单测试:

package com.microtao.set;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * 测试:
 *   重写hashCode和equals方法,作为判断两者是否相等
 *    
 * @author Microtao
 *
 */

class Per{
    
	private String name;
	private int age;
	private String sex;
	
	public String getName() {
    
		return name;
	}
	public void setName(String name) {
    
		this.name = name;
	}
	public int getAge() {
    
		return age;
	}
	public void setAge(int age) {
    
		this.age = age;
	}
	public String getSex() {
    
		return sex;
	}
	public void setSex(String sex) {
    
		this.sex = sex;
	}
	
	public Per(String name, int age, String sex) {
    
		super();
		this.name = name;
		this.age = age;
		this.sex = sex;
	}
	@Override
	public String toString() {
    
		return "Per [name=" + name + ", age=" + age + ", sex=" + sex + "]";
	}
	@Override
	public int hashCode() {
    
		return this.age * 31;
	}
	@Override
	public boolean equals(Object obj) {
    
		if(obj != null) {
    
			if(obj instanceof Per) {
    
				Per p = (Per) obj;
				return this.name.equals(p.name) && this.age == p.age;
			}
		}
		return false;
	}
	
}
public class HashSetTest {
    

	public static void main(String[] args) {
    
		Set hs = new HashSet();
		hs.add(new Per("zhangsan",12,"男"));
		hs.add(new Per("lisi",12,"女"));
		hs.add(new Per("wangwu",12,"男"));
		hs.add(new Per("zhaoliu",12,"男"));
		hs.add(new Per("zhaoliu",12,"女"));
		Iterator it = hs.iterator();
		while(it.hasNext()) {
    
			System.out.println(it.next());
		}
	}
}
运行结果:
		Per [name=zhangsan, age=12, sex=]
		Per [name=lisi, age=12, sex=]
		Per [name=wangwu, age=12, sex=]
		Per [name=zhaoliu, age=12, sex=]

上面的运行可以看出,name = zhaoliu ,age = 12有两个,但是在sex字段的值是不一样的,而在前面判断两个对象是否相等时,没有将sex字段考虑进去,所以会认为两者时一样的,所以在判断对象是否相等时,是通过计算两者的hashCode值,和equals方法进行的,这是作为Set集合判断不存重复元素的根本原因。

总结;
1、使用HashSet集合时, 首先应该知道它是无序的,其次不存在重复元素。
2、如何判断是否是重复的元素也是应该很清楚的
3、如果计算两者的hashCode值一样,但是equals不一样,也是不一样的对象,在存储时,会采用链式结构进行存储。

【参考资料】 https://blog.csdn.net/qq_33642117/article/details/52040345

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yt_19940616/article/details/90206441

智能推荐

《Linux内核设计与实现》读书笔记(十五)- 进程地址空间(kernel 2.6.32.60)_linux total_vm rss nr_ptes-程序员宅基地

文章浏览阅读323次。进程地址空间也就是每个进程所使用的内存,内核对进程地址空间的管理,也就是对用户态程序的内存管理。主要内容:地址空间(mm_struct)虚拟内存区域(VMA)地址空间和页表 1. 地址空间(mm_struct)地址空间就是每个进程所能访问的内存地址范围。这个地址范围不是真实的,是虚拟地址的范围,有时甚至会超过实际物理内存的大小。 现代_linux total_vm rss nr_ptes

攻防世界Re第一题Hello, CTF_hohctf-程序员宅基地

文章浏览阅读2.9k次。首先判断程序是32位的;用ida打开程序,对main反汇编分析发现一段可疑字符串,继续往下分析;发现scanf读入一段字符串 存于v9,且对该字符串有输入长度限制,初步怀疑v9为用户输入的flag往下分析发现v9赋与v4,且里用sprintf()函数将v4 16进制转换为字符串后面发现buffer赋与v10后,v10与可疑字符串有比较,所以v13可能为flag尝试将v13 进行16进制到字符串转换成功!!!!完结!..._hohctf

python识别验证码——一般的数字加字母验证码识别-程序员宅基地

文章浏览阅读1.7k次。转自:https://www.cnblogs.com/MrRead/p/7656800.html1、验证码的识别是有针对性的,不同的系统、应用的验证码区别有大有小,只要处理好图片,利用好pytesseract,一般的验证码都可以识别2、我在识别验证码的路上走了很多弯路,重点应该放在怎么把图片处理成这个样子,方便pytesseract的识别,以提高成功率3、原图为:思想..._python形状 数字 字母 验证码识别的代码

第一次作业-程序员宅基地

文章浏览阅读67次。第一次作业:1-1数据压缩的一个基本问题是“我们要压缩什么”,对此你是怎样理解的? 我对数据压缩的理解是在这个大数据的时代,数据量实在是太大,信息在传输的过程中过于缓慢,因此我们需要对数据进行压缩。数据压缩我们要压缩的是信号空间,主要对象包括①物理空间②时间空间③电磁频段1-2 数据压缩的另一个基本问题是“为什么进行压缩”,对此你又是怎样理解的?我个人理解的是进..._数据压缩技术的流程建模表达

Mysql的timestamp(时间戳)详解以及2038问题的解决方案_mysql timestamp范围-程序员宅基地

文章浏览阅读10w+次,点赞34次,收藏161次。mysql的timestamp 虽然好用,但是会有一个2038年的问题,本文将带你们详细了解 mysql的timestamp 以及2038问题_mysql timestamp范围

JSP基础语法-程序员宅基地

文章浏览阅读94次。学习视频来自:https://www.imooc.com/video/2940page指令语法实例:page指令学习 主要就是<%@ page language="java" import = "java.util.*" contentType="text/html; charset=utf-8"%>最常用的就是 language 使用的语言 impo..._j p的基本语法

随便推点

Cyswin 和 NCL 安装流程_cysgmwx-程序员宅基地

文章浏览阅读1.1k次。NCL 官网有提供详细的安装手册,详见:http://www.ncl.ucar.edu/Download/cygwin.shtml#RunCygwinX安装Cygwin/X 时注意:由于手册时间太老,里面很多jar包都找不到,安装Cygwin/X jar包时选择如下,安装Category "Devel","Editors","Graphics","Libs", "Net",_cysgmwx

缺包总结_写代码缺包怎么办-程序员宅基地

文章浏览阅读523次。学习SSH时,跟着书的代码写WEB应用,老是由于缺包而出错,而书上又没有相关的信息,真是郁闷。从今天开始,自己总结。java.lang.NoClassDefFoundError: antlr/ANTLRException缺失了antlr-2.7.6rc1.jar包_写代码缺包怎么办

@[],@()的使用-程序员宅基地

文章浏览阅读1.3k次。原文地址:City *city=[City new];_@[]

一. leetcode_简单题_3_char *str = (char *)malloc(max_string_length)-程序员宅基地

文章浏览阅读116次。38.给定一个正整数n(1 ≤n≤ 30),输出外观数列的第n项。(外观数列的详细定义见leetcode) 这是我见过相对困难的简单题。思路比较简单,但编程较难,这需要我们要有“状态机”的思维,也就是状态转换。因为需要一系列的状态转换,这就需要非常细心,对于那些边界条件要仔细检查。往往这类型题会让人思考有没有便捷的方法,因为这些状态转换会让人第一感觉繁琐,但事实上这道题的状态转换并不算非常困难,以后遇到这些思路简单,依赖于状态转换的题目还是要仔细思考深入一步,看是否状态转换繁琐,即..._char *str = (char *)malloc(max_string_length)

openstack简介_open stack-程序员宅基地

文章浏览阅读2.5k次。OpenStack既是一个社区,也是一个项目和一个开源软件,它提供了一个部署云的操作平台或工具集。其宗旨在于,帮助组织运行为虚拟计算或存储服务的云,为公有云、私有云,也为大云、小云提供可扩展的、灵活的云计算。1. OpenStack是什么 OpenStack既是一个社区,也是一个项目和一个开源软件,它提供了一个部署云的操作平台或工具集。其宗旨在于,帮助组织运行为..._open stack

简单工程项目管理系统-程序员宅基地

文章浏览阅读2.7k次。我是背后那一束模糊的影子,只为衬托前面那个美丽…… 实现这个“简单”的管理系统其实不是那么简单! 其中总结我所遇到的几个大问题: 其一:对于一个界面型的管理系统,用我所熟悉的MFC实现,也不断的碰见控件操作和数据交换问题; 其二:数据库操作,对于MFC的CRecordset类来说,还是需要研

推荐文章

热门文章

相关标签