这段时间在看JDK（1.8）的源码，从util包的集合开始看，首先要看的肯定是面试经常涉及的HashMap，HashSet，ArrayList等等，在这里记录一下读码时的一些疑惑以及重点。
为什么HashSet能够保证元素不唯一？
我们都知道，HashSet是能够保证插入的元素不唯一，那么其内部到底是怎样实现的呢？
先上源码：
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
//内部通过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 <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
/**
*剩下的代码...
**/
通过上述代码可以看到,HashSet的内部是由HashMap来实现的,但是HashMap是一个键值对,调用put方法都是要在key上来存放value,而HashSet的put方法为什么只有一个参数,实际上,看到那句//Dummy value to associate with an Object in the backing Map就知道了，原来HashSet内部插值时插的是HashMap的key，而HashMap的value则是这个静态常量PRESENT。那么整个HashSet代码看下来，保证HashSet内部元素唯一的一个方法就是HashSet的put方法了，该方法很简单，代码如下：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
不得不说这个锅甩的漂亮啊，仿佛听到HashSet在说，没我什么事了，去看HashMap吧，那么我们就先分析一下HashMap的put，再来看这个add。
HashMap的putVal方法
HashMap是Java中一个十分重要的数据结构，基本上所有Java开发都离不开它，那么HashMap的一个重要的功能就是不断的取数据，写数据，在这里主要看下HashMap是怎样写数据的，写数据的源码如下：
public V put(K key, V value) {
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;
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);//如果p为空，则插入新的对象，并返回null
else {
Node<K,V> e; K k; //不为空,则插入新的节点e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//如果p的key就是要修改的结点的key
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; //进行新的mapping
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null; //第一次插,返回的是null,后面再插,返回的就是oldValue;
}
HashMap内部是通过一个结点数组，Node<k,V>[]来存放键值对的，在通过计算写入对象的hash码后找到对应的index，并进行写入操作，遇到哈希碰撞则是通过链表的方式来处理，通过上述的代码可以看到HashMap插入对象的逻辑：
if 表为空或者表的大小为0，则进行resize，得到一个新表
then if 插入位置为空，则插入新的结点 //在此处做了一个赋值，将结点p指向了表的某一个位置
else if 插入位置的结点p就是要修改的结点，则新结点e指向结点p
else if 插入的结点是TreeNode，则调用TreeNode的插入方法。
else loop（对该位置存在的链表进行遍历）：
if 节点p的下一个结点为空，则插到链表后，退出循环
if 找到某一个不为空的结点，则退出循环，此时新结点e指向该结点
if 新节点不为空，则进行新的mapping，即替换值内容并返回旧值
if 表大小超过阈值，resize
返回null；
那么重点来了，当HashMap在某个位置首次插入时，由于插入位置为空，则插入了新的结点，此时直接返回null，而后续进行插入操作时，会进行新的mapping，从而返回旧值，那么我们再回头看一下HashSet的add方法：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
也就是说，HashSet里的HashMap只有第一次插值的时候会返回true，后续的都返回的false，这样就保证了HashSet中元素的唯一性。
PEACE OUT
网友评论