为何HashSet中使用PRESENT而不是null作为value

目录
  • 1. 为什么 HashSet 中使用 PRESENT 而不是 null 作为 value
    • 1.1. PRESENT 是个什么玩意
    • 1.2. HashSet 的构造方法
    • 1.3. PRESENT 何时会被用到

1. 为什么 HashSet 中使用 PRESENT 而不是 null 作为 value

无意之中碰到了这个问题,在此记录一下

1.1. PRESENT 是个什么玩意

HashSet 的部分源码如下

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    
    static final long serialVersionUID = -5024744406713321676L;
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
}

1.2. HashSet 的构造方法

// 默认构造函数 底层创建一个HashMap
public HashSet() {
    // 调用HashMap的默认构造函数,创建map
    map = new HashMap<E,Object>();
}
 
// 带集合的构造函数
public HashSet(Collection<? extends E> c) {
    // 创建map。
    map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
    // 将集合(c)中的全部元素添加到HashSet中
    addAll(c);
}
 
// 指定HashSet初始容量和加载因子的构造函数
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
 
// 指定HashSet初始容量的构造函数
public HashSet(int initialCapacity) {
    map = new HashMap<E,Object>(initialCapacity);
}
 
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

1.3. PRESENT 何时会被用到

  • add(E) 方法
  • remove(Object) 方法

1.3.1. HashSet 中的 add(E) 方法

/**
 * add(E) 方法返回 null 时,表示 HashSet 添加数据成功
 *
 * @return true 如果不包含该元素
 */
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

直接调用的是 HashMap 的 put(K, V) 方法,此时传入的 value 值是 PRESENT

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    // tab表示 Node<K,V>类型的数组,p表示某一个具体的单链表 Node<K,V> 节点
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 判断 table[] 是否为空,如果是空的就创建一个 table[],并获取他的长度n
    if ((tab = table) == null || (n = tab.length) == 0)
    	n = (tab = resize()).length;
    // tab[i = (n - 1) & hash] 表示数组中的某一个具体位置的数据
    // 如果单链表 Node<K,V> p == tab[i = (n - 1) & hash]) == null,
    // 就直接 put 进单链表中,说明此时并没有发生 Hash 冲突
    if ((p = tab[i = (n - 1) & hash]) == null)
    	tab[i] = newNode(hash, key, value, null);
    else {
		// 说明索引位置已经放入过数据了,已经在单链表处产生了Hash冲突
        Node<K,V> e; K k;
		// 判断 put 的数据和之前的数据是否重复
        if (p.hash == hash &&
            // 进行 key 的 hash 值和 key 的 equals() 和 == 比较,如果都相等,则初始化数组 Node<K,V> e
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
		// 判断是否是红黑树,如果是红黑树就直接插入树中
        else if (p instanceof TreeNode)
        	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
			// 如果不是红黑树,就遍历每个节点,判断单链表长度是否大于等于 7,
			// 如果单链表长度大于等于 7,数组的长度小于 64 时,会优先选择扩容
			// 如果单链表长度大于等于 7,数组的长度大于 64 时,才会选择单链表--->红黑树
            for (int binCount = 0; ; ++binCount) {
            	if ((e = p.next) == null) {
            		// 采用尾插法,在单链表中插入数据
                	p.next = newNode(hash, key, value, null);
                	// 如果 binCount >= 8 - 1
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                    	treeifyBin(tab, hash);
                        break;
                }
				// 判断索引每个元素的key是否可要插入的key相同,如果相同就直接覆盖
                if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                 p = e;
			}
		}
        if (e != null) {
        	// 此时说明 key 的 hash 值和 key 的 equals() 和 == 比较结果都相等
        	// 说明数组或者单链表中有完全相同的 key
        	// 因此只需要将value覆盖,并将oldValue返回即可
        	V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
            	e.value = value;
                afterNodeAccess(e);
              	return oldValue;
        }
	}
	// 说明没有key相同,因此要插入一个key-value,并记录内部结构变化次数
    ++modCount;
    // 判断是否扩容
    if (++size > threshold)
    	resize();
    afterNodeInsertion(evict);
    return null;
}

关于 HashMap 的 put(K, V) 方法的 详细解析请看这里

  • 如果 return oldValue 说明发生了 value 覆盖,也就是说此时返回了 PRESENT,自然而然 HashMap 添加数据失败
  • 如果 return null 说明 HashMap 添加数据成功

而如果将 PRESENT 替换为 null 作为 value 值,那么 HashSet 的 add(E) 方法将无法判断添加元素的成功与失败;因为不管是成功与失败都会返回结果 null

1.3.2. HashMap 进行 put 元素示例

1.3.3. HashSet 中的 remove(Object) 方法

HashSet 的 remove(Object) 方法源码

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

HashSet 的 remove(Object) 依旧直接使用 HashMap 的 remove(Object) 方法

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

HashMap 的 remove(Object) 方法会返回 null 或 value

  • 有该值,返回 value 也就是 PRESENT,表示 remove 成功
  • 无该值,返回 null,自然而然 remove 失败

而如果将 PRESENT 替换为 null 作为 value 值,那么 HashSet 的 remove(Object) 方法将无法判断移除元素的成功与失败;因为不管是成功与失败都会返回结果 null

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Java面试题 从源码角度分析HashSet实现原理

    面试官:请问HashSet有哪些特点? 应聘者:HashSet实现自set接口,set集合中元素无序且不能重复: 面试官:那么HashSet 如何保证元素不重复? 应聘者:因为HashSet底层是基于HashMap实现的,当你new一个HashSet时候,实际上是new了一个map,执行add方法时,实际上调用map的put方法,value始终是PRESENT,所以根据HashMap的一个特性: 将一个key-value对放入HashMap中时,首先根据key的hashCode()返回值决定该E

  • Java面试题之HashSet的实现原理

    HashSet 的实现原理? 首先,我们需要知道它是Set的一个实现,所以保证了当中没有重复的元素. 一方面Set中最重要的一个操作就是查找.而且通常我们会选择 HashSet来实现,因为它专门对快速查找进行了优化. HashSet使用的是散列函数,那么它当中的元素也就无序可寻.当中是允许元素为null的. 先对实现原理进行一个总结: (1)基于HashMap实现的,默认构造函数是构建一个初始容量为16,负载因子为0.75 的HashMap.封装了一个 HashMap 对象来存储所有的集合元素,

  • java中HashSet的特点及实例用法

    1.HashSet和TreeSet区别 HashSet底层使用Hash表. 确保元素唯一性的原理:判断元素的hashCode值是否相同.如果是一样的话,会继续判断元素的equals方法是否是true. TreeSet底层采用红黑树. 确保元素的唯一性是通过Comparable或Comparator接口实现的. 2.HashSet和HashMap区别 事实上,HashSet的底层实现还是HashMap,只是它只使用了Key,具体如下: (1)在HashSet的add方法的底层,使用HashMap的

  • 理解HashSet里为什么value不是null

    最近面试,遇到一些关于 HashSet 的不寻常的八股 HashSet底层的value为啥不是一个 null呢,效率不是更高,还省得创建对象了? 那我们先来看下,这个 value 何时会被用到呢? HashSet#add 直接调用的HashMap#put 若HashMap#put: 成功,则返回null 失败,说明key已存在,就返回该key的value 综上,若底层hashmap的value维护的是null,则 HashMap#put 成功或失败都会返回null,则 HashSet#add 每

  • 为何HashSet中使用PRESENT而不是null作为value

    目录 1. 为什么 HashSet 中使用 PRESENT 而不是 null 作为 value 1.1. PRESENT 是个什么玩意 1.2. HashSet 的构造方法 1.3. PRESENT 何时会被用到 1. 为什么 HashSet 中使用 PRESENT 而不是 null 作为 value 无意之中碰到了这个问题,在此记录一下 1.1. PRESENT 是个什么玩意 HashSet 的部分源码如下 public class HashSet<E> extends AbstractSe

  • MySQL中的唯一性约束与NULL详解

    前言 之前做的一个需求,简化描述下就是接受其他组的 MQ 的消息,然后在数据库里插入一条记录.为了防止他们重复发消息,插入多条重复记录,所以在表中的几个列上加了个唯一性索引. CREATE UNIQUE INDEX IDX_UN_LOAN_PLAN_APP ON testTable (A, B, C); 这时 A,B,C 三列都是不允许 NULL 值的,唯一性约束也是 work 的. 后来由于需求的变化,修改了以前的唯一性约束,又多加了一列.(至于为什么加就不赘述了). ALTER TABLE

  • SpringBoot项目中处理返回json的null值(springboot项目为例)

    在后端数据接口项目开发中,经常遇到返回的数据中有null值,导致前端需要进行判断处理,否则容易出现undefined的情况,如何便捷的将null值转换为空字符串? 以SpringBoot项目为例,SSM同理. 1.新建配置类(JsonConfig.java) import com.fasterxml.jackson.core.JsonGenerator; import com.fasterxml.jackson.core.JsonProcessingException; import com.f

  • springboot项目中jackson-序列化-处理 NULL教程

    在项目中有事需要对值为NULL的对象中Field不做序列化输入配置方式如下: [配置类型]: 源码包中的枚举类: public static enum Include { ALWAYS, NON_NULL, NON_ABSENT, NON_EMPTY, NON_DEFAULT, USE_DEFAULTS; private Include() { } } Include.Include.ALWAYS 默认 Include.NON_DEFAULT 属性为默认值不序列化 Include.NON_EMP

  • Java中HashMap里面key为null存放到哪

    我们知道HashMap集合是允许存放null值的 hashMap是根据key的hashCode来寻找存放位置的,那当key为null时, 怎么存储呢? 在put方法里头,其实第一行就处理了key=null的情况. // HashMap的put方法 public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) // key为null调用putForNull

  • MySQL中CONCAT()函数拼接出现NULL的问题解决

    项目中查询用到了concat()拼接函数,在此查询中出现了拼接的字段为null的情况,拼接结果为null在应用层报了空指针异常. SELECT CONCAT('1,',NULL,'2') result; SELECT CONCAT('1,','','2') result; 通过实践证明CONCAT()函数拼接时如果拼接的参数中有NULL时,结果为NULL. 使用以下方式来解决 方法一:使用IFNULL函数如果是NULL将其置为''空字符串. SELECT CONCAT('1,',IFNULL(N

  • iOS中json解析出现的null,nil,NSNumber的解决办法

    在iOS开发过程中经常需要与服务器进行数据通讯,Json就是一种常用的高效简洁的数据格式. JSON建构有两种结构: json简单说就是javascript中的对象和数组,所以这两种结构就是对象和数组2种结构,通过这两种结构可以表示各种复杂的结构 1.对象:对象在js中表示为"{}"扩起来的内容,数据结构为 {key:value,key:value,...}的键值对的结构,在面向对象的语言中,key为对象的属性,value为对应的属性值,所以很容易理解,取值方法为对象.key 获取属性

  • Java中String判断值为null或空及地址是否相等的问题

    String的null或空值的判断处理 笔者在开发过程中,常常碰到过下面这些错误的用法: 1,错误用法一: if (name == "") { //do something } 2,错误用法二: if (name.equals("")) { //do something } 3,错误用法三: if (!name.equals("")) { //do something } 我们来解说一下: 上述错误用法1是初学者最容易犯,也最不容易被发现的错误,

  • 浅谈C# 中的可空值类型 null

    C# 不允许把 null 赋给一个值类型的数据.在 C# 中,以下语句是非法的: 复制代码 代码如下: int a = null;    // 非法 但是,利用 C# 定义的一个修饰符,可将一个变量声明为一个可空(nullable)值类型.可空值类型在行为上与普通值类型相似,但可以将一个 null 值赋给它.如下所示: 复制代码 代码如下: int? a = null;      // 合法 当把一个变量定义为可空值类型时,该变量依然可以被赋值为 0,代码如下所示: 复制代码 代码如下: usi

随机推荐