introduction
- HashSets实现了Set接口
- HashSet:实际上是HashMap,看下源码.
public HashSet(){
map = new HashMap<>();
}- 可以存放null值，但是只能有一个null
- HashSet不保证元素是有序的，取决于hash后，再确定索引的结果.（即，不保证存放元素的顺序和取出顺序一致)
- 不能有重复元素/对象. 在前面Set接口使用已经讲过
属性
定义了一个 HashMap
private transient HashMap<E,Object> map;Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();构造器
Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75).
public HashSet() {
map = new HashMap<>();
}执行机制：
HashSet hashSet = new HashSet();进入构造器：
public HashSet() {
map = new HashMap<>();
}执行add() 方法
hashSet.add("java");public boolean add(E e) {
// PRESENT 是一个对象在HashSet 类里定义
return map.put(e, PRESENT)==null; // e:"java" map:"{}"
}进入put() 方法
public V put(K key, V value) { // key = "java", value = Object@27
return putVal(hash(key), key, value, false, true);
}进入hash() 方法
Computes key. hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.
static final int hash(Object key) { // 把 "java"传进来
int h;
// 如果为空返回 0 否则，把对象的 hash值右移16位，再与原先的hash值进行按位异或，得到新的hash值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}进入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; // 定义辅助变量
// table 就是 HashMap 的一个数组(属性)，类型是 Node[]
if ((tab = table) == null || (n = tab.length) == 0) // 第一次进来，table为 null，进入if 块内
n = (tab = resize()).length;
//(1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
//并把这个位置的对象，赋给 p
//(2)判断p 是否为null
//(2.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node (key="java",value=PRESENT)
//(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)
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;
}进入resize() 方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // table: null
int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldCap = 0
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
// 因为oldCap = 0 进入这里
newCap = DEFAULT_INITIAL_CAPACITY; // DEFAULT_INITIAL_CAPACITY = 16，所以新的容量为 16
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; // 把新的临界值赋给 threshold
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 创建了 newTab数组，容量为16
table = newTab; // 赋给 table（放node节点的数组）
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;
}到此返回。
这是 table 的情况
继续执行 add()方法
hashSet.add("php");与前面一样进入put(),之后进入 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) // 这个 if不进去了
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
//并把这个位置的对象，赋给 p
tab[i] = newNode(hash, key, value, null); // i = 9
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;
}
到此又加入一个同样的字符串"java"。
hashSet.add("java");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] = tab[3] 但是不等于null
// 根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
//并把这个位置的对象，赋给 p
tab[i] = newNode(hash, key, value, null);
else { // 所以进入else
Node<K,V> e; K k;
//如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
//并且满足 下面两个条件之一:
//(1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象
//(2) p 指向的Node 结点的 key 的equals() 和准备加入的key比较后相同
//就不能加入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //重新指向
//再判断 p 是不是一颗红黑树,
//如果是一颗红黑树，就调用 putTreeVal , 来进行添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果table对应索引位置，已经是一个链表, 就使用for循环比较
//(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
// 注意在把元素添加到链表后，立即判断 该链表是否已经达到8个结点
// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
// 注意，在转成红黑树时，要进行判断, 判断条件
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
// resize();
// 如果上面条件成立，先table扩容.
// 只有上面条件不成立时，才进行转成红黑树
//(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break
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;
}底层机制总结
在添加元素时：
- 先获取元素的哈希值(hashCode方法)
- 对哈希值进行运算，得出一个索引值即为要存放在哈希表中的位置号
- 如果该位置上没有其他元素，则直接存放；如果该位置上已经有其他元素，则需要进行equals判断，如果相等，则不再添加。如果不相等，则以链表的方式添加。
- HashSet底层是HashMap
- 添加一个元素时，先得到hash值后，会转成 → 索引值
- 找到存储数据表table,看这个索引位置是否已经存放的有元素
- 如果没有，直接加入
- 如果有，调用equals比较，如果相同，就放弃添加，如果不相同，则添加到最后
- 在Java8中，如果一条链表的元素个数到达
TREEIFY THRESHOLD(默认是8)，并且table的大小 >=MIN TREEIFY CAPACITY(默认64)，就会进行树化（红黑树）
HashSet的扩容和转成红黑树机制
- HashSet底层是HashMap,第一次添加时，table数组扩容到16，临界值(threshold)是16 * 加载因子(loadFactor) 是 0.75 = 12`
- 如果table数组使用到了临界值12，就会扩容到16 * 2=32，新的临界值就是32 * 0.75=24,依次类推
- 在Java8中，如果一条链表的元素个数到达TREEIFY THRESHOLD(默认是8)，并且tablel的大小>=MIN TREEIFY CAPACITY(默认64)，就会进行树化（红黑树），否则仍然采用数组扩容机制
Exercise
定义一个Employee类，该类包含：private 成员属性name,age 要求：
- 创建3个Employee对象放入HashSet中
- 当name和age的值相同时，认为是相同员工，不能添加到HashSets集合中
public class HashSetExercise {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add(new Employee("milan", 18));//ok
hashSet.add(new Employee("smith", 28));//ok
hashSet.add(new Employee("milan", 18));//加入不成功.
//回答,加入了几个?2个
System.out.println("hashSet=" + hashSet);
}
}
class Employee{
private String name;
private int 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.age = age;
this.name = name;
}
@Override
public String toString() {
return "Employee{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
//如果name 和 age 值相同，则返回相同的hash值
@Override
public 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);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}