HashSet
HashSet()构造器
public HashSet() {
map = new HashMap<>();
}
底层new了一个HashMap，再来看Set的add()方法
add()方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
PRESENT是静态共享的，就是下面的value
调用map的put()方法，进入
put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这里执行hash(key)方法，得到key对应的hash值，这里hash值不等于hashcode值
进入putVal()方法
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等，table是HashMap的一个数组，类型是Node[]
第一个if语句处表示如果当前table是null，或者大小是0，就第一次扩容到16个空间。
第二个if语句处根据key得到hash值，去计算该key应该存到table表的哪个索引位置，并把这个位置的对象赋给p。再判断p是否为null。
- 如果p为null，表示还没有存放元素，就创建一个Node，放在该位置tab[i]。Node中存放了hash值方便未来进行比较
- 如果p不为null，则进入else语句块中，还是先创建一个Node，进入else块中的第一个if语句。
2.1 else块中的第一个if语句里，如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样，并且满足下面两个条件之一，就不能加入
a. 准备加入的key和p指向的Node结点的key是同一个对象
b. p指向的Node结点的key的equals()方法和准备加入的key比较后相同
2.2 假如上面的if返回false，表示可以加入，则进入下面的else if，判断p是不是一颗红黑树，如果是红黑树，就调用putTreeVal来进行添加
2.3 假如上面的else if也返回false，即判断不是红黑树，则进入else语句块。如果table对应索引值已经是一个链表，则for循环遍历链表，依次和链表的每一个元素比较，都不相同，则说明元素不重复，则加入到该链表的最后，同时判断是否达到8个节点，达到8个节点就调用treeifyBin()方法进行红黑树化（内部还有判断逻辑）。当然如果有相同的，则直接break
最后一个if语句处判断当前已存放的数据量是否大于threshold，即阈值，超过则调用resize()方法
紧跟着的afterNodeInsertion()方法是一个空方法，我们就不看了，这个方法是留给HashMap的子类实现，可以进行自定义的对链表的排序等操作。下面我们还是来看看resize()方法
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;
}
大家观察上面代码有一串DEFAULT_INITIAL_CAPACITY，翻译一下就是默认初始化容量，我们点进去看，如下
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
果然是移位操作，1<<4 = 16，这个很简单，大家都能理解，所以默认长度为16
还有一串DEFAULT_LOAD_FACTOR，翻一下就是默认加载因子，我们点进去看，如下
static final float DEFAULT_LOAD_FACTOR = 0.75f
果然，默认加载因子是0.75，具体原因是加载因子为0.75时根据泊松分布，每个碰撞位置的链表长度超过8的概率已经是一百万分之一，已经不太可能发生碰撞。又因为加载因子过大会加大发生碰撞几率，过小虽然减少了碰撞几率，但是增加了扩容次数，扩容会影响性能，所以定为0.75最合适。
什么时候发生扩容呢？我们发现上面还有一串代码是DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR，即上面这两个数相乘，16 * 0.75 = 12，即到12的时候会发生扩容，为了防止数据量过大的时候无法及时扩容，所以进行一次预扩容
总结
image.png
HashMap
HashMap与HashSet实现的是同一个方法，具体表现的话Set可以去重而Map可以替换是因为putVal()方法里的这一段
putVal()
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
大家也看到注释里existing mapping for key，说明此时key是有value的，是一个map结构而不是set结构，这段代码里主要就是替换了value，由此造成HashSet和HashMap的表现是不同的
JDK1.7的resize()方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
如果原有table长度已经达到上限，就不再扩容，如果还没有达到上限，就创建一个新的table，调用transfer()方法
transfer()方法
//Transfers all entries from current table to newTable.
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
transfer()方法的作用是把原table的Node放到新的table中，使用头插法，也就是说新table中链表的顺序和旧链表中是相反的，在HashMap线程不安全的情况下，头插法是有可能导致环状节点和死循环的，如下
image.png
JDK1.8的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;
}
在resize()方法中，定义了oldCap参数，记录了原table的长度，定义了newCap参数，记录新table的长度，新容量newCap是旧容量oldCap长度的2倍，同时阈值newThr也变为原来的2倍
进入到下面的for循环，遍历原table，把原table中的每个链表中的每个新元素放入新table
for循环里的第2个if语句判断e.next是否为空，判断当前链表是否只有一个元素
- 只有一个元素就放入新table
- 否则else中的注释preserve order翻译一下就是“维护秩序”，计算节点在table中的下标，认识一下定义的四个新变量
2.1 loHead，下标不变情况下的链表头
2.2 loTail，下标不变情况下的链表尾
2.3 hiHead，下标改变情况下的链表头
2.4 hiTail，下标改变情况下的链表尾
其实这里体现了JDK1.8计算节点在新table中的思路。即正常情况下，计算节点在table中的下标的方法是：hash&(oldTable.length-1)，扩容之后，table长度翻倍，计算table下标的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我们有了这样的结论：这新旧两次计算下标的结果，要不然就相同，要不然就是新下标等于旧下标加上旧数组的长度。
image.png
我们可以看到hash值的每个二进制位用abcde来表示，那么，hash和新旧table按位与的结果，最后4位显然是相同的，唯一可能出现的区别就在第5位，也就是hash值的b所在的那一位，如果b所在的那一位是0，那么新table按位与的结果和旧table的结果就相同，反之如果b所在的那一位是1，则新table按位与的结果就比旧table的结果多了10000（二进制），而这个二进制10000就是旧table的长度16。
换言之，hash值的新散列下标是不是需要加上旧table长度，只需要看看hash值第5位是不是1就行了，位运算的方法就是hash值和10000（也就是旧table长度）来按位与，其结果只可能是10000或者00000。
所以，do-while里的（e.hash & oldCap），就是用于计算位置b到底是0还是1用的，只要其结果是0，则新散列下标就等于原散列下标，否则新散列坐标要在原散列坐标的基础上加上原table长度。
(e.hash & oldCap) == 0，就是代表散列下标不变的情况，这种情况下代码只使用了loHead和loTail两个参数，由他们组成了一个链表，否则将使用hiHead和hiTail参数。其实(e.hash & oldCap) == 0和(e.hash & oldCap) != 0后的逻辑完全相同，只是用的变量不一样。
这里也看出JDK1.8采用的是尾插法，顺序和原链表顺序一致，而非倒序
总结
image.png
JDK1.7的put()方法
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);//分配数组空间
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);//调用value的回调函数，其实这个函数也为空实现
return oldValue;
}
}
modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}
第1个if处，做一个判空操作，为空则调用inflateTable创建一个哈希表
第2个if处，如果key为null，调用putForNullKey方法
紧接着用hash函数进行散列，并计算下标index，进入for循环，如果对应数据已经存在，则指向覆盖操作，用新的value替换旧的value，并return旧的value
最后modCount用于计数防止并发，调用addEntry添加一个新的Entry结点
JDK1.7的get()方法
public V get(Object key) {
// 判断key是否为null
if (key == null) {
return getForNullKey(); // 直接去table[0]查找
}
// 否则 通过key获取获取对应下标的数组
Entry<K,V> entry = getEntry(key);
// 返回value
return null == entry ? null : entry.getValue();
}
开头也是先判断key是否为null，为null则调用getForNullKey，与上面put方法中为null时对应
不为null则获取对应的下标数组，调用getEntry方法
getEntry()方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 根据key获取hashcode值
int hash = (key == null) ? 0 : hash(key);
// 通过indexFor()计算下标， 获取对应数组下标的Entry对象, 并遍历
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
// 判断hash值是否相同 key是否一样
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
如果Map的大小为0，返回null
否则计算hash值，for循环中计算下标，最后判断hash和key的值是否相同，相同则返回对应的entry，否则返回null
回到上面的get()方法，为null则返回null，否则返回entry的value值
JDK1.8的put()方法
上面已经分析过，不再赘述
JDK1.8的get()方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
调用getNode()方法
getNode()方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 计算存放在数组table中的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 4. 通过该函数，依次在数组、红黑树、链表中查找（通过equals（）判断）
// a. 先在数组中找，若存在，则直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// b. 若数组中没有，则到红黑树中寻找
if ((e = first.next) != null) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// c. 若红黑树中也没有，则通过遍历，到链表中寻找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
第一个if处，如果table不为null，且长度大于0，且first变量等于（长度 - 1）& （hash值）不为null时，进入第2个if
第2个if处，判断第一个结点first的hash值和key是否与参数相等，为真则返回第一个结点
若第2个if为假则来到第3个if处判断节点数量
若节点数量不为1，则进入第4个if处进行红黑树的查找
若第3个if为真，第4个if为假，则进入do-while循环，在链表中寻找。和第2个if的判断条件一致，找到则返回e，否则进入循环，找链表的下一个结点
总结与比较
1.7put()方法
-
判断列表是否为空
1.1 为空则初始化，初始化后判断参数key是否为null
1.2 不为空则直接判断参数key是否为null -
参数key若为null，则遍历数组索引为0处是否能找到key为null的元素
2.1 找到则替换并返回
2.2 找不到则直接返回null -
参数key若不为null，对参数进行hash后计算下标，遍历数组判断是否有hash值相同且key相同，或者调用equals()方法后相同的位置
3.1 如果有相同的，则替换旧元素并返回
3.2 如果没有相同的，则先判断当前数组大小是否超过阈值 -
如果超过阈值，则数组扩容为原来的2倍，并重新按上述步骤计算插入的位置
-
如果没有超过阈值，则直接插入链表头部
image.png
先扩容，再插入
1.8put()方法
-
先计算hash值
-
判断是否为空表
2.1 若为空表，则进行resize操作
2.2 若不为空表，则取hash与数组长度 - 1进行与操作计算存储位置 -
判断存储位置结点位置是否为null
3.1 若为null则直接赋值，并判断赋值后存储元素数量是否大于阈值，大于则扩容，小于则返回null
3.2 若不为null则查看第一个元素是否hash和key与参数相同 -
若相同则覆盖旧结点
-
若不相同则查看是否为树结点
5.1 是则调用红黑树的put
5.2 不是则遍历看是否能找到key与hash值与参数相同的元素 -
没找到则在链表末尾插入新结点，同样判断长度是否大于8，是否需要树化等一系列操作
-
找到则覆盖旧结点
image.png
先插入，再扩容
1.7get()方法
-
先判断key是否为null
1.1 是则调用getForNullKey()方法，放在索引为0处
1.2 不是则调用getEntry()方法，并计算hash值，indexFor()方法计算下标 -
进而判断链表是否存在
2.1 存在则查找链表中是否有key为null的结点，是则返回其value
2.2 链表不存在或链表中不存在null结点则直接返回null
image.png
1.8get()方法
-
先计算hash值
-
调用getNode()方法，判断HashMap的table是否为null
2.1 不为null则判断其长度是否大于0。大于0则与运算计算索引
2.2 为null或table长度不大于0则返回null -
判断哈希表对应索引上的元素是否为空
3.1 不为空则先判断首结点是否与参数一致
3.2 为空则返回null -
若与参数一致则判断节点后个数是否大于1
4.1 大于1则判断是否为树节点，是就遍历红黑树
4.2 小于1则返回null。不是红黑树则遍历链表 -
查找红黑树或链表是否存在与参数相同的节点
5.1 不存在则返回null
5.2 存在则返回其value
image.png
hashcode和hash的区别与联系
hashcode在HashMap中实现的是Object类型的hashcode方法，使用key的hashcode与上value的hashcode得出
hash则是通过hashcode进行高十六位与低十六位异或运算得出，目的是为了让int类型的hashcode转换为32位比特位后，所有位都可以参与运算，增加散列程度
而最终确定的index下标值则是hash与上数组长度 - 1得出的值
部分参考：lkforce，b站【韩顺平讲java】
欢迎指正。
网友评论