|
|
10鱼币
本人菜鸟一只, 今天遇到一串代码 好奇实现原理是怎么样, 跪求大佬们教学一波
package Test;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
* User: User
* Date: 2022/3/11
*/
public class test_01 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Set<Integer> a = new HashSet<Integer>();
for (int i = 0;sc.nextInt()!=0;){
a.add(sc.nextInt());
}
System.out.println(a);
}
}
控制台输入和获取的信息如下:
1 2 3 4 5 6 0
[2, 4, 6]
大佬们可以详细说明一下标红的代码的实现过程之类的吗
本帖最后由 782353676 于 2022-3-13 11:40 编辑
你好,我刚好在总结相关知识
### 结论
- `HashSet的底层是HashMap (HashMap的底层是数组+链表结构+红黑树)`
- `HashSet不保证元素是有序的,取决于hash后，再确定索引的结果.`
- `可以存放null,但只能是一个`
- ==不能有重复的元素或值(相同的值经过hash算法得到的索引位置的值equals`equals依据程序员标准`比较.相同放弃添加,不相同,在该位置生成链表追加)==
` 1. HashSet底层是HashMap,第一次添加时,table数组扩容到16，临界值(threshold)是16*加载因子(loadFactor)是0.75 =12`
` 2. 如果table数组使用到了临界值12,就会扩容到16*2 = 32,新的临界值就是32*0.75 = 24,依次类推`
` 3. 在Java8/11中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN TREEIFY CAPACITY(默认64),就会进行树化(红黑树)，否则仍然采用数组扩容机制`
`4.只要添加了元素,size++.也就是说总元素到达阈值就会触发扩容或树化`
`5. 若链表元素到了8个,而table表的大小不到64,那么table表会按照2倍扩容`
### 3.1.1 HashSet无参构造增添元素
`1.HashsSet底层就是HashMap`
`putVal` /**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
// return putVal(hash(key), key, value, false, true);
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 定义的辅助变量
Node<K,V>[] tab; Node<K,V> p; int n, i;
// talbe 是hashMap的一个放Node节点的数组
// if 表示如果当前table是null,或大小等于0,就是第一次扩容到16个
if ((tab = table) == null || (n = tab.length) == 0)
// 下面细讲resize方法,这里是重新计算并开辟表的空间.无参构造第一次初始化为16
n = (tab = resize()).length;
// 根据传入key的hash值去计算该key应该放到table表的哪个索引位置
//(& 按位与操作,一定比最小的还要小!控制了不会越界)
// 并把这个索引对应的对象赋给p
// 判断这个p是否为null
// 如果为null,就创建一个节点Node(key="java",value=PRESENT)
if ((p = tab[i = (n - 1) & hash]) == null)
// value是被共享的PRESENT对象
tab[i] = newNode(hash, key, value, null);
else {
// 开发技巧提示: 定义辅助变量时,在需要局部变量(辅助变量)的时候再创建
Node<K,V> e; K k;
// 如果当前索引位置对应链表的的第一个元素和准备添加的key的hash值一样
//满足两个条件之一:如果p指向Node的key元素和准备加入的元素是同一个对象 或者 键不为空,内容相同(equals可能被重写) 就不能加入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判断p是不是一颗红黑树
// 如果是一颗红黑树就调用putTreeVal方法,下面详解putTreeVal红黑树
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);
// 添加后,立即判断该节点是否到达8个节点
// 对当前链表,进行树化(红黑树)
// 注意,在转成红黑树时,还得进行判断表的容量必须大于64.否则先扩容表容量
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 在比较的过程中,如果有相同的直接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;
// 检查大小是否是原表的3/4.第一次就是12.超过就扩容
if (++size > threshold)
resize();
// hashmap交给子类如LinkedHashMap使用
afterNodeInsertion(evict);
// 返回null代表成功
return null;
}
### 3.1.2 扩容机制和转成红黑树机制
` 1. HashSet底层是HashMap,第一次添加时,table数组扩容到16，临界值(threshold)是16*加载因子(loadFactor)是0.75 =12`
` 2. 如果table数组使用到了临界值12,就会扩容到16*2 = 32,新的临界值就是32*0.75 = 24,依次类推`
` 3. 在Java8/11中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN TREEIFY CAPACITY(默认64),就会进行树化(红黑树)，否则仍然采用数组扩容机制`
`4.只要添加了元素,size++.也就是说总元素到达阈值就会触发扩容或树化`
`resize扩容` /**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
// 存储当前表的数据
Node<K,V>[] oldTab = table;
// 当返回0,则是初始化表.否则保存旧表的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 保存旧阈值
int oldThr = threshold;
int newCap, newThr = 0;
// 当旧数据元素>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
// 新容量默认值 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
newCap = DEFAULT_INITIAL_CAPACITY;
// 装填因子 DEFAULT_LOAD_FACTOR=0.75 ; DEFAULT_INITIAL_CAPACITY 同上注解
// 即newThr为12时扩容,有个扩容提前量作为缓冲,防止突然大量线程填入,造成堵塞
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 获得新阈值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
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;
}
`当在Java8/11中，如果一条链表的元素个数到达 TREEIFY_THRESHOLD(默认是 8 )，并且table的大小>= MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树)，否则仍然采用数组扩容机制`
`putTreeVal` /**
* Tree version of putVal.
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。用这个树结构保证了,树深较小.
很遗憾图片发不出来.今天下午整理完再发布链接
|
最佳答案
查看完整内容
你好,我刚好在总结相关知识
### 结论
- `HashSet的底层是HashMap (HashMap的底层是数组+链表结构+红黑树)`
- `HashSet不保证元素是有序的,取决于hash后，再确定索引的结果.`
- `可以存放null,但只能是一个`
- ==不能有重复的元素或值(相同的值经过hash算法得到的索引位置的值equals`equals依据程序员标准`比较.相同放弃添加,不相同,在该位置生成链表追加)==
` 1. HashSet底层是HashMap,第一次添加时,table数组扩容到16 ...
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-3-11 17:14:18
置顶卡
千斤顶
显身卡