一、概述
- LinkedHashMap是HashMap的子類祖搓，一些基本方法LinkedHashMap都沒有實(shí)現(xiàn)戳葵，所以集合-HashMap解析這篇文章是必讀的。
- 它是HashMap的子類坝茎，所以底層數(shù)據(jù)結(jié)構(gòu)是和HashMap完全相同的，只是新增了一個(gè)雙向鏈表來維護(hù)插入順序暇番，這個(gè)鏈表在增加嗤放、修改、刪除數(shù)據(jù)是會(huì)維護(hù)鏈表的順序壁酬，Android中則是采用的雙向循環(huán)鏈表斤吐，但是不提供雙向循環(huán)的API。
- 它也是線程不安全的厨喂，允許key為null，value為null
- 關(guān)于數(shù)據(jù)遍歷時(shí)順序有兩種方式庄呈，一種是插入順序蜕煌，一種是訪問順序。使用了accessOrder來控制是使用哪種順序诬留。accessOrder默認(rèn)為false來表示插入順序斜纪，如果設(shè)置為true贫母，那么在使用get方法時(shí)，會(huì)修改鏈表中最后訪問元素的順序盒刚。
二腺劣、構(gòu)造函數(shù)和節(jié)點(diǎn)信息
2.1 構(gòu)造函數(shù)
相比于HashMap的構(gòu)造函數(shù)，就多了一個(gè)accessOrder參數(shù)及相關(guān)的構(gòu)造函數(shù)
Java
基本上都是調(diào)用了HashMap的相關(guān)構(gòu)造函數(shù)因块，然后設(shè)置數(shù)據(jù)的最終遍歷順序橘原。
transient LinkedHashMap.Entry<K,V> head;//頭結(jié)點(diǎn)
transient LinkedHashMap.Entry<K,V> tail;//尾節(jié)點(diǎn)
final boolean accessOrder;//數(shù)據(jù)遍歷是順序，是否是訪問順序
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);//調(diào)用父類相關(guān)方法
accessOrder = false;//默認(rèn)是插入順序
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);//參考上篇文章
accessOrder = false;//默認(rèn)是插入順序
}
public LinkedHashMap() {
super();//參考上篇文章
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();//參考上篇文章
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);//參考上篇文章
this.accessOrder = accessOrder;//使用自定義的順序
}
Android
transient LinkedEntry<K, V> header;//節(jié)點(diǎn)信息涡上，類似于在LinkedList中voidLink
private final boolean accessOrder;//數(shù)據(jù)的遍歷順序趾断，默認(rèn)是插入順序
public LinkedHashMap() {
init();
accessOrder = false;//默認(rèn)值
}
public LinkedHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//調(diào)用下一個(gè)構(gòu)造函數(shù)
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, false);//調(diào)用下一個(gè)構(gòu)造函數(shù)
}
public LinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);//調(diào)用父類的構(gòu)造方法
init();//初始化
this.accessOrder = accessOrder;//設(shè)置數(shù)據(jù)遍歷順序
}
public LinkedHashMap(Map<? extends K, ? extends V> map) {
this(capacityForInitSize(map.size()));//調(diào)用第二個(gè)構(gòu)造函數(shù)
constructorPutAll(map);//參考父類具體方法
}
@Override
void init() {
header = new LinkedEntry<K, V>();//初始化header節(jié)點(diǎn)
}
2.2 節(jié)點(diǎn)信息
Java
另有HashMap中TreeNode繼承了該Entry，來保證哈希桶中紅黑樹也能記錄前后位置
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;//前后節(jié)點(diǎn)
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
Android
static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
LinkedEntry<K, V> nxt;//后節(jié)點(diǎn)
LinkedEntry<K, V> prv;//前節(jié)點(diǎn)
/** Create the header entry */
LinkedEntry() {//專用于創(chuàng)建Header使用
super(null, null, 0, null);
nxt = prv = this;
}
/** Create a normal entry *///創(chuàng)建一個(gè)普通的鍵值對(duì)使用
LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
super(key, value, hash, next);
this.nxt = nxt;
this.prv = prv;
}
}
三吩愧、增加條目
Java
在新增一個(gè)節(jié)點(diǎn)芋酌，并將該節(jié)點(diǎn)放置在鏈表的尾部
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//創(chuàng)建一個(gè)新的條目
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);//將新條目鏈接到鏈表的尾部
return p;
}
//創(chuàng)建一個(gè)新的樹節(jié)點(diǎn)，并將樹節(jié)點(diǎn)放在鏈表的末尾雁佳，樹節(jié)點(diǎn)是節(jié)點(diǎn)子類
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)//表示鏈表為空
head = p;
else {//不為空脐帝，將p的前節(jié)點(diǎn)設(shè)為原尾節(jié)點(diǎn)，將原尾節(jié)點(diǎn)后節(jié)點(diǎn)設(shè)為p
p.before = last;
last.after = p;
}
}
//插入后修改
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//evict大多數(shù)情況都是true糖权，默認(rèn)put方法也是使用的true
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//移除最老的方法堵腹，這個(gè)方法默認(rèn)返回false，但是可以被覆蓋
//如果覆蓋可以設(shè)置在身份情況下刪除最老的節(jié)點(diǎn)信息
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
Android
//添加節(jié)點(diǎn)
@Override
void addNewEntry(K key, V value, int hash, int index) {
LinkedEntry<K, V> header = this.header;//void頭結(jié)點(diǎn)
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;//最老節(jié)點(diǎn)
//removeEldestEntry温兼，是否需要一次最老的節(jié)點(diǎn)
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;//老的尾部
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);//新的尾部節(jié)點(diǎn)
//在HashMap哈希桶中鏈表頭部添加數(shù)據(jù)
//在LinkedHashMap中鏈表尾部添加新的尾部
//將void的前節(jié)點(diǎn)設(shè)置為新的尾節(jié)點(diǎn)
table[index] = oldTail.nxt = header.prv = newTail;
}
//添加空節(jié)點(diǎn)
@Override
void addNewEntryForNullKey(V value) {
LinkedEntry<K, V> header = this.header;//頭結(jié)點(diǎn)
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;//最老的節(jié)點(diǎn)
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
null, value, 0, null, header, oldTail);
//空節(jié)點(diǎn)秸滴，指向了新創(chuàng)建的尾節(jié)點(diǎn)
entryForNullKey = oldTail.nxt = header.prv = newTail;
}
四、刪除條目
在節(jié)點(diǎn)(條目)刪除后募判，修復(fù)鏈表的相關(guān)關(guān)系
Java
void afterNodeRemoval(Node<K,V> e) { // unlink
//獲取刪除的節(jié)點(diǎn)荡含、獲取刪除節(jié)點(diǎn)前節(jié)點(diǎn)、獲取刪除節(jié)點(diǎn)的后節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;//將p與鏈表的前后管理關(guān)系移除
if (b == null)//如果前節(jié)點(diǎn)為空届垫，表示刪除節(jié)點(diǎn)是頭結(jié)點(diǎn)
head = a;//將頭結(jié)點(diǎn)指向刪除節(jié)點(diǎn)的后節(jié)點(diǎn)
else//如果前節(jié)點(diǎn)不為空释液，將前節(jié)點(diǎn)后節(jié)點(diǎn)指向刪除節(jié)點(diǎn)的后節(jié)點(diǎn)
b.after = a;
if (a == null)//如果后節(jié)點(diǎn)為空，表示刪除的節(jié)點(diǎn)是尾節(jié)點(diǎn)
tail = b;//將尾節(jié)點(diǎn)指向刪除節(jié)點(diǎn)的前節(jié)點(diǎn)
else//如果后節(jié)點(diǎn)不為空装处，將后節(jié)點(diǎn)的前節(jié)點(diǎn)置為刪除節(jié)點(diǎn)的前節(jié)點(diǎn)
a.before = b;
}
Android
@Override
void postRemove(HashMapEntry<K, V> e) {
LinkedEntry<K, V> le = (LinkedEntry<K, V>) e;
//不存在le.prv和le.nxt為空的情況误债，因?yàn)橛衕eader。
le.prv.nxt = le.nxt;//修復(fù)鏈接關(guān)系
le.nxt.prv = le.prv;//修復(fù)鏈接關(guān)系
le.nxt = le.prv = null; // Help the GC (for performance)
}
五妄迁、修改條目
Java
替換條目后寝蹈，會(huì)調(diào)用afterNodeAccess這個(gè)訪問后修改方法，因?yàn)樾薷囊菜闶窃L問的一種
重寫了父類的replaceAll方法登淘，因?yàn)槭褂面湵砣闅v比HashTable遍歷效果更好
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
if (function == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
e.value = function.apply(e.key, e.value);
if (modCount != mc)
throw new ConcurrentModificationException();
}
Android
雖然沒有Replace相關(guān)的API箫老，但是有預(yù)修改
這個(gè)API也是判斷是否是訪問順序
@Override
void preModify(HashMapEntry<K, V> e) {
if (accessOrder) {
makeTail((LinkedEntry<K, V>) e);
}
}
六、查詢條目
Java
查詢后黔州，判斷遍歷順序耍鬓，然后決定是否移動(dòng)最新訪問的節(jié)點(diǎn)到尾部
public V get(Object key) {//獲取節(jié)點(diǎn)阔籽，根據(jù)遍歷順序然后決定是否移動(dòng)鏈表節(jié)點(diǎn)
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
//獲取帶有默認(rèn)值的節(jié)點(diǎn)
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
//節(jié)點(diǎn)訪問后
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;//最后的節(jié)點(diǎn)
//將last設(shè)置為尾節(jié)點(diǎn)
if (accessOrder && (last = tail) != e) {//如果遍歷順序是訪問順序
//獲取最后訪問的節(jié)點(diǎn)，獲取訪問節(jié)點(diǎn)的前節(jié)點(diǎn)牲蜀，獲取訪問節(jié)點(diǎn)的后節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;//將訪問節(jié)點(diǎn)后節(jié)點(diǎn)置空
if (b == null)//如果前節(jié)點(diǎn)為空笆制，表示最后訪問的節(jié)點(diǎn)是首節(jié)點(diǎn)
head = a;//將首節(jié)點(diǎn)置為后節(jié)點(diǎn)
else//不是首節(jié)點(diǎn)，將前節(jié)點(diǎn)的后節(jié)點(diǎn)置為訪問節(jié)點(diǎn)的首節(jié)點(diǎn)
b.after = a;
if (a != null)//如果后節(jié)點(diǎn)不為空
a.before = b;//將后節(jié)點(diǎn)的前節(jié)點(diǎn)置為訪問節(jié)點(diǎn)的前節(jié)點(diǎn)
else//將最后訪問節(jié)點(diǎn)設(shè)為剛才訪問的節(jié)點(diǎn)
last = b;
if (last == null)//如果last==null涣达，表示尾節(jié)點(diǎn)為空或者剛訪問的節(jié)點(diǎn)為空在辆，此時(shí)將頭結(jié)點(diǎn)指向p即可，這種情況一般不會(huì)發(fā)生峭判，因?yàn)榭真湵聿艜?huì)出這種情況开缎，為了保證不出異常，才如此做林螃。
head = p;
else {//將p放置到最后訪問的尾部
p.before = last;
last.after = p;
}
tail = p;//將尾部設(shè)為p
++modCount;//增加修改次數(shù)
}
}
Android
重寫了get方法奕删，加入了遍歷順序是訪問順序情況下，修改鏈表的情況
@Override
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null)
return null;
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
return null;
}
private void makeTail(LinkedEntry<K, V> e) {
// Unlink e疗认，將e從鏈表中移除
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// Relink e as tail完残，將e鏈接到鏈表中
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
}
七、包含元素
因?yàn)閏ontainsValue有可能需要遍歷整個(gè)哈希桶横漏，所以使用鏈表遍歷更方便谨设、快捷、高效
Java
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
Android
@Override
public boolean containsValue(Object value) {
if (value == null) {
for (LinkedEntry<K, V> header = this.header, e = header.nxt;
e != header; e = e.nxt) {
if (e.value == null) {
return true;
}
}
return false;
}
// value is non-null
for (LinkedEntry<K, V> header = this.header, e = header.nxt;
e != header; e = e.nxt) {
if (value.equals(e.value)) {
return true;
}
}
return false;
}
八缎浇、遍歷
關(guān)于Map的遍歷都是使用相應(yīng)的迭代器進(jìn)行相應(yīng)的遍歷
迭代器優(yōu)化過扎拣，不在使用哈希桶的迭代器，因?yàn)楣Ｍ暗牡绞教珡?fù)雜了素跺。
而采用鏈表的迭代器方法二蓝，更加的高效
在Java中通過重寫entrySet()等相關(guān)方法來實(shí)現(xiàn)新的迭代器
在Android中則是通過直接重寫構(gòu)造迭代器的方法實(shí)現(xiàn)迭代器的重構(gòu)，但是原理相似
8.1 鍵值對(duì)迭代器
Java
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
//返回相應(yīng)的集合
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
//鍵值的集合
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }//返回Map的Size
public final void clear() { LinkedHashMap.this.clear(); }//清空
public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();//返回鏈表鍵值對(duì)迭代器
}
public final boolean contains(Object o) {//是否包含值
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {//移除值
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
//分割迭代器
public final Spliterator<Map.Entry<K,V>> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED |
Spliterator.DISTINCT);
}
//lambda循環(huán)使用
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
Android
@Override
Iterator<Map.Entry<K, V>> newEntryIterator() {
return new EntryIterator();
}
private final class EntryIterator
extends LinkedHashIterator<Map.Entry<K, V>> {
public final Map.Entry<K, V> next() { return nextEntry(); }
}
8.2 Key迭代器
和鍵值對(duì)迭代器相似
Java
public Set<K> keySet() {
Set<K> ks;
return (ks = keySet) == null ? (keySet = new LinkedKeySet()) : ks;
}
final class LinkedKeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
public final Iterator<K> iterator() {
return new LinkedKeyIterator();
}
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED |
Spliterator.DISTINCT);
}
public final void forEach(Consumer<? super K> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e.key);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
Android
private final class KeyIterator extends LinkedHashIterator<K> {
public final K next() { return nextEntry().key; }
}
@Override Iterator<K> newKeyIterator() {
return new KeyIterator();
}
8.3 值迭代器
Java
public Collection<V> values() {
Collection<V> vs;
return (vs = values) == null ? (values = new LinkedValues()) : vs;
}
final class LinkedValues extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
public final Iterator<V> iterator() {
return new LinkedValueIterator();
}
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator<V> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED);
}
public final void forEach(Consumer<? super V> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e.value);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
Android
private final class ValueIterator extends LinkedHashIterator<V> {
public final V next() { return nextEntry().value; }
}
@Override Iterator<V> newValueIterator() {
return new ValueIterator();
}
8.4 公共方法
采用鏈表的方式來迭代器數(shù)據(jù)指厌，相比迭代哈希桶刊愚，這樣更加高效
Java
//抽象的hash迭代器，返回的LinkedHashMap的鍵值對(duì)對(duì)象
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
//是否有下一個(gè)節(jié)點(diǎn)
public final boolean hasNext() {
return next != null;
}
//下一個(gè)節(jié)點(diǎn)
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
// 移除最后訪問的節(jié)點(diǎn)
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
Android
鏈表的迭代器
private abstract class LinkedHashIterator<T> implements Iterator<T> {
LinkedEntry<K, V> next = header.nxt;
LinkedEntry<K, V> lastReturned = null;
int expectedModCount = modCount;
public final boolean hasNext() {
return next != header;
}
final LinkedEntry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedEntry<K, V> e = next;
if (e == header)
throw new NoSuchElementException();
next = e.nxt;
return lastReturned = e;
}
public final void remove() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (lastReturned == null)
throw new IllegalStateException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
}
九踩验、總結(jié)
- 相比于HashMap增加了鏈表來存儲(chǔ)數(shù)據(jù)的順序鸥诽，這個(gè)順序用于遍歷
- 數(shù)據(jù)的順序有兩種：插入順序和訪問順序
- 相對(duì)來說優(yōu)化了遍歷功能，畢竟鏈表的迭代效率高于哈希桶的箕憾。
- 關(guān)于鏈表的維護(hù)牡借，則是在每次插入數(shù)據(jù)、刪除數(shù)據(jù)袭异、修改數(shù)據(jù)和查詢數(shù)據(jù)后判斷是否進(jìn)行數(shù)據(jù)的修改钠龙。如果數(shù)據(jù)需要移動(dòng)(插入、修改、查詢)一般移動(dòng)(插入俊鱼、修改、查詢)到末尾畅买。
- 關(guān)于contains相關(guān)的方法并闲，只重寫了containsValue方法，因?yàn)檫@個(gè)方法在HashMap中需要遍歷整個(gè)哈希桶谷羞，遍歷的效率比較低帝火。containsKey方法則是使用哈希值進(jìn)行定位的，查找起來如果hash值的算法比較高效的話湃缎，查找效率是優(yōu)于整個(gè)hash表的遍歷的犀填。
其他文章
容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析
