Python 官方文档:入门教程 => 点击学习
目录HashSet 类图HashSet 简单说明HashSet 底层机制说明模拟数组+链表的结构HashSet 添加元素底层机制HashSet 添加元素的底层实现HashSet 扩容
1.HashSet
实现了 Set
接口
2.HashSet
底层实际上是由 HashMap
实现的
public HashSet() {
map = new HashMap<>();
}
3.可以存放 null
,但是只能有一个 null
4.HashSet
不保证元素是有序的(即不保证存放元素的顺序和取出元素的顺序一致),取决于 hash
后,再确定索引的结果
5.不能有重复的元素
HashSet
底层是 HashMap
,HashMap
底层是 数组 + 链表 + 红黑树
public class HashSetStructureMain {
public static void main(String[] args) {
// 模拟一个 HashSet(HashMap) 的底层结构
// 1. 创建一个数组,数组的类型为 node[]
// 2. 有些地方直接把 Node[] 数组称为 表
Node[] table = new Node[16];
System.out.println(table);
// 3. 创建节点
Node john = new Node("john", null);
table[2] = jhon; // 把节点 john 放在数组索引为 2 的位置
Node jack = new Node("jack", null);
jhon.next = jack; // 将 jack 挂载到 jhon 的后面
Node rose = new Node("rose", null);
jack.next = rose; // 将 rose 挂载到 jack 的后面
Node lucy = new Node("lucy", null);
table[3] = lucy; // 将 lucy 放在数组索引为 3 的位置
System.out.println(table);
}
}
// 节点类 存储数据,可以指向下一个节点,从而形成链表
class Node{
Object item; // 存放数据
Node next; // 指向下一个节点
public Node(Object item, Node next){
this.item = item;
this.next = next;
}
}
1.HashSet
底层是 HashMap
2.当添加一个元素时,会先得到 待添加元素的 hash
值,然后将其转换成一个 索引值
3.查询存储数据表(Node 数组) table
,看当前 待添加元素 所对应的 索引值 的位置是否已经存放了 其它元素
4.如果当前 索引值 所对应的的位置不存在 其它元素,就将当前 待添加元素 放到这个 索引值 所对应的的位置
5.如果当前 索引值 所对应的位置存在 其它元素,就调用 待添加元素.equals(已存在元素)
比较,结果为 true
,则放弃添加;结果为 false
,则将 待添加元素 放到 已存在元素 的后面(已存在元素.next = 待添加元素
)
1.HashSet
的底层是 HashMap
,第一次添加元素时,table
数组扩容到 cap = 16
,threshold
(临界值) = cap * loadFactor(加载因子 0.75) = 12
2.如果 table
数组使用到了临界值 12,就会扩容到 cap * 2 = 32
,新的临界值就是 32 * 0.75 = 24
,以此类推
3.在 Java8 中,如果一条链表上的元素个数 到达 TREEIFY_THRESHOLD
(默认是 8),并且 table
的大小 >= MIN_TREEIFY_CAPACITY
(默认是 64),就会进行 树化(红黑树)
4.判断是否扩容是根据 ++size > threshold
,即是否扩容,是根据 HashMap
所存的元素个数(size
)是否超过临界值,而不是根据 table.length()
是否超过临界值
public class HashSetSourceMain {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("PHP");
hashSet.add("java");
System.out.println("set = " + hashSet);
// 源码分析
// 1. 执行 HashSet()
// 2. 执行 add()
// 3. 执行 put()
// hash(key) 得到 key(待存元素) 对应的hash值,并不等于 hashcode()
// 算法是 h = key.hashCode()) ^ (h >>> 16
// 4. 执行 putVal()
// 定义的辅助变量:Node<K,V>[] tab; Node<K,V> p; int n, i;
// table 是 HashMap 的一个属性,初始化为 null;transient Node<K,V>[] table;
// resize() 方法,为 table 数组指定容量
// p = tab[i = (n - 1) & hash] 计算 key的hash值所对应的 table 中的索引位置,将索引位置对应的 Node 赋给 p
}
}
1.HashSet
的底层是 HashMap
,HashSet
的迭代器也是借由 HashMap
来实现的
2.HashSet.iterator()
实际上是去调用 HashMap
的 KeySet().iterator()
public Iterator<E> iterator() {
return map.keySet().iterator();
}
3.KeySet()
方法返回一个 KeySet
对象,而 KeySet
是 HashMap
的一个内部类
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
4.KeySet().iterator()
方法返回一个 KeyIterator
对象,KeyIterator
是 HashMap
的一个内部类
public final Iterator<K> iterator() { return new KeyIterator(); }
5.KeyIterator
继承了 HashIterator
(HashMap
的内部类) 类,并实现了 Iterator
接口,即 KeyIterator
、HashIterator
才是真正实现 迭代器 的类
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
6.当执行完 Iterator iterator = HashSet.iterator;
之后,此时的 iterator
对象中已经存储了一个元素节点
KeySet().iterator()
方法返回一个 KeyIterator
对象new KeyIterator()
调用 KeyIterator
的无参构造器HashIterator
的无参构造器HashIterator
的无参构造器就知道发生了什么
next
、current
、index
都是 HashIterator
的属性Node<K,V>[] t = table;
先把 Node
数组 talbe
赋给 t
current = next = null;
current
、next
都置为 null
index = 0;
index
置为 0
do {} while (index < t.length && (next = t[index++]) == null);
这个 do-while
会在 table
中遍历 Node
结点(next = t[index++]) == null
不成立 时,就说明找到了一个 table
中的 Node
结点next
,并退出当前 do-while
循环Iterator iterator = HashSet.iterator;
就执行完了iterator
的运行类型其实是 HashIterator
,而 HashIterator
的 next
中存储着从 table
中遍历出来的一个 Node
结点7.执行 iterator.hasNext
此时的 next
存储着一个 Node
,所以并不为 null
,返回 true
public final boolean hasNext() {
return next != null;
}
8.执行 iterator.next()
I.Node<K,V> e = next;
把当前存储着 Node
结点的 next
赋值给了 e
II.(next = (current = e).next) == null
判断当前结点的下一个结点是否为 null
null
,就执行 do {} while (index < t.length && (next = t[index++]) == null);
,在 table
数组中遍历,寻找 table
数组中的下一个 Node
并赋值给 next
null
,就将当前结点的下一个结点赋值给 next
,并且此刻不会去 table
数组中遍历下一个 Node
结点III.将找到的结点 e
返回
IV.之后每次执行 iterator.next()
都像 (a)、(b) 那样去判断遍历,直到遍历完成
public class HashSetSourceMain {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("php");
hashSet.add("java");
System.out.println("set = " + hashSet);
// HashSet 迭代器实现原理
// HashSet 底层是 HashMap,HashMap 底层是 数组 + 链表 + 红黑树
// HashSet 本身没有实现迭代器,而是借由 HashMap 来实现的
// 1. hashSet.iterator() 实际上是去调用 HashMap 的 keySet().iterator()
// 2. KeySet() 方法返回一个 KeySet 对象,而 KeySet 是 HashMap 的一个内部类
// 3. KeySet().iterator() 方法返回一个 KeyIterator 对象,KeyIterator 是 HashMap的一个内部类
// 4. KeyIterator 继承了 HashIterator(HashMap的内部类) 类,并实现了 Iterator 接口
// 即 KeyIterator、HashIterator 才是真正实现 迭代器的类
// 5. 当执行完 Iterator iterator = hashSet.iterator(); 后
// 此时的 iterator 对象中已经存储了一个元素节点
// 怎么做到的?
// 回到第 3 步,KeySet().iterator() 方法返回一个 KeyIterator 对象
// new KeyIterator() 调用 KeyIterator 的无参构造器
// 在这之前,会先调用 KeyIterator 父类 HashIterator 的无参构造器
// 因此分析 HashIterator 的无参构造器就知道发生了什么
// 5.0 next, current, index 都是 HashIterator 的属性
// 5.1 Node<K,V>[] t = table; 先把 Node 数组 table 赋给 t
// 5.2 current = next = null; 把 current 和 next 都置为 null
// 5.3 index = 0; index 置为 0
// 5.4 do {} while (index < t.length && (next = t[index++]) == null);
// 这个 do{} while 循环会在 table 中 遍历 Node节点
// 一旦 (next = t[index++]) == null 不成立时,就说明找到了一个 table 中的节点
// 将这个节点赋给 next,并退出当前 do while循环
// 此时 Iterator iterator = hashSet.iterator(); 就执行完了
// 当前 iterator 的运行类型其实是 HashIterator,而 HashIterator 的 next 中存储着从 table 中遍历出来的一个 Node节点
// 6. 执行 iterator.hasNext()
// 6.1 此时的 next 存储着一个 Node,所以并不为 null,返回 true
// 7. 执行 iterator.next(),其实是去执行 HashIterator 的 nextNode()
// 7.1 Node<K,V> e = next; 把当前存储着 Node 节点的 next 赋值给了 e
// 7.2 (next = (current = e).next) == null
// 判断当前节点的下一个节点是否为 null
// a. 如果当前节点的下一个节点为 null
// 就执行 do {} while (index < t.length && (next = t[index++]) == null);
// 再 table 数组中 遍历,寻找 table 数组中的下一个 Node 并赋值给 next
// b. 如果当前节点的下一个节点不为 null
// 就将当前节点的下一个节点赋值给 next,并且此刻不会去 table 数组中遍历下一个 Node 节点
// 7.3 将找到的节点 e 返回
// 7.4 之后每次执行 iterator.next(),都像 a、b 那样去判断遍历,直到遍历完成
Iterator iterator = hashSet.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println(next);
}
}
}
到此这篇关于Java HashSet添加 遍历元素源码分析的文章就介绍到这了,更多相关HashSet添加 遍历元素内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: Java HashSet添加 遍历元素源码分析
本文链接: https://www.lsjlt.com/news/153926.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0