草庐IT

49天精通Java，第24天，Java链表、散列表、HashSet、TreeSet

哪 吒 2023-06-28 原文


目录

大家好，我是哪吒。

一、链表

从数组中间删除一个元素开销很大，其原因是向数组中插入元素时，此元素之后的所有元素都要向后端移动，删除时也是，数组中位于被删除元素之后的所有元素都要向数组的前端移动。

此时，在Java中，可以通过链表解决这个问题。

数组是在连续的存储位置上存放对象引用，而链表则是将每个对象存放在单独的链接link中。每个链接还存放着序列中下一个链接的引用。在Java中，所有的链表都是双向链接，即每个链接还存储前驱的引用。

在链表中新增、删除一个元素是很轻松的操作，只需要更新锁删除元素前后对应的链接即可。


有的同学可能觉得上面两个图，没啥区别，其实就是前后链接指向的问题，so easy。

在Java中，可以使用双指针法来向链表中间添加元素。

ListNode newNode = new ListNode(val);  
if (head == null) {  
    head = newNode;  
} else {  
    ListNode curr = head;  
    while (curr.next != null && curr.next.next != null) {  
        curr = curr.next;  
    }  
    curr.next = newNode;  
}

在上面的代码中，我们首先创建一个新的节点newNode，并将其插入到链表的中间。如果链表为空，则将新节点设置为头部节点。否则，我们遍历链表，找到最后一个节点，并将新节点插入到该节点的后面。

二、散列表

如果想要查找某个元素，但又不知道它的存储位置，此时，就需要遍历所有元素，直到找到匹配的元素为止。如果集合中包含的元素很多，就需要耗费很长时间时间。

此时，散列表闪亮登场。

散列表可以快速的查找对象，散列表为每个元素计算一个整数，称为散列码，散列码是以某种方式由对象的实例字段得出的一个整数，可以保证不同的数据对象拥有不同的散列码。

在Java中，删列表实现为链表数组，每个列表被称为桶bucket，可以通过：先计算散列码，再与桶的总数取余，所得到的数就是保存这个元素的那个桶的索引。

可以通过初始化桶数的方式，快速的进行元素插入。

如果装载因子是0.75，当表中已经填到75%就会进行自动再散列，新的桶数就是原来的两倍。对大多数情况而言，装载因子为0.75是比较合理的。

三、HashSet

散列表可以用于实现很多数据结构，最简单的是集类型。

集的add方法会在添加前，在集中进行验证，看是否存在，只有不存在的时候，才会添加这个对象。

Java集合中的集是HashSet类，它是基于散列表实现的一个集。

  1. boolean add(E e)，向Set集合中添加元素，添加成功返回true，否则返回false；
  2. int size()，返回Set集合中的元素个数；
  3. boolean remove(Object o)，删除Set集合中的元素，删除成功返回true，否则返回false；
  4. boolean isEmpty()，如果Set不包含元素，则返回 true ，否则返回false；
  5. clear()，删除HashSet中所有元素；
  6. Iterator iterator()，遍历HashSet的迭代器；
  7. boolean contains(Object o)，判断是否含有某元素；

四、TreeSet

TreeSet是一个基于红黑树实现的有序集合，可以以任意顺序插入集合，在堆集合进行遍历时，值将自动按照排序后的顺序出现。

public static void main(String[] args) {
     TreeSet<String> treeSet = new TreeSet<String>();
     treeSet.add("哪吒编程");
     treeSet.add("Java");
     treeSet.add("Love");
     treeSet.add("CSDN");

     for(String str : treeSet){
         System.out.println(str);
     }
 }


TreeSet是通过红黑树进行排序的。

将一个元素添加到TreeSet中要比添加到散列表中慢，因为要进行排序。但与检查HashSet中的重复元素相比，使用树还是要快得多。

五、TreeSet常用方法

  1. add(Object obj)：将一个对象添加到TreeSet中；
  2. remove(Object obj)：从TreeSet中移除一个对象；
  3. pollFirst()：返回TreeSet中的第一个对象，如果TreeSet为空则返回null；
  4. pollLast()：返回TreeSet中的最后一个对象，如果TreeSet为空则返回null;
  5. size()：返回TreeSet中元素的个数;
  6. isEmpty()：判断TreeSet是否为空;
  7. contains(Object obj)：判断一个对象是否在TreeSet中;
  8. addAll(Collection<? extends E> c)：将一个Collection对象中的元素添加到TreeSet中;
  9. removeAll(Collection<? extends E> c)：从TreeSet中移除一个Collection对象中的元素;
  10. retainAll(Collection<? extends E> c)：保留一个Collection对象中的元素，并将它们添加到TreeSet中；

🏆本文收录于，Java基础教程系列。

目前已经700+订阅，CSDN最强Java专栏，包含全部Java基础知识点、Java8新特性、Java集合、Java多线程、Java代码实例，理论结合实战，实现Java的轻松学习。

🏆哪吒多年工作总结：Java学习路线总结，搬砖工逆袭Java架构师。

Java精通spanclasstoken链表散列表

有关49天精通Java，第24天，Java链表、散列表、HashSet、TreeSet的更多相关文章

  1. ruby - RVM 使用列表[0] - 2

    是否有类似“RVMuse1”或“RVMuselist[0]”之类的内容而不是键入整个版本号。在任何时候，我们都会看到一个可能包含5个或更多ruby的列表，我们可以轻松地键入一个数字而不是X.X.X。这也有助于rvmgemset。 最佳答案 这在RVM2.0中是可能的=>https://docs.google.com/document/d/1xW9GeEpLOWPcddDg_hOPvK4oeLxJmU3Q5FiCNT7nTAc/edit?usp=sharing-知道链接的任何人都可以发表评论

  2. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  3. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  4. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  5. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  6. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

  7. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

  8. 【Java入门】使用Java实现文件夹的遍历 - 2

    遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg

  9. java - 为什么 ruby​​ modulo 与 java/other lang 不同？ - 2

    我基本上来自Java背景并且努力理解Ruby中的模运算。(5%3)(-5%3)(5%-3)(-5%-3)Java中的上述操作产生，2个-22个-2但在Ruby中，相同的表达式会产生21个-1-2.Ruby在逻辑上有多擅长这个？模块操作在Ruby中是如何实现的？如果将同一个操作定义为一个web服务，两个服务如何匹配逻辑。 最佳答案 在Java中，模运算的结果与被除数的符号相同。在Ruby中，它与除数的符号相同。remainder()在Ruby中与被除数的符号相同。您可能还想引用modulooperation.

  10. java - Ruby 相当于 Java 的 Collections.unmodifiableList 和 Collections.unmodifiableMap - 2

    Java的Collections.unmodifiableList和Collections.unmodifiableMap在Ruby标准API中是否有等价物？ 最佳答案 使用freeze应用程序接口(interface):Preventsfurthermodificationstoobj.ARuntimeErrorwillberaisedifmodificationisattempted.Thereisnowaytounfreezeafrozenobject.SeealsoObject#frozen?.Thismethodretur

随机推荐