Set
Set集合實現(xiàn)框架：
Set是一種無序不重復(fù)的集合徘铝，它最多只允許有一個null元素。Set接口繼承Collection接口惯吕，因為Set是無序的所以我們可以看到它的接口沒有跟游標(biāo)有管的方法惕它。Set的遍歷完全依賴迭代器來Iterator來完成。
Set有兩個有兩個子接口巾陕，SortedSet和NavigableSet毕荐，SortedSet提供了set集合的排序功能郁妈，NavigableSet擴(kuò)展了SortedSet接口，提供了支持基于最接近匹配原則檢索元素的行為甲锡。
HashSet
HashSet是擴(kuò)展了Set接口，HashSet使用了Hash表作為支持(實際是HashMap)羽戒。如果散列均勻到到不同的桶的haul缤沦，HashSet的add、remove易稠、contains和size方法的時間復(fù)雜度為O(1)疚俱。HashSet的迭代時間等于列表長度+桶數(shù)，所以如果迭代很重要缩多，在初始化HashSet的時候應(yīng)該將其設(shè)置的初始容量設(shè)置的小一些呆奕，或者將負(fù)載因子設(shè)置的小一些(如果負(fù)載因子大的話，桶的個數(shù)就多)衬吆。
HashSet底層是使用HashMap實現(xiàn)的梁钾，所以存儲數(shù)據(jù)變量為map。
private transient HashMap<E,Object> map;
HashSet提供了6中構(gòu)造方法逊抡，主要參數(shù)就是初始容量大小和負(fù)載因子姆泻。
public HashSet() {
//初始化容量為HashMap默認(rèn)容量16零酪，負(fù)載因子為HashMap默認(rèn)負(fù)載因子0.75
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
//以指定集合元素作為新建的HashSet初始值，最少為HashMap的默認(rèn)值16拇勃，如果大于默認(rèn)值則為集合c的1.75倍容量
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
//指定初始容量和負(fù)載因子
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
//指定初始用量
map = new HashMap<>(initialCapacity);
}
//使用LinkedHashMap作為HashSet底層存儲
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
HashSet將元素作為HashMap的key進(jìn)行存儲四苇，所有操作都是針對HashMap的key進(jìn)行操作。
public Iterator<E> iterator() {
//返回map key的迭代器
return map.keySet().iterator();
}
public int size() {
//返回map個數(shù)
return map.size();
}
public boolean isEmpty() {
//判斷map是否為空
return map.isEmpty();
}
public boolean contains(Object o) {
//判斷map的是否包含指定key
return map.containsKey(o);
}
public boolean add(E e) {
//將添加值作為map的key存儲
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
public Spliterator<E> spliterator() {
return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
}
HashSet也不是線程安全的方咆，可以在構(gòu)造時添加同步操作月腋。
Set s = Collections.synchronizedSet(new HashSet(...));
LinkedHashSet
LinkedHashSet繼承HashSet，它主要使用了HastSet的最后一個構(gòu)造方法瓣赂，創(chuàng)建LinkedHashMap榆骚。所以LinkedHashSet底層采用的LinkedHashMap進(jìn)行操作。
//使用LinkedHashMap作為HashSet底層存儲
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
LinkedHashSet的操作方法都是繼承HashSet的煌集。
TreeSet
TreeSet是基于TreeMap實現(xiàn)的NavigableSet有序集合妓肢，我們上面說了NavigableSet擴(kuò)展了SortedSet接口，它能夠保證元素有序苫纤，并且提供了最近匹配檢索元素碉钠。元素順序可以按照自然順序(升序)，或者提供比較器卷拘。
需要注意TreeSet中添加是引用類型元素放钦，我們可以通過實現(xiàn)它的comapreTo方法來保證存取順序。如果compareTo返回1(正數(shù)即可)恭金，則會按照添加元素的順序進(jìn)行存儲操禀，如果返回-1(負(fù)數(shù)即可)則會按照添加元素的倒序進(jìn)行存儲，如果返回0則添加完第一個元素后横腿，后面所有元素都不會添加進(jìn)去了颓屑。我們也可以指定排序方法，這樣就會對元素進(jìn)行排序耿焊。
TreeSet為基本操作保證O(logn)時間開銷揪惦。
注意這里提供了許多NavigableSet中定義的匹配檢索最近元素的方法，比如taiSet罗侯、subSet器腋、headSet等。
TreeSet底層實現(xiàn)方式和HashSet一樣钩杰，直接操作的TreeMap纫塌。
其它Set
除了上面說的Set，Java還提供了一下基類Set讲弄。
CopyOnWriteArraySet措左，它底層采用CopyOnWriteArrayList實現(xiàn)。它是線程安全的Set避除，它適合用于小數(shù)據(jù)量集合怎披，并且讀操作遠(yuǎn)遠(yuǎn)超過修改操作胸嘁，因為修改操作代價很昂貴，需要復(fù)制數(shù)組凉逛。
用于枚舉操作的EnumSet性宏，EnumSet保證值存儲單個枚舉類型的元素。EnumSet底層使用Enum變量存儲數(shù)據(jù)final Enum<?>[] universe;状飞。EnumSet是抽象類毫胜，它主要被用于JumboEnumSet和RegularEnumSet。
基于ConcurrentSkipListMap的實現(xiàn)的NavigableSet的實現(xiàn)類ConcurrentSkipListSet昔瞧，它是線程安全的，并且元素有序菩佑。
Map集合框架
Map和Collection是同一級別的集合框架接口自晰，Map定義了一組鍵值對的映射。Map中鍵值是唯一的稍坯，并且每一個鍵對應(yīng)一個映射值酬荞。Map中的元素順序取決于迭代器的迭順序，有的實現(xiàn)類保證了輸入瞧哟、輸出時的順序混巧，比如TreeMap；有的實現(xiàn)類則是無序勤揩，比如HashMap咧党。
Map提供了三種視圖來幫助分析Map：keySet、values和Entry陨亡。
keySet是Map中鍵的集合傍衡，它使用Set保存，所以不允許重復(fù)负蠕，所以存儲的鍵值需要重寫equals和hashCode方法蛙埂。可通過Map.keySet()獲取鍵值集合遮糖。
values是Map中值的集合绣的，它以Collection形式保存，因此可以重復(fù)欲账÷沤可以通過Map.values()獲取值集合。
Entry是Map中存儲鍵值對的實體赛不，它是Map中內(nèi)部定義的數(shù)據(jù)結(jié)構(gòu)盼理。通過Map.entrySet()可以的得到一組Entry集合保存在Set中。
下面是Map接口定義的方法：
- int size()：返回Map元素個數(shù)俄删，最大值為Interger.MAX_VALUE宏怔。
- boolean isEmpty()：如果map集合為空奏路，則返回true。
- boolean containsKey()：如果map保證指定key值臊诊，則返回true鸽粉。
- boolean containsValue()：如果map包含指定value值，則返回true抓艳。
- V get(Object key)：返回map映射中key對應(yīng)的值触机，如果不存在該鍵，則返回null玷或。
- V put(K key,V value)：將指定kv存儲到map中儡首，如果已經(jīng)存在對應(yīng)的key，則新value會覆蓋舊value值偏友。
- V remove(Object key)：刪除指定key對應(yīng)的鍵值對蔬胯，并返回該鍵對應(yīng)的value，如果不存在對應(yīng)的key位他，則返回null氛濒。
- void putAll(Map<? extends K,? extends V> m)：將指定Map中的映射復(fù)制到調(diào)用map中，它實際調(diào)用的是put方法鹅髓。
- clear()：清除map中所有的映射關(guān)系舞竿。
- Set<K> keySet()：返回key的集合。
- Collection<V> values()：返回映射的值集合窿冯。
- Set<Map.Entry<K,V>> entrySet()：返回map映射的實體集合骗奖。
- equals(Object o)：比較兩個Map映射是否相等。
-
hashCode()：返回map的hash值醒串，該hash值是每個Entry實體哈希值的總和重归。
除了上面這些基礎(chǔ)方法，Java在JDK8又新增了一些方法厦凤，這些方法都是接口默認(rèn)方法實現(xiàn)鼻吮。
image.png
Map接口還定義了內(nèi)部接口Entry，下面是Entry中定義的方法较鼓。
Set替代了Dictionary抽象類椎木，作為映射的頂級接口。
可以使用Map類型作為映射的value博烂，但是禁止使用Map類型作為key香椎。因為太復(fù)雜equals和hashCode方法很難確定。還有就是應(yīng)該盡量避免key是可變的禽篱，因為這樣會造成map的混亂畜伐。
AbstractMap
AbstractMap是Map接口的核心實現(xiàn)抽象類，這樣以后map就不需要重新實現(xiàn)這些方法了躺率。當(dāng)我們要實現(xiàn)一個不可變Map時玛界，可以直接繼承該抽象類万矾。如果想要實現(xiàn)可變的Map映射，則還需要覆蓋put方法慎框。因為AbstractMap中定義的put方法是不允許操作的良狈。
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
AbstractMap中定義了唯一抽象方法entrySet，所以子類都需要重寫這個方法笨枯，這個方法是返回Map中所有映射實體的集合薪丁。AbstractMap中其它方法，都是基于該方法返回的Set<Entry<K,V>>來實現(xiàn)的馅精。
public abstract Set<Entry<K,V>> entrySet();
AbstractMap中定義了兩個變量严嗜，用來存儲鍵集合和值集合。transient表示該變量不可序列化洲敢，volatile表示并發(fā)環(huán)境的線程可見性漫玄。
transient volatile Set<K> keySet;
transient volatile Collection<V> values;
下面是AbstractMap具體方法實現(xiàn)：
//Set集合中Entry個數(shù)就是map中映射的個數(shù)
public int size() {
return entrySet().size();
}
public boolean isEmpty() {
//長度為0就是為空
return size() == 0;
}
public boolean containsValue(Object value) {
//獲取Entry的迭代器，然后通過Entry.getValue()來獲取映射值
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
//分是否為null進(jìn)行判斷
if (value==null) {
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}
public boolean containsKey(Object key) {
//獲取Entry的迭代器沦疾，然后通過Entry.getKey來判斷是否存在指定key
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
//通過這里來看可以知道称近，Map中的key是允許為null的第队。
if (key==null) {
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
if (e.getKey()==null)
return true;
}
} else {
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return true;
}
}
return false;
}
public V get(Object key) {
//獲取Entry的迭代器
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
//通過key的equals來比較key是否相同
if (key.equals(e.getKey()))
return e.getValue();
}
}
//如果沒有找到哮塞，則返回null
return null;
}
public V remove(Object key) {
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
Map.Entry<K,V> correctEntry = null;
//查找要刪除的Entry
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Map.Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Map.Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
//存儲要刪除的value，如果沒有找到要刪除的映射凳谦，則返回null忆畅。找到的話則返回刪除key對應(yīng)的value。
V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}
public void putAll(Map<? extends K, ? extends V> m) {
//遍歷指定的map尸执，然后調(diào)用put方法家凯。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
public void clear() {
//直接使用Set的clear()方法
entrySet().clear();
}
public Set<K> keySet() {
//如果key為空，則返回一個空的set集合
if (keySet == null) {
keySet = new AbstractSet<K>() {
//AbstractSet中的抽象方法iterator方法實現(xiàn)
public Iterator<K> iterator() {
return new Iterator<K>() {
//直接使用entrySet的迭代器
private Iterator<Map.Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
}
return keySet;
}
public Collection<V> values() {
//如果值集合為空如失，則返回一個新建的Collection
if (values == null) {
values = new AbstractCollection<V>() {
public Iterator<V> iterator() {
return new Iterator<V>() {
private Iterator<Map.Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public V next() {
return i.next().getValue();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object v) {
return AbstractMap.this.containsValue(v);
}
};
}
return values;
}
除了上面基本方法绊诲，還有就是提供equals和hashCode：
public boolean equals(Object o) {
if (o == this)
return true;
//先判斷類型
if (!(o instanceof Map))
return false;
Map<?,?> m = (Map<?,?>) o;
//在判斷長度，能夠有效提高比較效率
if (m.size() != size())
return false;
try {
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
//比較key和value相同才相等
Map.Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(m.get(key)==null && m.containsKey(key)))
return false;
} else {
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}
public int hashCode() {
int h = 0;
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
//map的hash值為所有Entry哈希值的和
while (i.hasNext())
h += i.next().hashCode();
return h;
}
除了這些方法褪贵，AbstractMap還定義了兩個內(nèi)部靜態(tài)類SimpleImmutableEntry和SimpleEntry掂之，它們實現(xiàn)了Entry接口，分別表示不可邊的實體Entry和可變的Entry脆丁，二者唯一的區(qū)別就是setValue方法的支持和不支持世舰。
HashMap
HashMap是使用哈希表(hash table)實現(xiàn)的鍵值對集合，它繼承AbstractMap抽象類和實現(xiàn)了Map接口槽卫。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap在功能上和HashTable一樣跟压，只不過HashMap不是同步操作，而且HashMap允許鍵值為null歼培。
HashMap的特殊存儲結(jié)構(gòu)震蒋，使得獲取指定元素前茸塞，需要經(jīng)過哈希計算，得到目標(biāo)元素在哈希表中的位置喷好，然后在進(jìn)行少量的比較即可得到元素翔横。
當(dāng)發(fā)生哈希沖突時，HashMap采用拉鏈法進(jìn)行解決梗搅，所以HashMap的底層實現(xiàn)其實是數(shù)組+鏈表禾唁。
下面我們看一下HashMap的具體實現(xiàn)。
HashMap中定義了下面13個變量:
- 默認(rèn)初始容量16无切，比如為2的整數(shù)倍
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- 最大容量2^30荡短，所以map大小為2 ~ 2^30 中間的偶數(shù)個。
static final int MAXIMUM_CAPACITY = 1 << 30;
- 哈希表的默認(rèn)負(fù)載因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 樹型閾值哆键，當(dāng)使用樹而不是使用列表時使用掘托，必須大于2。JDK1.8新增
static final int TREEIFY_THRESHOLD = 8;
- 非樹形閾值(TODO)籍嘹，JDK1.8新增
static final int UNTREEIFY_THRESHOLD = 6;
- 樹的最小容量闪盔，至少是TREEIFY_THRESHOLD的4倍，避免擴(kuò)容時沖突辱士。
static final int MIN_TREEIFY_CAPACITY = 64;
- 哈希表中的鏈表數(shù)組泪掀。
transient Node<K,V>[] table;
- 緩存的鍵值對集合，另外兩個視圖在AbstractMap中的values()和keySet()中颂碘。
transient Set<Map.Entry<K,V>> entrySet;
- map中的長度
transient int size;
- HashMap的修改次數(shù)异赫，用來保證快速失敗(fail-fast)
transient int modCount;
- 下次需要擴(kuò)容的值，等于容量 * 負(fù)載因子
int threshold;
- Hash表的負(fù)載因子
final float loadFactor;
其中Node[K,V] table是HashMap底層存儲的鏈表數(shù)組头岔，在JDK1.8之前這也是唯一存儲數(shù)據(jù)結(jié)構(gòu)塔拳。Node實現(xiàn)了Map.Entry接口。Node的定義就是鏈表的定義加上實現(xiàn)了Entry中的方法峡竣。
static class Node<K,V> implements Map.Entry<K,V> {
//哈希值靠抑，就是位置
final int hash;
//存儲的鍵
final K key;
//存儲的值
V value;
//指向下一個節(jié)點的指針
HashMap.Node<K,V> next;
Node(int hash, K key, V value, HashMap.Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//哈希值為鍵和值哈希值的異或
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
//kv相等才相等
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
HashMap擴(kuò)容開銷是非常大的(重新創(chuàng)建數(shù)組、重新哈希适掰、分配等等呢個)颂碧，所以我們應(yīng)該盡量減少擴(kuò)容次數(shù)。與擴(kuò)容有關(guān)的兩個因素：
- 容量：數(shù)組的容量攻谁。
- 加載因子：決定了HashMap中元素占有多少比例時擴(kuò)容稚伍。
HashMap的默認(rèn)加載因子是0.75，這是在時間和空間兩方面的考慮戚宦。加載因子太大的話个曙，產(chǎn)生沖突的可能性就會很大，查找的效率就會降低。太小的話垦搬，需要頻繁rehash呼寸，導(dǎo)致性能低寨昙。
加載因子表示哈希表中元素填滿的程度猜年，加載因子越大雨膨，填充的元素越多淑趾，導(dǎo)致沖突的概率也會越大，查找效率也會越低他匪，但是空間利用率會提高末荐。如果加載因子越少嚎卫，則填充的元素少栅干，導(dǎo)致沖突的概率也會越小迈套，查找的效率會提高，但是空間利用率會降低碱鳞。
HashMap提供了四個構(gòu)造方法：
//指定初始容量和加載因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//容量最多為2^30個
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//加載因子需要大于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//指定容量
public HashMap(int initialCapacity) {
//使用默認(rèn)加載因子
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用默認(rèn)容量和默認(rèn)加載因子
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//創(chuàng)建一個內(nèi)容為m映射
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
我們看到上面第三個構(gòu)造方法調(diào)用了tableSizeFor方法桑李，該方法是根據(jù)你傳入的容量，計算出最接近你傳入初始容量的2^n窿给。比如傳入是5贵白，則返回8。
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;
}
接下來我們看看添加kv操作：
//將指定kv添加到Map中
public V put(K key, V value) {
//需要先調(diào)用hash方法計算hash值
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//哈希表的一個引用
HashMap.Node<K,V>[] tab;
//插入kv的節(jié)點
HashMap.Node<K,V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果插入位置為空崩泡，則新建一個鏈表節(jié)點
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果插入位置不為空則有兩種情況：插入key已經(jīng)存在或該key是產(chǎn)生hash沖途的鏈表內(nèi)
HashMap.Node<K,V> e; K k;//e為當(dāng)前插入節(jié)點
//拿出鏈表的第一個節(jié)點進(jìn)行匹配禁荒，如果匹配成功則直接返回給e(對于引用類型需要使用equals比較，基礎(chǔ)類型使用==比較)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果第一個節(jié)點不為目標(biāo)節(jié)點允华，并且該節(jié)點類型是樹形(JDK1.8后)則新增節(jié)點到樹中
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//遍歷鏈表
for (int binCount = 0; ; ++binCount) {
//如果遍歷到最后圈浇，則直接將新節(jié)點添加到鏈表后面
if ((e = p.next) == null) {
//新節(jié)點
p.next = newNode(hash, key, value, null);
//當(dāng)鏈表中節(jié)點個數(shù)大于8時寥掐，就需要樹型化靴寂，提高效率
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果匹配到則直接停止，此時e已經(jīng)指向了對應(yīng)節(jié)點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//替換舊節(jié)點
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//記錄修改次數(shù)
++modCount;
//如果超過閾值則進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上述流程可以總結(jié)如下：
- 先調(diào)用hash()方法計算哈希值召耘。
- 然后調(diào)用putVal()方法根據(jù)哈希值進(jìn)行相關(guān)操作百炬。
- 如果當(dāng)前鏈表為空，則新建一個鏈表污它。
- 如果插入的桶中沒有元素剖踊，則新建一個節(jié)點放進(jìn)去。
- 匹配桶中鏈表第一個元素衫贬，如果匹配成功德澈，則直接替換新節(jié)點，結(jié)束查找固惯。
- 如果第一個元素梆造，并且第一個元素是JDK8以后的樹型節(jié)點，則調(diào)用putTreeVal()將新數(shù)據(jù)插入到樹中葬毫。
- 否則從傳統(tǒng)鏈表中查找镇辉、替換屡穗。
- 當(dāng)當(dāng)前鏈表長度大于8時，調(diào)用treeIfyBin()忽肛，將鏈表樹形話村砂。
- 最后檢查是否需要擴(kuò)容
上面設(shè)計的方法：
- hash()：計算哈希值，也就是數(shù)組中對應(yīng)的位置
- resize()：擴(kuò)容
- putTreeVal()：向樹型節(jié)點添加元素
- treeIfByBin()：樹形化容器
我們先看一下上面計算hash值的方法屹逛。hash方法將當(dāng)前key的哈希值與該哈希值右移16位的結(jié)果進(jìn)行異或础废。之所以這么做是因為，元素的hashCode在很多時候低位是相同的罕模，這將容易導(dǎo)致沖突色迂。將key的hashCode與hashCode值右移16位進(jìn)行異或，效果如下：
代碼實現(xiàn)如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這樣能夠避免只依靠低位計算的結(jié)果導(dǎo)致沖突手销，將高低位結(jié)合能夠避免哈希值的分布不均歇僧。
resize()是初始化或擴(kuò)容時候使用的，思路是如果是初始化并且
final HashMap.Node<K,V>[] resize() {
HashMap.Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果舊容量已經(jīng)達(dá)到最大值容量锋拖，則直接返回不進(jìn)行擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//擴(kuò)容到舊容量的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//舊容量為0诈悍，但是舊閾值大于0，說明創(chuàng)建的了哈希表兽埃，但是還沒有添加元素
else if (oldThr > 0) // initial capacity was placed in threshold
//容量擴(kuò)容到舊閾值
newCap = oldThr;
//舊容量和閾值都為0侥钳，說明還沒有創(chuàng)建哈希表，則使用默認(rèn)規(guī)則創(chuàng)建哈希表
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新閾值為0柄错，則使用新容量重新計算一次
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//創(chuàng)建當(dāng)前兩倍的哈希表舷夺，然后將元素復(fù)制過去
@SuppressWarnings({"rawtypes","unchecked"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K,V> e;
if ((e = oldTab[j]) != null) {
//將舊桶置為空
oldTab[j] = null;
//如果當(dāng)前桶中沒有元素，則直接賦值給對應(yīng)位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果舊節(jié)點是樹形元素售貌，則在新鏈表數(shù)組中該節(jié)點也是樹形
else if (e instanceof HashMap.TreeNode)
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//否則保留舊哈希表中桶的元素順序
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.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;
}
擴(kuò)容過程中的鍵點：
- 初始化哈希表時给猾，容量為默認(rèn)容量，閾值為 容量* 負(fù)載因子颂跨。
- 已有哈希表擴(kuò)容時敢伸，容量、閾值均翻倍恒削。
- 如果之前節(jié)點類型是樹池颈，需要把新哈希表表里當(dāng)前桶也變成樹形結(jié)構(gòu)。
- 復(fù)制到新哈希表時需要重新索引(rehash)钓丰，這里采用的計算方法為
e.hash() & (newCap - 1);等價于e.hash() % newCap
可以發(fā)現(xiàn)擴(kuò)容開銷確實大躯砰，需要迭代所有元素，rehash携丁、復(fù)制琢歇，還得保留原來的數(shù)據(jù)結(jié)構(gòu)。所以應(yīng)該盡量少擴(kuò)容，最好在初始化的時候指定好HashMap的長度矿微，盡量避免resize()痕慢。
獲取元素時最常用的就是get(Object key)了，我們看下它是如何實現(xiàn)的涌矢。
public V get(Object key) {
HashMap.Node<K,V> e;
//先計算key的hash值掖举，然后通過getNode獲取
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
//如果哈希表為空，則返回null娜庇。tab[n-1 & hash]是獲取哈希表中的數(shù)組位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果拉鏈表中的一個元素和給定的key匹配塔次，則返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//第一個元素不符合，則開始向后遍歷
if ((e = first.next) != null) {
//如果節(jié)點類型為樹類型名秀，則通過getTreeNode獲取節(jié)點值
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//節(jié)點類型為鏈表励负，則開始遍歷鏈表
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
獲取值的關(guān)鍵步驟：
- 先計算哈希值hash。
- 利用(n-1) & hash計算桶的位置匕得。
- 在桶里遍歷鏈表或樹查找元素继榆。
HashMap提供的其它方法實現(xiàn)和上面類似，都是先通過hash值找到哈希表位置汁掠，然后遍歷鏈表進(jìn)行操作略吨，這里就不一一介紹了。下面主要看下JDK1.8新增的紅黑樹考阱。
[圖片上傳失敗...(image-f0783a-1548676054872)]
在JDK8之后如果桶中的鏈表長度大于8之后翠忠，就會將其轉(zhuǎn)換為一棵紅黑樹，目的在于能夠提高查大量哈希沖突后的元素遍歷乞榨。
首先看一下HashMap中的紅黑樹定義：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
...
}
TreeNode中提供了紅黑樹的基本操作左右轉(zhuǎn)：rotateLeft和rotateRight秽之。同時還提供了紅黑樹節(jié)點的添加、刪除吃既、修剪等操作考榨。
JDK8新增的紅黑樹有三個關(guān)鍵參數(shù)變量：
//桶的樹化閾值，當(dāng)桶中元素個數(shù)大于8時态秧，將鏈表轉(zhuǎn)換為RB-tree
static final int TREEIFY_THRESHOLD = 8;
//桶中將樹還原為鏈表的閾值董虱，當(dāng)樹的節(jié)點個數(shù)為6時扼鞋，將其轉(zhuǎn)換為列表
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表最小樹形化容量申鱼，讓hash表中元素大于這個值時才會進(jìn)行樹型化
static final int MIN_TREEIFY_CAPACITY = 64;
關(guān)于HashMap的紅黑樹內(nèi)部具體實現(xiàn)之后再看：TODO
HashMap不是同步的，如果想要同步使用云头，可以加鎖或使用
Collections.synchronizedMap包一層捐友，變成線程安全的Map。
HashMap返回的三個視圖溃槐，都是fail-fast匣砖，所以在遍歷過程中，如果修改了Map內(nèi)容，會拋出ConcurrentModificationException猴鲫。
如果HashMap中大量元素放在一個桶中对人，這時候在遍歷桶中元素時，時間復(fù)雜度就為O(n)拂共，就失去HashMap的優(yōu)勢了牺弄。針對這個問題HashMap在JDK1.8新增了紅黑樹優(yōu)化這個問題。
之所以容量要為2的冪次方宜狐，主要是以下兩個原因：
- 容量為2的整次冪的話势告，h&(length-1)就相當(dāng)于取模運算，使用減法替代取模運算提升效率抚恒。
- 保證了length-1為奇數(shù)咱台，這樣length-1二進(jìn)制最后一位為1，它與hash結(jié)果進(jìn)行&運算可以隨著hash值得到奇數(shù)或偶數(shù)俭驮。如果為偶數(shù)回溺，則與后的值一定為0(因為0與任何值都是0)，這樣所有值都會散列到數(shù)組下標(biāo)偶數(shù)位置混萝。
TreeMap
TreeMap繼承AbstractMap馅而，并且實現(xiàn)了NavigableMap，再看TreeMap前譬圣，我們先看下NavigableMap實現(xiàn)瓮恭。
NavigableMap
NavigableMap接口繼承SortedMap接口。
Map中鍵值對是無序的厘熟，我們在遍歷Map時屯蹦，遍歷鍵的順序是隨機(jī)的。SortedMap接口是Map接口進(jìn)一步擴(kuò)充绳姨，通過對鍵(key)的排序(自然升序或提供比較器)登澜，使得在遍歷Map視圖時能夠根據(jù)指定順序遍歷(entrySet()、keySet()飘庄、values()方法返回的迭代器)脑蠕。
public interface SortedMap<K,V> extends Map<K,V> {
//返回此Map中使用的比較器，如果采用自然順序跪削，則返回null谴仙。
Comparator<? super K> comparator();
//返回此映射的部分視圖，范圍從指定的fromKey(包含)到toKey(不包含)
java.util.SortedMap<K,V> subMap(K fromKey, K toKey);
//返回次映射的部分視圖碾盐，范圍為鍵值小于toKey的所有鍵值對
java.util.SortedMap<K,V> headMap(K toKey);
//返回此映射的部分視圖晃跺，范圍為鍵值大于等于fromKey的所有鍵值對
java.util.SortedMap<K,V> tailMap(K fromKey);
//返回此映射中的第一個鍵
K firstKey();
//返回次映射的最后一個鍵值
K lastKey();
//返回包含所有鍵的集合視圖
Set<K> keySet();
//返回所有值的列表視圖
Collection<V> values();
//返回所有鍵值對實體的集合視圖
Set<Map.Entry<K, V>> entrySet();
}
所有實現(xiàn)可排序的Map的實現(xiàn)類，都應(yīng)該實現(xiàn)四個標(biāo)準(zhǔn)構(gòu)造方法毫玖。
- 無參構(gòu)造函數(shù)掀虎，它將會根據(jù)鍵的自然順序創(chuàng)建一個空的有序映射凌盯。
- 具有單個參數(shù)類型為Comparator的構(gòu)造方法，它會根據(jù)提供的比較器對鍵值對進(jìn)行排序烹玉。
- 具有單個參數(shù)類型為Map的構(gòu)造方法驰怎，它會創(chuàng)建一個與參數(shù)具有相同鍵值對新映射，并且按照自然順序?qū)︽I進(jìn)行排序二打。
- 具有單個參數(shù)類型為SortedMap的構(gòu)造方法砸西，它會創(chuàng)建一個與參數(shù)具有相同鍵值對映射，并且順序和SortedMap的排序一致址儒。
需要注意芹枷，所有鍵都需要實現(xiàn)Comparable接口，或能夠接受comparator比較器莲趣。
NavigableMap擴(kuò)展了Sorted接口鸳慈，提供了要查找的元素最接近匹配相關(guān)方法。
[圖片上傳失敗...(image-316f83-1548676054872)]
NavigalbeMap除了提供SortedMap定義的方法外喧伞，還提供了以下幾類方法：
- lowerEntry走芋、floorEntry、ceilingEntry潘鲫、higherEntry分別返回小于指定key翁逞、小于或等于指定key、大于或等于指定key和大于指定key的鍵值對(只返回最接近的一個鍵值對)溉仑。
同理lowerKey挖函、floorKey、ceilingKey怨喘、higherKey返回對應(yīng)的鍵key。 - 同時還提供了返回最小key必怜、最大key的firstEntry、pollFirstEntry(返回并刪除)抱环、lastEntry壳快、pollLastEntry(返回并刪除)。
- 最后NavigableMap還提供了倒序視圖descendingMap镇草、倒序鍵集合decendingKeySet和返回NavigableSet類型的鍵集合navigableKeySet()眶痰。
TreeMap實現(xiàn)
TreeMap是基于紅黑樹實現(xiàn)的有序鍵值對集合，該映射根據(jù)鍵的自然順序或傳入的比較器進(jìn)行排序梯啤，具體取決于使用的構(gòu)造函數(shù)竖伯。
TreeMap的基本操作containsKey、get因宇、put和remove的時間復(fù)雜度為log(n)七婴。
TreeMap繼承了AbstractMap抽象類，并且實現(xiàn)了NavigableMap察滑、Cloneable打厘、Serializable接口。
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
首先TreeMap的構(gòu)造方法就是包含了第一開始所說的可排序Map四類構(gòu)造函數(shù)贺辰。
//無慘構(gòu)造函數(shù)
public TreeMap() {
comparator = null;
}
//指定比較器的構(gòu)造函數(shù)
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//傳入指定Map户盯，以自然升序構(gòu)造的新TreeMap
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
//傳入排好序的SortedMap
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
//采用有序方式構(gòu)造TreeMap
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
我們看到第三個構(gòu)造函數(shù)最后調(diào)用了putAll方法，我們再看下putAll的具體實現(xiàn)饲化。
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
//如果Map類型為SortedMap類型莽鸭，通過buildFromSorted方法構(gòu)造
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
//如果是無序Map，則使用AbstractMap中定義的putAll方法
super.putAll(map);
}
從上面可以看到如果傳入Map類型如果SortedMap則采用和第四個構(gòu)造函數(shù)一樣的方法構(gòu)建TreeMap：buildFromSorted吃靠。如果為普通Map則使用AbstractMap的putAll硫眨，上面我們看到過AbstractMap的putAll就是挨個調(diào)用子類的put方法實現(xiàn)。
首先我們看下紅黑樹的數(shù)據(jù)結(jié)構(gòu)：
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; //存儲Map的key
V value;//存儲Map的value
Entry<K,V> left; //樹左節(jié)點引用
Entry<K,V> right; //樹右節(jié)點應(yīng)用
Entry<K,V> parent;
boolean color = BLACK; //顏色
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
除了HashMap和TreeMap巢块，我們看下Map中的其它實現(xiàn)：
- Attributes：Attributes實現(xiàn)了Map接口捺球，它將Manifest屬相映射到關(guān)聯(lián)的字符串，底層使用Map實現(xiàn)key-value存儲夕冲。
- HashTable：繼承Dictionary類氮兵，并且實現(xiàn)了Map接口。線程安全的哈希表實現(xiàn)歹鱼，實現(xiàn)方式和HashMap類似采用數(shù)組實現(xiàn)存儲泣栈，采用鏈表解決hash沖突(沒有提供紅黑樹的優(yōu)化)。HashTable通過為每個方法增加synchronized同步鎖的方式弥姻，保證線程安全南片。如果不需要線程安全建議使用HashMap，如果需要線程安全庭敦，并且對高并發(fā)有要求疼进，建議使用ConcurrentHashMap。
- ConcurrentHashMap：功能和HashTable一樣秧廉，但是不是通過鎖來來保證方法訪問的線程安全伞广，所以能夠應(yīng)對高并發(fā)下的使用拣帽。ConcurrentHashMap采用的是鎖分段技術(shù)，將數(shù)據(jù)分成一段段的存儲嚼锄，然后給每一段分配一把鎖减拭，當(dāng)線程占用鎖訪問其中一段數(shù)據(jù)時，其它端還能夠被訪問区丑。
- LinkedHashMap：LinkedHashMap繼承了HashMap和Map接口拧粪，它與HashMap不同的是將所有元素通過一個雙向鏈表連接。這樣就提供了可以按照插入順序遍歷元素的可能沧侥，而不需要使用TreeMap那樣引入額外成本(提供排序順序)可霎。LinkedHashMap提供了一個特殊構(gòu)造函數(shù)，其迭代順序為其元素最后一次訪問的順序宴杀，這個非常適合構(gòu)建LRU緩存癣朗。
- EnumMap：專門用于枚舉類型鍵的Map實現(xiàn)，枚舉映射中的所有鍵必須來創(chuàng)建映射時指定的枚舉類型婴氮。
- IdentityHashMap：不是通用Map的實現(xiàn)斯棒，因為它違反了Map的規(guī)定，它要求在比較對象時使用equals方法主经。此類僅在引用相等語義的情況下使用荣暮。
- Properties：繼承HashTable，Properties類表示一組持久的屬性罩驻，可以將Properties保存到流中穗酥，會從流中加載。Properties中每個鍵和值都是一個字符串惠遏。
- WeakHashMap：WeakHashMap繼承AbstractMap砾跃，并且實現(xiàn)了Map接口。WeakHashMap和HashMap類似节吮，但是WeakHashMap中鍵為弱鍵抽高，意思是當(dāng)鍵不在正常使用時，會被從WeakHashMap中自動移除透绩。比如WeakHashMap中鍵沒有其它對象引用使用時翘骂，就會被GC回收。
- ConcurrentSkipListMap
集合相關(guān)問題
Iterable和Iterator的關(guān)系是什么帚豪？
Iterator是迭代器接口碳竟，而Iterable是使用迭代器需要實現(xiàn)的接口。所以我們?nèi)绻胍褂玫骶托枰獙崿F(xiàn)Iterable接口狸臣，并且實現(xiàn)它的iterator()方法莹桅，來返回一個迭代器。
之所以這樣主要是因為Iterator中的next()烛亦、hasNext()等方法是依賴當(dāng)前位置進(jìn)行的诈泼，如果所有需要使用迭代器的類都直接繼承Iterator接口的話懂拾，都需要為其維護(hù)一套指針，并且當(dāng)同時操作一個類的迭代器時厂汗，就會出現(xiàn)這個指針混亂昭娩。
所以一個明智的方法就是通過Iterable的iterator方法來為每個需要使用迭代器的方法返回一個迭代器扳剿。什么是深拷貝和淺拷貝？
拷貝方法定義在Object中狞悲，Object對clone方法進(jìn)行了默認(rèn)實現(xiàn)汁汗，這個默認(rèn)實現(xiàn)其實就是一種淺拷貝衷畦。它對于拷貝對象中的應(yīng)用類型會將其地址拷貝出來，這樣就會導(dǎo)致兩個對象操作相同的引用變量知牌。
所以如果想要使用深拷貝祈争，需要重新實現(xiàn)clone方法，不僅利用淺拷貝將基礎(chǔ)類型進(jìn)行拷貝角寸，而且還還需將引用類型進(jìn)行深拷貝菩混。
還有一種實現(xiàn)深拷貝的方法就是利用序列化與反序列化，將對象序列化成字節(jié)扁藕，然后反序列化成對象返回沮峡。
