Java HashSet:底层工作原理与实现机制

简介: 本文介绍了Java中HashSet的工作原理,包括其基于HashMap实现的底层机制。通过示例代码展示了HashSet如何添加元素,并解析了add方法的具体过程,包括计算hash值、处理碰撞及扩容机制。

前言

在Java集合框架中,`HashSet` 是一个非常常用的数据结构,它提供了高效的元素存储和查找功能。作为一种集合,`HashSet` 允许我们存储不重复的元素,并且在平均情况下可以实现常数时间复杂度的插入和查找。这一切的背后,`HashSet` 依赖于 `HashMap` 来实现其底层机制。本文将深入探讨 `HashSet` 的工作原理,包括其如何通过计算哈希值来管理元素、如何处理碰撞以及在存储容量不足时的扩容机制。通过示例代码,我们将逐步解析 `add` 方法的具体实现过程,帮助读者更好地理解这一重要数据结构的运作方式。


public class HashSet_ {
    @SuppressWarnings("all")
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("jack");
        hashSet.add("tom");
        hashSet.add("jack");
    }
}

HashSet底层走的是HashMap()

public HashSet() {
    map = new HashMap<>();
}

执行add()方法 e就是你传入进的值,PRESENT是一个静态object()空方法,目的就是为了站位能够用到put()方法

public boolean add(E e) {
  return map.put(e, PRESENT)==null;//如果这里返回空就代表e这个值在这个并没有
}

传入的key就是上面的e,然后value就是PRESENT

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true); //如果这里返回空就代表成功了
}

求Key的hash值里面会到hashCode()方法,由于算法有点复杂就不追了,这个方法会得到key的hash值,但是这个hash值并不等价于hashCode,因为他里面还有算法

这个算法的设计可以理解为就是为了让key尽量得到不一样的hash值

static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i; //定义了一些辅助变量,一开始都是初始值
    //table就是HashMap里面一个数组类型是Node
    if ((tab = table) == null || (n = tab.length) == 0)
        //这里跳转到resize()方法n=16
        n = (tab = resize()).length; 
        //(1)根据key,得到hash 去计算该key应该存放到table表的哪个索引位置
      //并把这个位置的对象,赋给 p
        //判断p是否为null如果为null那么就表示他还没有存放元素,就创建一个Node就放在tab[i]
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((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 {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //代表修改了一次
    ++modCount;
  /*size表示存入了几个值,如果size大于了他的threshold,也就是临界值大小那么他就会跳入
    resize()这个方法进行扩容;*/
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);//这是HashMap里面一个方法
    return null;//这里返回空就代表成功了
}
final Node<K,V>[] resize() {
    // 把table赋值给一个Node类型的OldTab数组
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //threshold是HashMap定义的一个int类型初始值为0
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //DEFAULT_INITIAL_CAPACITY是HashMap里面一个静态不可改量为16 
        //static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
        //这里节解释一个<<4的意思就是1*2*2*2*2就是1*2的4次方为16
        newCap = DEFAULT_INITIAL_CAPACITY; //newCap为16
         // static final float DEFAULT_LOAD_FACTOR = 0.75f
        //这里也是是HashMap里面一个静态不可改量为0.75,他也是加载因子
        //newThr是一个临界值就是当你16个空间用了12个他就会开始扩展,就是为了防止突然大量的添加
        //内容,如果没有他就会突然卡住,这个也类似与一个缓冲
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//newThr为12
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;//12
    @SuppressWarnings({"rawtypes","unchecked"})
    //newTab数组大小为16
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //table这时已经变为16了
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;//返回newTab[16]
}
相关文章
|
24天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
64 2
|
28天前
|
Java 编译器
探索Java中的异常处理机制
【10月更文挑战第35天】在Java的世界中,异常是程序运行过程中不可避免的一部分。本文将通过通俗易懂的语言和生动的比喻,带你了解Java中的异常处理机制,包括异常的类型、如何捕获和处理异常,以及如何在代码中有效地利用异常处理来提升程序的健壮性。让我们一起走进Java的异常世界,学习如何优雅地面对和解决问题吧!
|
29天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
29天前
|
Java
Java之CountDownLatch原理浅析
本文介绍了Java并发工具类`CountDownLatch`的使用方法、原理及其与`Thread.join()`的区别。`CountDownLatch`通过构造函数接收一个整数参数作为计数器,调用`countDown`方法减少计数,`await`方法会阻塞当前线程,直到计数为零。文章还详细解析了其内部机制,包括初始化、`countDown`和`await`方法的工作原理,并给出了一个游戏加载场景的示例代码。
Java之CountDownLatch原理浅析
|
7天前
|
Java 程序员
深入理解Java异常处理机制
Java的异常处理是编程中的一块基石,它不仅保障了代码的健壮性,还提升了程序的可读性和可维护性。本文将深入浅出地探讨Java异常处理的核心概念、分类、处理策略以及最佳实践,旨在帮助读者建立正确的异常处理观念,提升编程效率和质量。
|
8天前
|
Java 开发者 UED
深入探索Java中的异常处理机制##
本文将带你深入了解Java语言中的异常处理机制,包括异常的分类、异常的捕获与处理、自定义异常的创建以及最佳实践。通过具体实例和代码演示,帮助你更好地理解和运用Java中的异常处理,提高程序的健壮性和可维护性。 ##
27 2
|
8天前
|
Java 开发者
Java中的异常处理机制深度剖析####
本文深入探讨了Java语言中异常处理的重要性、核心机制及其在实际编程中的应用策略,旨在帮助开发者更有效地编写健壮的代码。通过实例分析,揭示了try-catch-finally结构的最佳实践,以及如何利用自定义异常提升程序的可读性和维护性。此外,还简要介绍了Java 7引入的多异常捕获特性,为读者提供了一个全面而实用的异常处理指南。 ####
25 2
|
11天前
|
Java 程序员 UED
深入理解Java中的异常处理机制
本文旨在揭示Java异常处理的奥秘,从基础概念到高级应用,逐步引导读者掌握如何优雅地管理程序中的错误。我们将探讨异常类型、捕获流程,以及如何在代码中有效利用try-catch语句。通过实例分析,我们将展示异常处理在提升代码质量方面的关键作用。
24 3
|
11天前
|
Java 数据库连接 开发者
Java中的异常处理机制:深入解析与最佳实践####
本文旨在为Java开发者提供一份关于异常处理机制的全面指南,从基础概念到高级技巧,涵盖try-catch结构、自定义异常、异常链分析以及最佳实践策略。不同于传统的摘要概述,本文将以一个实际项目案例为线索,逐步揭示如何高效地管理运行时错误,提升代码的健壮性和可维护性。通过对比常见误区与优化方案,读者将获得编写更加健壮Java应用程序的实用知识。 --- ####
|
12天前
|
运维 Java 编译器
Java 异常处理:机制、策略与最佳实践
Java异常处理是确保程序稳定运行的关键。本文介绍Java异常处理的机制,包括异常类层次结构、try-catch-finally语句的使用,并探讨常见策略及最佳实践,帮助开发者有效管理错误和异常情况。
41 4