十 java集合框架（2）：set接口 -凯发k8官方网

文章目录

• set接口和常用方法
• • 基本介绍
  • set接口常用方法
  • set接口的遍历方式
• set实现类--hashset
• • 基本介绍
  • hashset底层机制
  • 源码分析
  • • hashset的add方法
    • hashset扩容机制
  • 代码实践
• set实现类--linkedhashset
• • 基本介绍
  • 源码分析
• set实现类--treeset
• • 基本介绍
  • 源码分析

课程视频：https://www.bilibili.com/video/bv1ya411t76k

基本介绍

无序（添加和取出的顺序不一致），没有索引

不允许重复元素，所以最多包含一个null

jdk api中set接口的实现类有

set接口常用方法

和list接口一样，set接口也是collection的子接口，因此，常用方法和collection接口一样。

modifier and typemethod and description

boolean	add(e e)如果指定的元素不存在，则将其指定的元素添加（可选操作）。
boolean	addall(collection c)将指定集合中的所有元素添加到此集合（如果尚未存在）（可选操作）。
void	clear()从此集合中删除所有元素（可选操作）。
boolean	contains(object o)如果此集合包含指定的元素，则返回 true 。
boolean	containsall(collection c)返回 true如果此集合包含所有指定集合的元素。
boolean	equals(object o)将指定的对象与此集合进行比较以实现相等。
int	hashcode()返回此集合的哈希码值。
boolean	isempty()如果此集合不包含元素，则返回 true 。
iterator	iterator()返回此集合中元素的迭代器。
boolean	remove(object o)如果存在，则从该集合中删除指定的元素（可选操作）。
boolean	removeall(collection c)从此集合中删除指定集合中包含的所有元素（可选操作）。
boolean	retainall(collection c)仅保留该集合中包含在指定集合中的元素（可选操作）。
int	size()返回此集合中的元素数（其基数）。
default spliterator	spliterator()在此集合中的元素上创建一个 spliterator 。
object[]	toarray()返回一个包含此集合中所有元素的数组。
t[]	toarray(t[] a)返回一个包含此集合中所有元素的数组; 返回的数组的运行时类型是指定数组的运行时类型。

set接口的遍历方式

同collection的遍历方法一样，因为set接口是collection接口的子接口。

可以使用迭代器

增强for

不能使用索引的方式遍历

// 以set接口的实现子类 hashset举例 set接口方法 /*1. set接口的实现类（set接口对象），不能存放重复的元素，可以添加一个null2. set接口对象存放的数据是无序的（即添加的顺序和取出的顺序不一致）3. 注意：取出的顺序虽然不是添加的顺序，但是它是固定的。*/ set set = new hashset(); set.add("1"); set.add("2"); set.add("3"); set.add("3");//重复 set.add("4"); set.add("100"); set.add(null); set.add(null);//重复添加null system.out.println(set);//[null, 1, 100, 2, 3, 4] //遍历(两种方式) //1. 迭代器 system.out.println("====迭代器遍历"); iterator iterator = set.iterator(); while (iterator.hasnext()) {object next = iterator.next();system.out.println(next); } //2. 增强for遍历, 本质就是迭代器 system.out.println("====增强for遍历"); for (object o : set) {system.out.println(o); } //set接口对象，不能通过索引来获取，无法使用普通for循环遍历

基本介绍

hashset 实现了set接口

hashset 实际上是hashmap（源码如下）

public hashset() {map = new hashmap<>(); }

可以存放null值，但是只能有一个null

hashset不保证元素是有序的，取决于hash值，再确定索引的结果

不能有重复元素/对象

//1. hashset 实际上是hashmap hashset hashset = new hashset(); /* 默认构造器源码public hashset() {map = new hashmap<>();}*///2. 可以存放null值，但是只能有一个null hashset.add(null); hashset.add(null); system.out.println(hashset);hashset set = new hashset();//1.在执行add方法后，会返回一个boolean值 //2.如果添加成功，返回true，否则返回false //3.可以通过remove指定删除哪个对象 system.out.println(set.add("tom")); // true system.out.println(set.add("mike")); // true system.out.println(set.add("john")); // true system.out.println(set.add("tom")); // false system.out.println(set.add("jerry")); //true set.remove("tom"); system.out.println(set);//[mike, john, jerry]set = new hashset(); //hashset 不能添加相同的元素/数据 set.add("lucy"); // true set.add("lucy"); // false set.add(new cat("tom")); //true set.add(new cat("tom")); //true system.out.println(set);//[cat{name='tom'}, cat{name='tom'}, lucy]//经典面试题 system.out.println(set.add(new string("kobe")));//true system.out.println(set.add(new string("kobe")));//false system.out.println(set);//[kobe, cat{name='tom'}, cat{name='tom'}, lucy]

hashset底层机制

hashset 底层是hashmap，hashmap底层是（数组 链表 红黑树）

相较数组存储效率高

代码实现

//模拟一个hashsetmap的底层(hashmap的底层结构)//1.创建一个数组，数组的类型是node[] //2.有些人，直接把node[]数组称为表 node[] table = new node[16];//3.创建结点 node john = new node("john",null); table[2] = john; node jack = new node("jack", null); john.next = jack;//将jack节点挂载到 john后 node rose = new node("rose",null); jack.next = rose;//将roes结点挂载到jack后 node lucy = new node("lucy", null); table[3] = lucy; system.out.println(table);

存储结构

源码分析

hashset的add方法

hashset 底层是 hashmap

添加一个元素时，先得到hash值 会转成 -> 索引值，（不是hashcode，是hashcode经过相关运算得到hash值）

找到存储数据表table，看这个索引位置是否已经存放的有元素

如果没有，直接加入

如果有，调用equals() 比较， 如果相同，就放弃添加，如果不相同，则添加到最后

在 java8 中，如果一条链表的元素个数大于等于treeify_threshold（默认是8），并且table的大小 >= min_treeify_capcaity（默认64），就会进行树化（红黑树）

hashset hashset = new hashset();hashset.add("java"); hashset.add("php"); hashset.add("java");system.out.println("haseset="hashset); /* 1. 执行hashset() public hashset() {map = new hashmap<>(); } 2. 执行hashset.add() public boolean add(e e) { //e="java"return map.put(e, present)==null;//private static final object present = new object(); } 3. 执行put方法 public v put(k key, v value) {//key = "java" , value = present (静态)return putval(hash(key), key, value, false, true); } 4. hash(key)方法，得到key对应的一个”hash值“，但不是hashcode！ static final int hash(object key) {int h;return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);//>>>无符号右移16位 } 5. 执行putval 核心! final v putval(int hash, k key, v value, boolean onlyifabsent,boolean evict) {node[] tab; node p; int n, i; //定义了辅助变量//table 就是hashmap 的一个数组，类型是node[]//if语句标识如果当前table是null或者大小为0//第一次扩容，空间大小为16if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//resize():扩容，第一次生成node[16],数组扩展的阈值为0.75*16=12//(1)根据key，得到hash去计算该key应该存放到table表的哪个索引位置//并把这个位置的对象，赋给p//(2)判断这个p是否为空//(2.1)如果p为null//如果p为null，标识还没有存放元素，就创建一个node(key=”java“，value=present)//就放在该位置tab[i] = newnode(hash, key, value, null);if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newnode(hash, key, value, null);else {//开发技巧：在需要辅助变量或者局部变量的时候再创建//2.2如果p不为nullnode e; k k;//2.2.1 假如数组位置的元素与key（相同）//如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样//并且满足 （准备加入的key和p指向的node结点的key相同） 或（key动态绑定的equals()方法为真）if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//2.2.2 判断p是不是红黑树结点// 调用puttreeval方法添加else if (p instanceof treenode)e = ((treenode)p).puttreeval(this, tab, hash, key, value);else {//2.2.3 假如是链表// 顺次比较链表的每一个元素是否相同(和2.2.1比较方法相同)，都不相同加在最后一个位置，相同就break// 注意在把元素添加到链表后，立即判断，该链表是否到达8个结点，就调用treeifybin对链表进行树化（转成红黑树）// 注意，在转成红黑树时，要进行判断，判断条件：tab == null || (n = tab.length) < min_treeify_capacity（默认64）//上述条件成立，先table扩容，否则不成立才转成红黑树for (int bincount = 0; ; bincount) {if ((e = p.next) == null) {//比较到最后一个位置p.next = newnode(hash, key, value, null);if (bincount >= treeify_threshold - 1) // -1 for 1sttreeifybin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//3 判断是否存在if (e != null) { // existing mapping for keyv oldvalue = e.value;if (!onlyifabsent || oldvalue == null)e.value = value;afternodeaccess(e);return oldvalue;}} modcount;//size 就是我们每加入一个结点node(k,v,h,next),size ,不论是加在数组还是链表if ( size > threshold)resize();//扩容afternodeinsertion(evict);//空方法，给hashmap子类去实现return null; }*/

hashset扩容机制

hashset 底层是hashmap，第一次添加时，table数组扩容到16，临界值（threshold）是 16 * 加载因子（loadfactor）是0.75 = 12

如果table数组使用到了临界值12，就会扩容到 16 * 2 = 32，新的临界值就是 32*0.75 = 24，依次类推

在java8中，如果一条链表的元素个数到 treeify_threshold（默认是8），并且table的大小 >= min_treeify_capacity（默认64），就会进行树化（红黑树），否则仍然采用数组扩容机制

注意：

• 每添加一个元素（包括在table表，与表中链表）即添加一个节点，会执行一次 size，当size > threshold 时就会执行扩容。
• table表扩容并不是表的16个大小被添加完才执行，当所有元素的个数大于临界值时就会执行扩容。

具体可以查看博客 https://blog.csdn.net/weixin_39667787/article/details/86678215

代码实践

题目描述：

定义一个eeployee类，该类包括：private成员属性name,age

创建3个employee对象放入 hashset中

当 name和age的值相同时，认为是相同员工，不能添加到hashset集合中

关键：重写hashcode()与equals()方法

快捷键：alt insert => equals() and hashcode() => 选择相应的参数

public class demo17_hashsetexercise {public static void main(string[] args) {hashset hashset = new hashset();hashset.add(new employee("jack", 18));hashset.add(new employee("mike", 28));hashset.add(new employee("jack", 18));system.out.println(hashset);//[employee{name='mike', age=28}, employee{name='jack', age=18}]} } class employee {string name;int age;@overridepublic boolean equals(object o) {if (this == o) return true;if (o == null || getclass() != o.getclass()) return false;employee employee = (employee) o;return age == employee.age && objects.equals(name, employee.name);}@overridepublic int hashcode() {return objects.hash(name, age);}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 employee(string name, int age) {this.name = name;this.age = age;}@overridepublic string tostring() {return "employee{" "name='" name '\'' ", age=" age '}';} }

基本介绍

• linkedhashset 是 hashset的子类
• linkedhashset 底层是一个linkedhashmap，底层维护了一个 数组 双向链表
• linkedhashset 根据元素的 hashcode 值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存得。
• linkedhashset 不允许添加重复元素

说明：

在linkedhashset中维护了一个hash表和双向链表（linkedhashset 有 head和tail）

每一个节点有 before和after属性，这样可以形成双向链表

在添加一个元素时，先求hash值，在求索引，确定该元素在table的位置，然后将添加的元素加入到双向链表（如果已经存在，不添加【原则和hashset一样】）

这样遍历linkedhashset 也能确保插入顺序和遍历顺序一致

源码分析

public class demo19_linkedhashset_source {public static void main(string[] args) {linkedhashset set = new linkedhashset();set.add(new string("aa"));set.add(456);set.add(456);set.add(new customer("刘",1001));set.add(123);set.add("kobe");for (int i = 0; i < 100; i) {set.add(new customer("kobe",24));}//也会树化 parent、left、rightsystem.out.println(set);//1. linkedhashset 加入顺序和遍历顺序一致//2. linkedhashset 底层是一个linkedhashmap(是hashmap的子类)//3. linkedhashset 底层结构(数组table 双向列表)//4. 添加第一次时，直接将数组table扩容到16，存放的结点类型 linkedhashmap$entry//5. 数组是hashmap$node[] , 存放的元素/数据是 linkedhashmap$entry 类型/*//继承关系是在内部类完成 ， 都是静态内部类static class entry extends hashmap.node {entry before, after;entry(int hash, k key, v value, node next) {super(hash, key, value, next);}}*/} } class customer{private string name;private int no;public customer(string name, int no) {this.name = name;this.no = no;}@overridepublic string tostring() {return "customer{" "name='" name '\'' ", no=" no '}';}@overridepublic int hashcode() {return 1;} }

树化后的结点结构

基本介绍

• 不允许添加重复元素，不允许添加 null，不允许添加
• 无序（没有按照输入顺序进行输出）
• 遍历结果有顺序
• 底层为排序二叉树(红黑树)，且采用中序遍历得到结果 （左节点，根节点，右节点）

源码分析

public class demo_treeset {public static void main(string[] args) {//treeset treeset = new treeset();//使用匿名内部类实现comparator接口，并重写compare方法，指定排序方法treeset treeset = new treeset(new comparator() {@overridepublic int compare(object o1, object o2) {return ((string)o1).length() - ((string)o2).length();}});//添加数据treeset.add("jack");treeset.add("tom");treeset.add("sp");treeset.add("abc");//tom 和 abc 长度相等，key相等，添加失败system.out.println(treeset);//[sp, tom, jack]//1.当我们使用无参构造器时，创建treeset时,底层默认创建treemap/*public treeset() {this(new treemap());}*///treemap 如果使用默认构造函数，要求key是实现了comparable接口的，并且使用key的compareto方法比较，//也就是说仍然按照key排序，如果key没有实现comparable方法就会报错/*string类实现了comparable接口，重写了compareto方法：按升序排序,首字母先比较，相等再用第二个字母，以此类推public final class string implements java.io.serializable, comparable, charsequence {}*///2.上面的的代码实现了添加元素按照字符串长度来排序//3./*public v put(k key, v value) {entry t = root;if (t == null) {compare(key, key); // type (and possibly null) checkroot = new entry<>(key, value, null);size = 1;modcount ;return null;}int cmp;entry parent;// split comparator and comparable pathscomparator cpr = comparator;//传入的比较器if (cpr != null) {do {parent = t;cmp = cpr.compare(key, t.key);//动态绑定到我们的comparatorif (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setvalue(value);//如果比较器比较结果相同，更改value，不更改key//treeset的value是类,private static final object present = new object();} while (t != null);}else {//如果使用默认构造函数，即没有比较器对象//要求key是实现了comparable接口的，并且使用key的compareto方法比较，if (key == null)//key不能为空throw new nullpointerexception();@suppresswarnings("unchecked")comparable k = (comparable) key;//要求key是实现了comparable接口的do {parent = t;cmp = k.compareto(t.key);//使用key的compareto方法比较if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setvalue(value);} while (t != null);}entry e = new entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;fixafterinsertion(e);//加入后红黑树旋转size ;modcount ;return null;}*/treeset = new treeset();treeset.add(new c(1));treeset.add(new c(2));treeset.add(new c(1));system.out.println(treeset);} } class c implements comparable<c>{int num;public c(int num) {this.num = num;}public int compareto( c c) {return this.num - c.num;}@overridepublic string tostring() {return "c{" "num=" num '}';} }

总结

以上是凯发k8官方网为你收集整理的十 java集合框架（2）：set接口的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。