Java集合类HashSet
世界尽头与你 人气:01.Set接口方法
Set接口对象存放的数据是没有重复，且数据是无序存放的（添加顺序和存放顺序不一致，但是这个存放的顺序是固定的，不会随机变化）
代码示例：
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/**
* Set接口方法
*/
public class SetTest {
@SuppressWarnings({"all"})
public static void main(String[] args) {
Set set = new HashSet();
// 添加
set.add("dahe");
set.add("wangwei");
set.add(521);
set.add(521);
set.add(null);
System.out.println(set);
// 遍历Set
// 迭代器
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
System.out.println(obj);
}
// 增强for
for (Object o : set) {
System.out.println(o);
}
}
}
2.HashSet
HashSet的底层其实，是HashMap：维护的是一个数组 + 单向链表
public HashSet() {
map = new HashMap<>();
}
HashSet不保证存放元素的顺序和取出的顺序一致，这取决于hash后，再确定索引的结果
代码示例：
import java.util.HashSet;
import java.util.Set;
/**
* HashSet
*/
public class HashSetText {
@SuppressWarnings({"all"})
public static void main(String[] args) {
Set hashSet = new HashSet();
// 添加
hashSet.add("dahe");
// 添加成功，返回true，失败返回false
System.out.println(hashSet.add("qian"));
System.out.println(hashSet.add("qian"));
System.out.println(hashSet);
// 添加对象，以下是不同的对象
hashSet.add(new DDD("aaa"));
hashSet.add(new DDD("aaa"));
System.out.println(hashSet);
// 经典面试题，以下的两个只能添加一个
hashSet.add(new String("hsp"));
hashSet.add(new String("hsp"));
System.out.println(hashSet);
}
}
class DDD {
private String name;
public DDD(String name) {
this.name = name;
}
@Override
public String toString() {
return "DDD{" +
"name='" + name + '\'' +
'}';
}
}
3.HashSet的扩容机制 - 初次添加数据
针对如下的代码对java的扩容机制进行分析：
hashSet.add("dahe");
System.out.println(hashSet.add("qian"));
System.out.println(hashSet.add("qian"));
执行add操作：（传入待添加的值e和PRESENT，这里的PRESENT只起到一个占位的效果）
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
继续步入：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在进入putVal方法之前，我们先来看一下这个hash的算法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
如果待添加的数据为null，则返回0值，否则返回hash算法的结果（此算法可以极大的防止冲突的发生）
执行putVal方法：这个方法很重要（且复杂）！
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}不要慌，我们来一步一步进行分析：
先来看一下这个东西：
Node<K,V>[] tab;
这个是存放Map Node节点的数组，如果你精通数据结构邻接表，对这个数组应该很熟悉，tab里面的存储结构是这样的：（下图仅作示例）
当这个节点数组为空或者大小为0的时候，会触发这个操作：（tab先进行resize操作，随后返回给n一个处理后数组的大小）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
那这个resize操作到底是什么呢？我们步入来看看它的真面目：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
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
newCap = DEFAULT_INITIAL_CAPACITY;
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;
}由于初始化tab为null，经过一番操作，会执行如下的代码，这里给计算了新数组的空间大小：
newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
DEFAULT_INITIAL_CAPACITY的定义，默认表的大小为16：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
下面这里是JDK设计者的聪明所在，tab数组并非用到空之后扩容，而是内部有一个临界的值newThr，所用的空间达到临界的值会触发扩容机制 （容量*2），起到一个缓冲的效果，这样做主要是为了防止阻塞
注意：这里的空间指的是全部节点的数量，而非tab元素的个数
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
一切准备就绪，开始扩容（这里初始化扩容的tab容量为16）：
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab;
我们再回到putVal方法，看一下接下来会发生什么有趣的事情
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
根据key得到hash，去计算该key应该存放到table表的那个索引位置，并把这个位置对象赋值给p，如果p为null的话，表示该索引位置还没有存放过任何的数据，就在tab[i]位置创建一个Node，创建完新Node之后，它在tab数组中的存储结构就变成了这样：
继续向下走，修改次数 + 1，并且还要判断一次tab元素数量是否大于了临界值，如果大于了临界值，进行扩容操作：
++modCount;
if (++size > threshold)
resize();
最后，返回null，代表一切操作成功！
至此，初次添加数据的操作就已经完成了！
4.HashSet的扩容机制 - 继续添加数据
初次添加数据的结构其实很简单，更加困难的是第二次添加数据的操作
我们继续步入，再次追到putVal方法：
和初次添加不同的是，不会再进入下面的语句，而是向下执行：
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
直接判断计算得出的tab索引位置有没有数据，没有的话（实验的值没有）继续新建节点：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
添加完数据后，tab里面的结构就变成了这样：
5.HashSet的扩容机制 - 添加重复元素
此时存在两个key是相等的，那么下面的语句必然不会为空，因为key相等，那么他们hash过后的值也会相等：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
继续步入，走到else里面，我们来看一下if语句里面的内容：
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
并且满足准备：（比较地址和值）
- 加入的key和p指向的Node节点的key是同一个对象
- 不是同一个对象，但是通过equals比较过后相同
这时就不能加入，执行：e = p;
再来看看else if语句：
判断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;
}
当前索引位置已经是一个链表。会依次和该链表的每一个节点进行比较，有重复的直接break掉，没有重复的进行挂载
注意：在添加新节点之后，需要进行一次链表长度判断，看下当前链表中是否已经有8个节点了，如果已经存在了8个节点，会通过treeifyBin方法尝试进化链表为红黑树
有趣的是，在进化红黑树的代码中，存在下面这两行：
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
这里面的MIN_TREEIFY_CAPACITY定义如下：
static final int MIN_TREEIFY_CAPACITY = 64;
也就是说，如果tab长度小于64，不会马上进行树化，会先进行tab扩容操作！
加载全部内容