從源碼分析面試中經(jīng)常出現(xiàn)的集合類問題
點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”
優(yōu)質(zhì)文章，第一時(shí)間送達(dá)
76套java從入門到精通實(shí)戰(zhàn)課程分享
Collection接口
/* @author Josh Bloch
* @author Neal Gafter
* @see Set
* @see List
* @see Map
* @see SortedSet
* @see SortedMap
* @see HashSet
* @see TreeSet
* @see ArrayList
* @see LinkedList
* @see Vector
* @see Collections
* @see Arrays
* @see AbstractCollection
* @since 1.2
集合層次結(jié)構(gòu)中的根接口。集合表示一組對(duì)象，稱為其元素。
一些集合允許重復(fù)的元素，而另一些則不允許。有些是有序的，而另一些則是無序的。
JDK不提供此接口的任何直接實(shí)現(xiàn)：它提供了更多特定子接口的實(shí)現(xiàn)
*/
public interface Collection<E> extends Iterable<E> {
// Query Operations
/**
返回此集合中的元素?cái)?shù)
*/
int size();
/**
如果此集合不包含任何元素，則返回<tt> true </ tt>
*/
boolean isEmpty();
...........
.........
Collection接口是集合類的根接口，繼承了Iterable接口，Java中沒有直接提供Collection接口的實(shí)現(xiàn)類。但是卻產(chǎn)生了兩個(gè)接口，就是Set和List。Set中不能包含重復(fù)的元素。List是一個(gè)有序的集合，可以包含重復(fù)的元素，提供了按索引訪問的方式。
List接口
1、List（有序、可重復(fù)）
List里存放的對(duì)象是有序的，同時(shí)也是可以重復(fù)的，List關(guān)注的是索引，擁有一系列和索引相關(guān)的方法，查詢速度快。因?yàn)橥鵯ist集合里插入或刪除數(shù)據(jù)時(shí)，會(huì)伴隨著后面數(shù)據(jù)的移動(dòng)，所有插入刪除數(shù)據(jù)速度慢。
2、Set（無序、不能重復(fù)）
Set里存放的對(duì)象是無序，不能重復(fù)的，集合中的對(duì)象不按特定的方式排序，只是簡單地把對(duì)象加入集合中。
/* @see Collection
* @see List
* @see SortedSet
* @see HashSet
* @see TreeSet
* @see AbstractSet
* @see Collections#singleton(java.lang.Object)
* @see Collections#EMPTY_SET
* @since 1.2
不包含重復(fù)元素的集合
*/
public interface Set<E> extends Collection<E> {
// Query Operations
/**
返回此集合中的元素?cái)?shù)（其基數(shù)）
*/
int size();
/**
如果此集合不包含任何元素，則返回<tt> true </ tt>
*/
boolean isEmpty();
/**
如果此集合包含指定的元素，則返回<tt> true </ tt>
*/
boolean contains(Object o);
/**
返回此集合中元素的迭代器。 *元素以不特定的順序返回（除非此集合是提供保證的某些*類的實(shí)例）。
*/
Iterator<E> iterator();
...........
.........
ArrayList(動(dòng)態(tài)數(shù)組)
List接口的可調(diào)整大小的數(shù)組實(shí)現(xiàn)。實(shí)現(xiàn)所有可選的列表操作(實(shí)現(xiàn)了List的全部方法)，并允許所有元素，包括null；
/* @see Collection
* @see List
* @see LinkedList
* @see Vector
* @since 1.2
List接口的可調(diào)整大小的數(shù)組實(shí)現(xiàn)。實(shí)現(xiàn)所有可選的列表操作，并允許所有元素，包括null。除了實(shí)現(xiàn) List接口之外，此類還提供了一些方法來操縱內(nèi)部用于存儲(chǔ)列表的數(shù)組的大小
*/
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
默認(rèn)初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
用于空實(shí)例的共享空數(shù)組實(shí)例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
共享的空數(shù)組實(shí)例，用于默認(rèn)大小的空實(shí)例。我們將其與EMPTY_ELEMENTDATA區(qū)別開來，以了解添加第一個(gè)元素時(shí)需要充氣多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
用于存儲(chǔ)ArrayList元素的數(shù)組緩沖區(qū)。ArrayList的容量是此數(shù)組緩沖區(qū)的長度。添加第一個(gè)元素時(shí)，任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都將擴(kuò)展為DEFAULT_CAPACITY,
該elementData是真正存放元素的容器，可見ArrayList是基于數(shù)組實(shí)現(xiàn)的;
*/
transient Object[] elementData; //非私有，以簡化嵌套類的訪問
ArrayList提供了三個(gè)構(gòu)造方法
/** *構(gòu)造一個(gè)具有指定初始容量的空列表。 @param initialCapacity列表的初始容量@如果指定的初始容量為負(fù)，則拋出IllegalArgumentException */
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/** *構(gòu)造一個(gè)初始容量為10的空列表。 */
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**構(gòu)造一個(gè)包含指定集合的元素的列表，其順序由集合的迭代器返回。 @param c 要將其元素放入此列表的集合如果指定的集合為null，則拋出NullPointerException */
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList擴(kuò)容和add,set等方法
可見當(dāng)初始化的list是一個(gè)空ArrayList的時(shí)候，會(huì)直接擴(kuò)容到DEFAULT_CAPACITY，該值大小是一個(gè)默認(rèn)值10。而當(dāng)添加進(jìn)ArrayList中的元素超過了數(shù)組能存放的最大值就會(huì)進(jìn)行擴(kuò)容。
/** ArrayList擴(kuò)容
默認(rèn)初始容量 DEFAULT_CAPACITY = 10
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
get,add,set等方法
/** *返回此列表中指定位置的元素。@要返回的元素的索引索引 @返回此列表中指定位置的元素、@throws IndexOutOfBoundsException {@inheritDoc} */
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
用指定的元素替換此列表中指定位置的元素。@param要替換元素的索引index @param要存儲(chǔ)在指定位置的元素 @返回先前在指定位置的元素 @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
/**
將指定的元素追加到此列表的末尾。@要附加到此列表的參數(shù)元素 @返回 true （由{@link Collection＃add}指定）
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
LinkedList(雙向鏈表)
LinkedList是一種鏈表結(jié)構(gòu)，從UML圖可以看到，LinkList接口實(shí)現(xiàn)了Queue接口和List接口
進(jìn)LinkList源碼看看
List和Deque接口的雙鏈列表實(shí)現(xiàn)。實(shí)現(xiàn)所有可選的列表操作(實(shí)現(xiàn)了List的全部方法)，并允許所有元素（包括null）
LinkedList由一個(gè)頭節(jié)點(diǎn)和一個(gè)尾節(jié)點(diǎn)組成，分別指向鏈表的頭部和尾部。
/** {@code List}和{@code Deque}接口的雙鏈列表實(shí)現(xiàn)。實(shí)現(xiàn)所有可選的列表操作，
并允許所有元素（包括{@code null}）。
所有操作均按雙鏈接列表的預(yù)期執(zhí)行。索引到列表中的操作將從開頭或結(jié)尾遍歷列表，
以更接近指定索引的位置為準(zhǔn)。
*/
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
指向第一個(gè)節(jié)點(diǎn)的指針
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
指向最后一個(gè)節(jié)點(diǎn)的指針
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
/**
構(gòu)造一個(gè)空List
*/
public LinkedList() {
}
/**
構(gòu)造一個(gè)包含指定集合的元素的List，其順序由集合的迭代器返回。
@param c 要將其元素放入此List的集合
如果指定的集合為null，則拋出NullPointerException
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/** Node節(jié)點(diǎn)*/
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
數(shù)據(jù)結(jié)構(gòu)中鏈表的頭插法linkFirst和尾插法linkLast
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
LinkList的查詢方法
/**
返回此列表中指定位置的元素,要遍歷，找到節(jié)點(diǎn)才能拿到元素
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**返回指定元素索引處的（非空）節(jié)點(diǎn) */
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
注意！ArrayList隨機(jī)訪問比LinkedList快的原因，LinkedList要遍歷找到該位置才能進(jìn)行修改，而ArrayList是內(nèi)部數(shù)組操作會(huì)更快
（1）ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)。
（2）對(duì)于隨機(jī)訪問get和set，ArrayList覺得優(yōu)于LinkedList，因?yàn)長inkedList要遍歷找節(jié)點(diǎn)。
（3）對(duì)于新增和刪除操作add和remove，LinedList比較占優(yōu)勢，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)。這一點(diǎn)要看實(shí)際情況的。若只對(duì)單條數(shù)據(jù)插入或刪除，ArrayList的速度反而優(yōu)于LinkedList。但若是批量隨機(jī)的插入刪除數(shù)據(jù)，LinkedList的速度大大優(yōu)于ArrayList. 因?yàn)锳rrayList每插入一條數(shù)據(jù)，要移動(dòng)插入點(diǎn)及之后的所有數(shù)據(jù)。
Vector
Vector類實(shí)現(xiàn)了對(duì)象的可增長數(shù)組。像數(shù)組一樣，初始數(shù)組大小為10和ArrayList相同，它包含可以使用整數(shù)索引訪問的組件。但是Vector的大小可以根據(jù)需要增大或縮小，以適應(yīng)創(chuàng)建Vector之后的添加和刪除項(xiàng);
與新的集合實(shí)現(xiàn)不同，Vector是同步的,線程安全的。如果不需要線程安全實(shí)現(xiàn)，建議使用 ArrayList代替 Vector,ArrayList是線程不安全的
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
向量分量存儲(chǔ)在其中的數(shù)組緩沖區(qū)。
向量的容量是此數(shù)組緩沖區(qū)的長度，
并且至少足夠大以包含所有向量的元素。
Vector中最后一個(gè)元素之后的所有數(shù)組元素均為null
*/
protected Object[] elementData;
/**
此Vector對(duì)象中有效組件的數(shù)量
* @serial
*/
protected int elementCount;
/**
向量的容量在其大小大于其容量時(shí)自動(dòng)增加的量。如果容量增量小于或等于零，
則向量的容量每次需要增長時(shí)都會(huì)加倍。
* @serial
*/
protected int capacityIncrement;
/** 使用JDK 1.0.2中的serialVersionUID來實(shí)現(xiàn)互操作性 */
private static final long serialVersionUID = -2767605614048989439L;
/**
使用指定的初始容量和容量增量構(gòu)造一個(gè)空向量。 @param initialCapacity向量的初始容量
@param Capacity增大向量溢出時(shí)容量增加的數(shù)量
如果指定的初始容量為負(fù)，則拋出IllegalArgumentException
*/
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
/**
構(gòu)造一個(gè)具有指定初始容量和*容量增量等于零的空向量。
@param initialCapacity向量的初始容量
@如果指定的initialCapacity為負(fù)，則拋出IllegalArgumentException
*/
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
/**
構(gòu)造一個(gè)空向量，以便其內(nèi)部數(shù)據(jù)數(shù)組的大小為 10，并且其標(biāo)準(zhǔn)容量增量為零
*/
public Vector() {
this(10);
}
/**
構(gòu)造一個(gè)向量，該向量包含指定集合的元素，
并按集合的迭代器返回它們的順序。
@param c 將元素放置在此向量中的集合
如果指定的集合為null，則拋出NullPointerException
*/
public Vector(Collection<? extends E> c) {
elementData = c.toArray();
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
為什么Vector是線程安全的？
vector是線程同步的，所以它也是線程安全的，而arraylist是線程異步的，是不安全的。如果不考慮到線程的安全因素，一般用arraylist效率比較高
使用synchronized給方法加鎖，達(dá)到線程安全的目的；
..........
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
............
ArrayList是非線程安全的，Vector是線程安全的；
HashMap是非線程安全的，HashTable是線程安全的；
StringBuilder是非線程安全的，StringBuffer是線程安全的。
Vector和ArrayList擴(kuò)容數(shù)組的區(qū)別
ArrayList擴(kuò)容數(shù)組1.5倍，擴(kuò)容50%；
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Vector擴(kuò)容數(shù)組2倍，擴(kuò)容100%；
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Set接口
Set里存放的對(duì)象是無序，不能重復(fù)的，集合中的對(duì)象不按特定的方式排序，只是簡單地把對(duì)象加入集合中。
不包含重復(fù)元素的集合
HashSet(無序)
此類實(shí)現(xiàn)由散列表（實(shí)際上是 HashMap 實(shí)例）支持的Set接口。它不保證集合的迭代順序。特別是，它不能保證順序會(huì)隨時(shí)間保持不變。此類允許null 元素
如果多個(gè)線程同時(shí)訪問哈希集，并且線程中的至少一個(gè)修改了哈希集，則它必須 </ i> >從外部進(jìn)行同步。這通常是通過對(duì)自然封裝了該集合的某個(gè)對(duì)象進(jìn)行同步來完成的。如果不存在這樣的對(duì)象，則應(yīng)使用Collections synchronized Set Collections.synchronizedSet} 方法來“包裝”該集合。最好在創(chuàng)建時(shí)完成此操作，以防止意外異步訪問集合;(說明Hashset線程不安全)
HashSet集合底層就是
HashMap(hashmap無序所以hashset也無序)，基于二叉樹的treemap,treeset有序
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
構(gòu)造一個(gè)新的空集
支持的HashMap實(shí)例具有默認(rèn)初始容量（16）和負(fù)載因子（0.75）
*/
public HashSet() {
map = new HashMap<>();
}
/**
構(gòu)造一個(gè)新集合，其中包含指定集合中的元素。
HashMap是使用默認(rèn)負(fù)載因子（0.75）和足以容納指定集合中的元素的初始容量創(chuàng)建的。
@param c 要將其元素放入此集合的集合
如果指定的集合為null，則拋出NullPointerException
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
/**
構(gòu)造一個(gè)新的空鏈接哈希集（此包private構(gòu)造函數(shù)僅由LinkedHashSet使用）
支持 HashMap實(shí)例是具有指定的初始容量和指定的負(fù)載因子的LinkedHashMap。
@param initialCapacity 哈希圖的初始容量
@param loadFactor 哈希圖的負(fù)載因子
@param dummy（將此構(gòu)造函數(shù)與其他int，float構(gòu)造函數(shù)區(qū)分開。
@throws IllegalArgumentException如果初始容量為小于零，或者負(fù)載因子為非正
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
HashSet怎么保證元素不重復(fù)？
public boolean add(E e) {
return map.put(e, PRESENT)==null; //map元素是不重復(fù)的 后面見到HashMap
}
HashSet是如何保證元素的唯一性？
//如果此集合已經(jīng)包含元素，則調(diào)用將使該集合保持不變
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
------------------------------------------------------
public V put(K key, V value) { // HashMap中的put方法
return putVal(hash(key), key, value, false, true);
}
/** 首先會(huì)使用 hash() 函數(shù)生成一個(gè) int 類型的 hashCode 散列值，然后與已經(jīng)存儲(chǔ)的元素的 hashCode 值作比較，如果 hashCode 值不相等，則所存儲(chǔ)的兩個(gè)對(duì)象一定不相等，此時(shí)把這個(gè)新元素存儲(chǔ)在它的 hashCode 位置上；如果 hashCode 相等*/
TreeSet(有序)
基于TreeMap的NavigableSet實(shí)現(xiàn)。元素使用其{@link Comparable 自然排序}進(jìn)行排序，或通過在集合創(chuàng)建時(shí)提供的{@link Comparator}進(jìn)行排序，具體取決于所使用的構(gòu)造函數(shù)。此實(shí)現(xiàn)為基本操作（{@code add}，{@ code remove}和{@code contains}）提供了保證的log（n）時(shí)間成本。請(qǐng)注意，如果要正確實(shí)現(xiàn){@code Set}接口，則集合（無論是否提供了顯式比較器）所維護(hù)的順序必須與equals 一致。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
/**
構(gòu)造一個(gè)新的空樹集，并根據(jù)其元素的自然順序進(jìn)行排序。
插入到集合中的所有元素都必須實(shí)現(xiàn){@link Comparable}接口
*/
public TreeSet() {
this(new TreeMap<E,Object>());
}
/**
構(gòu)造一個(gè)新的空樹集，并根據(jù)指定的比較器進(jìn)行排序。
插入到集合中的所有元素都必須由指定的比較器進(jìn)行相互比較：
{@code比較器.compare（e1，* e2）}
*/
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
/**
*構(gòu)造一個(gè)新的樹集，其中包含指定集合中的元素，并根據(jù)其元素的自然順序進(jìn)行排序。
插入集合中的所有元素都必須實(shí)現(xiàn){@link Comparable}接口。
此外，所有此類元素必須可相互比較：
@param c集合，其元素將組成新集合
*/
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
Map接口
將鍵(key)映射到值(value)的對(duì)象。映射不能包含重復(fù)的鍵；每個(gè)鍵最多可以映射到一個(gè)值
public interface Map<K,V> {
// Query Operations
/**
返回此映射中的鍵值映射數(shù)
*/
int size();
/**
如果此映射不包含鍵值映射，則返回true
*/
boolean isEmpty();
/**
如果此映射包含指定*鍵的映射，則返回true
*/
boolean containsKey(Object key);
/**
如果此映射將一個(gè)或多個(gè)鍵映射到指定值，則返回 true
*/
boolean containsValue(Object value);
/**
返回指定鍵所映射到的值
如果此映射不包含該鍵的映射，則返回 null
*/
V get(Object key);
// Modification Operations
/**
將指定值與此映射中的指定鍵關(guān)聯(lián)（可選操作）
如果該映射先前包含鍵的映射，則舊值將替換為指定值
*/
V put(K key, V value);
/**
從該映射中刪除鍵的映射（如果存在）
*/
V remove(Object key);
HashMap（鏈表加數(shù)組）
HashMap是 Map 接口的基于哈希表的實(shí)現(xiàn)。HashMap提供了所有可選的映射操作，并允許 null 值和null 鍵。HashMap類與 Hashtable大致等效，除了HashMap不同步并且允許空值。）此類不保證map的順序；特別是，它不能保證順序會(huì)隨著時(shí)間的推移保持恒定；
HashMap是線程不安全的，HashTable是線程安全的
HashMap的常量組成
//是hashMap的最小容量16，容量就是數(shù)組的大小也就是變量，
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大數(shù)量，該數(shù)組最大值為2^31一次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)的加載因子，如果構(gòu)造的時(shí)候不傳則為0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//一個(gè)位置里存放的節(jié)點(diǎn)轉(zhuǎn)化成樹的閾值，也就是8，比如數(shù)組里有一個(gè)node，這個(gè)
// node鏈表的長度達(dá)到該值才會(huì)轉(zhuǎn)化為紅黑樹。
static final int TREEIFY_THRESHOLD = 8;
//當(dāng)一個(gè)反樹化的閾值，當(dāng)這個(gè)node長度減少到該值就會(huì)從樹轉(zhuǎn)化成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//滿足節(jié)點(diǎn)變成樹的另一個(gè)條件，就是存放node的數(shù)組長度要達(dá)到64
static final int MIN_TREEIFY_CAPACITY = 64;
//具體存放數(shù)據(jù)的數(shù)組
transient Node<K,V>[] table;
//entrySet，一個(gè)存放k-v緩沖區(qū)
transient Set<Map.Entry<K,V>> entrySet;
//size是指hashMap中存放了多少個(gè)鍵值對(duì)
transient int size;
//對(duì)map的修改次數(shù)
transient int modCount;
//加載因子
final float loadFactor;
HashMap的構(gòu)造方法
//只有容量，initialCapacity
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) // 容量不能為負(fù)數(shù)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//當(dāng)容量大于2^31就取最大值1<<31;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//當(dāng)前數(shù)組table的大小，一定是是2的冪次方
// tableSizeFor保證了數(shù)組一定是是2的冪次方，是大于initialCapacity最結(jié)進(jìn)的值。
this.threshold = tableSizeFor(initialCapacity);
}
HashMap的哈希沖突解決方法-鏈?zhǔn)降刂贩?/span>
如何HashMap和HashTable存放數(shù)據(jù)的不同(哈希值的來源)？
HashMap的hash值：通過key的來計(jì)算得到的hash值，每一個(gè)hash值對(duì)應(yīng)一個(gè)數(shù)組下標(biāo)，由于不同的key值可能具有相同的hash值，即一個(gè)數(shù)組的某個(gè)位置出現(xiàn)兩個(gè)相同的元素，對(duì)于這種情況，Hashmap采用鏈表的形式進(jìn)行存儲(chǔ)。（使用鏈表進(jìn)行鏈接）；
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
--------------------------------------------
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashTable的hash值：直接通過Key拿到hash值
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
HashMap采用Entry數(shù)組來存儲(chǔ)key-value對(duì)，每一個(gè)鍵值對(duì)組成了一個(gè)Entry實(shí)體，Entry類實(shí)際上是一個(gè)單向的鏈表結(jié)構(gòu)，它具有Next指針，可以連接下一個(gè)Entry實(shí)體。HashMap底層是以數(shù)組方式進(jìn)行存儲(chǔ)的。將key-value鍵值對(duì)作為數(shù)組的一個(gè)元素進(jìn)行存儲(chǔ)
只是在JDK1.8中，鏈表長度大于8的時(shí)候，鏈表會(huì)轉(zhuǎn)成紅黑樹。
HashTable（鏈表加數(shù)組）
HashMap和Hashtable都實(shí)現(xiàn)了Map接口，并且都是key-value的數(shù)據(jù)結(jié)構(gòu)。它們的不同點(diǎn)主要在三個(gè)方面：
（1）Hashtable是Java1.1的一個(gè)類，它基于陳舊的Dictionary類。而HashMap是Java1.2引進(jìn)的Map接口的一個(gè)實(shí)現(xiàn)。
（2）Hashtable是線程安全的，也就是說是線程同步的，而HashMap是線程不安全的。也就是說在單線程環(huán)境下應(yīng)該用HashMap，這樣效率更高。
（3）HashMap允許將null值作為key或value，但Hashtable不允許（會(huì)拋出NullPointerException）。
（4）哈希值的使用不同：HashTable直接使用對(duì)象的hashCode，HashMap重新計(jì)算hash值，而且用與代替求模；
（5）HashTable中hash數(shù)組默認(rèn)大小是11，增加的方式是 old*2+1。
HashMap中hash數(shù)組的默認(rèn)大小是16，而且一定是2的指數(shù)。
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
/**
哈希表數(shù)據(jù)
*/
private transient Entry<?,?>[] table;
/**
哈希表中的條目總數(shù)
*/
private transient int count;
/**
當(dāng)表的大小超過此閾值時(shí)，表將被重新映射。
（此字段的值為（int）（capacity loadFactor）。
*/
private int threshold;
/**
哈希表的加載因子
*/
private float loadFactor;
/**
此哈希表經(jīng)過結(jié)構(gòu)修改的次數(shù)
*/
private transient int modCount = 0;
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1421746759512286392L;
/**
*使用指定的初始容量和指定的負(fù)載因子構(gòu)造一個(gè)新的空哈希表
*/
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
/**
使用指定的初始容量和默認(rèn)的加載因子（0.75）構(gòu)造一個(gè)新的空哈希表
*/
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
/**
構(gòu)造一個(gè)新的空哈希表，其默認(rèn)初始容量（11）*和負(fù)載因子（0.75）
*/
public Hashtable() {
this(11, 0.75f);
}
/**
*構(gòu)造一個(gè)新的哈希表，該哈希表具有與給定 Map相同的映射。
創(chuàng)建哈希表時(shí)，其初始容量應(yīng)足以將給定Map中的映射保存并具有默認(rèn)的加載因子（0.75）
*/
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
為什么HashTable線程安全？
方法使用 synchronized獲取鎖，實(shí)現(xiàn)線程安全
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
ConcurrentHashMap
哈希表支持檢索的完全并發(fā)和更新的高期望并發(fā)。此類遵循與{@link java.util.Hashtable}相同的功能規(guī)范，并且包含與{{code Hashtable}的每個(gè)方法相對(duì)應(yīng)的方法的版本。但是，即使所有操作都是線程安全的，但檢索操作 并不需要進(jìn)行鎖定，并且 對(duì)以鎖定方式鎖定整個(gè)表沒有任何支持阻止所有訪問。在依賴于其線程安全但不依賴于其同步詳細(xì)信息的程序中，此類可以與{@code Hashtable}完全互操作
static class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
final float loadFactor;
Segment(float lf) { this.loadFactor = lf; }
}
ConcurrentHashMap 中有一個(gè) Segment 的概念。Segment 本身就相當(dāng)于一個(gè) HashMap 對(duì)象。同 HashMap 一樣，Segment 包含一個(gè) HashEntry 數(shù)組，數(shù)組中的每一個(gè) HashEntry 既是一個(gè)鍵值對(duì)，也是一個(gè)鏈表的頭節(jié)點(diǎn);
ConcurrentHashMap 集合中有 2 的N次方個(gè) Segment 對(duì)象，共同保存在一個(gè)名為 segments 的數(shù)組當(dāng)中;
采取了鎖分段技術(shù)，每一個(gè) Segment 就好比一個(gè)自治區(qū)，讀寫操作高度自治，Segment 之間互不影響;
但是操作同一個(gè) Segment需要加鎖的，但檢索操作 并不需要進(jìn)行鎖定，并且
對(duì)以鎖定方式鎖定整個(gè)表沒有任何支持阻止所有訪問。在依賴于其線程安全但不依賴于其同步詳細(xì)信息的程序中，此類可以與Hashtable完全互操作
總結(jié)：ConcurrentHashMap是線程安全的，并且鎖分離。ConcurrentHashMap內(nèi)部使用段(Segment)來表示這些不同的部分，每個(gè)段其實(shí)就是一個(gè)小的hash table，它們有自己的鎖。只要多個(gè)修改操作發(fā)生在不同的段上，它們就可以并發(fā)進(jìn)行
————————————————
版權(quán)聲明：本文為CSDN博主「代碼與她皆過客」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。
原文鏈接：
https://blog.csdn.net/weixin_44313584/article/details/115051897
鋒哥最新SpringCloud分布式電商秒殺課程發(fā)布
??????
??長按上方微信二維碼 2 秒
感謝點(diǎn)贊支持下哈 