Set
前面写过一篇有关Set的笔记，发现写的过于基础，没有说明重点，在此重新更新一篇。
Set是一个不允许有重复元素出现的线性数据结构，它的实现类有：AbstractSet ， ConcurrentHashMap.KeySetView ， ConcurrentSkipListSet ， CopyOnWriteArraySet ， EnumSet ， HashSet ， JobStateReasons ， LinkedHashSet ， TreeSet。在这里我们主要讲解我们常用的HashSet,TreeSet.
HashSet
HashSet是基于HashMap来实现的，它的大部分操作都是使用HashMap来处理的，
public HashSet() {
map = new HashMap<>();
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
} 等等，HashSet的所有构造函数，都是通过HashMap，或LinkedHashMap来实现,相关的操作，eg:isEmpty(),size(),iterator()方法都是通过调用全局的map的相关方法来实现的，而这个map实例化则是通过构造函数来完成。
HashMap
HashMap继承AbstractMap,实现Map接口，Map是一种键值对<Key,Value>的方式来存储数据。
常量有：
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 装载因子：0.75，一种用来判断已有数据量占总数据量的程度，即等于 已有数据/总的数据。
最大容量：则是指明HashMap能存放的最大数据量。
默认初始大小：默认的初始大小为16。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
......
......
......
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
transient Node<K,V>[] table; 省略号代表中间有代码，我只不过截取想要解释的代码。
我们可以看出HashMap是一个数组，数组中的元素是Node实例，Node则是一个实现Map.Entry<K,V>的实现类，Node是一个链表，每个元素都有指向下一个元素的地址。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
} 空参构造函数，使用的装载因子为0.75，容量为默认的 DEFAULT_INITIAL_CAPACITY = 1 << 4，即16。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} 带有初始容量的构造器：则会调用另一个构造器，实例的实际容量大小还需要进行比较，才可以得出：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
如果容量为0或装载因子小于0或无限大，抛出异常；初始容量大于MAXIMUM_CAPACITY，则intialCapacity等于MAXIMUM_CAPACITY；threadshold为数组的实际大小容量，通过tableSizeFor函数计算，
注意：tableSizeFor这个函数，是为了求的大于输入参数且最近的2的整数次幂的数,并返回。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
} 这个算法效率特别高，简单解释就是：它将数据依次无符号右移，然后进行位或运算，最高位的1后面的位全变为1。n+1，得到了2的整数次幂的值了。网上有有关这个算法的解释，建议看看，（这就是阅读源码的好处）
threshold的值为HashMap的容量的大小；所以传入的initialCapacity并不是HashMap的大小，实际大小为大于initialCapacity的2的整数次幂，即例如7，则返回8。
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) {
......
return null;
}
put方法传入Key,Value值，然后调用内部的putVal方法进行实际的添加元素操作。源码放在这，有点长，所以建议亲自读取，这里进行解释：
putVal(int hash, K key, V value, boolean onlyIfAbsent boolean evict)
形参onlyIfAbsent表示是否改变存在的值，如果为true,则不改变存在的值，如果为false，则改变；
形参evict表示表所处的模式，如果为false，则说明table处于创建模式.
⑴先判断table数组是否为null或table的长度为0，如果为空或为0，则调用resize()方法创建table，
⑵接下来根据hash值和table大小-1做与运算，求出Entry的下标位置，如果为null,则证明该位置没有元素，则在此位置创建新的节点，如果不为null,则证明该位置已经有Entry对象，判断key是否等于第一个元素的key,hash值是否相等，如果相等，则将该节点赋值给这个元素，如果不相同，则证明该节点的key不在链表头，因此对链表进行遍历，找到key和hash相同的节点，则赋值，如果一直没有找到，则将其插入到链表的尾部。如果节点属于TreeNode类，则使用putTreeVal（)方法进行存储。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get方法，先根据Key的值，计算hash，找到数组的位置，如果位置为null，返回null,否则计算出元素在table数组中的位置，然后遍历在该位置的链表，从头到尾遍历，找到key和hash相同的node节点，返回val值，如果没有，返回null。
remove方法过程与get类似。
HashSet线程不安全。
TreeSet
TreeSet基于TreeMap实现，支持排序。
public TreeSet() {
this(new TreeMap<>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
} TreeSet的实例的实现都是通过TreeMap实现。
TreeSet的其他方法，eg：size,isEmpty,contains等都是通过NavigableMap<E,Object> m实例调用具体的方法进行，NavigableMap是一个接口，而TreeMap则是NavigableMap接口的实现类，这里通过多态的方式来进行访问，在TreeSet中使用接口定义实例，而在构造方法中，将具体的实现类TreeMap赋值给NavigableMap变量。
TreeMap
实现NavigableMap接口，
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
...... TreeMap空参构造器，将comparator置为null;
TreeMap(Comparator comparator)参数，接受一个Comparator实现类，可以自定义TreeMap中元素的存储顺序。
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
......
TreeMap是基于红黑树的实现，它的每个节点都有其左，右，父节点的指向。红黑树是一个平衡的二叉搜索树。如果红黑树失去平衡，则必须通过旋转令其恢复平衡。
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
} TreeMap的get(key)通过调用内部的getEntry(key)方法，来匹配树中是否有此key的节点，有则输出其val值，没有则返回null。对于getEntry(key)方法，首先判断key是否null,然后检查key是否实现了Comparable接口，因为树的比较就是基于Comparable接口的comparaTo()方法来进行比较，对树从根节点root进行遍历，如果key大于比较节点，则将从右边部分开始遍历，如果key小于被比较的节点，则从左边部分遍历，类似与二分法。因为红黑树是一个二叉搜索树，每个节点大于它的左部分，小于它的右部分。
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
......
}
......
return null;
}
先判断树是否为null，如果为空，则直接将元素作为根节点，然后判断是否有comparator传入进来，这个comparator变量是TreeMap在开头定义的，只有定义，没有实例化，而具体的实例化是通过构造函数中携带的Comparator实例，如果有，即传入comparator实例，则以次来进行比较，使用二分法，来找到具有相同key，并直接替换其value,如果没有找到相等的key，则创建一个新的Entry对象，将其插入到特定的位置，如果comaprator为null,则判断key是否为Null，如果为null，抛出空指针异常，否则则将key转为Comparable，因为很多类都实现了Comparable接口，进行同样的遍历。
TreeMap不是线程安全的。
总结的代码来自jdk1.8源代码，如有问题，敬请指出，与君共勉。
京公网安备 11010502036488号