JAVA中HashMap隘世、ArrayList栈雳、StringBuilder等的擴容機制

原文地址:https://www.cnblogs.com/lq147760524/p/6713677.html

第一部分:
  • HashMap hmap=new HashMap<>();
  • HashSet hset=new HashSet<>();
  • Hashtable htable=new Hashtable<>();
第二部分:
  • CopyOnWriteArrayList coarray=new CopyOnWriteArrayList<>();
  • ArrayList array=new ArrayList<>();
  • Vector vec=new Vector<>();
第三部分:
  • StringBuffer sb=new StringBuffer();
  • StringBuilder sbu=new StringBuilder();

從以下幾個源碼方面分析:(JDK1.8)

  1. 初始容量忘苛。
  2. 擴容機制蝉娜。
  3. 同類型之間對比唱较。

1.1 HashMap

初始容量定義:默認為1 << 4(16)。最大容量為1<< 30召川。

/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

擴容加載因子為(0.75)南缓,第一個臨界點在當(dāng)HashMap中元素的數(shù)量等于table數(shù)組長度加載因子(160.75=12),如果超出則按oldThr << 1(原長度*2)擴容荧呐。

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* Constructs an empty HashMap with the default initial capacity
* (16) and the default load factor (0.75).
*/
if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold

1.2 HashSet

初始容量定義:16汉形。因為構(gòu)造一個HashSet,其實相當(dāng)于新建一個HashMap倍阐,然后取HashMap的Key概疆。擴容機制和HashMap一樣。

public HashSet(Collection c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

1.3 HashTable

Hashtable htable=new Hashtable<>();
public class Hashtable extends Dictionary

初始容量定義:capacity (11)峰搪。

/**
* Constructs a new, empty hashtable with a default initial capacity (11)
* and load factor (0.75).
*/
public Hashtable() {
    this(11, 0.75f);
}

擴容加載因子(0.75)岔冀,當(dāng)超出默認長度(int)(110.75)=8時,擴容為old2+1概耻。

int newCapacity = (oldCapacity << 1) + 1;

HashTable和HashMap區(qū)別

  1. 繼承不同使套。
public class Hashtable extends Dictionary implements Map
public class HashMap extends AbstractMap implements Map
  1. Hashtable 中的方法是同步的,而HashMap中的方法在缺省情況下是非同步的鞠柄。 在多線程并發(fā)的環(huán)境下侦高,可以直接使用Hashtable,但是要使用HashMap的話就要自己增加同步處理了厌杜。
  2. Hashtable中奉呛,key和value都不允許出現(xiàn)null值。在HashMap中期奔,null可以作為鍵侧馅,這樣的鍵只有一個;可以有一個或多個鍵所對應(yīng)的值為null呐萌。當(dāng)get()方法返回null值時馁痴,即可以表示 HashMap中沒有該鍵,也可以表示該鍵所對應(yīng)的值為null肺孤。因此罗晕,在HashMap中不能由get()方法來判斷HashMap中是否存在某個鍵, 而應(yīng)該用containsKey()方法來判斷赠堵。
  3. 兩個遍歷方式的內(nèi)部實現(xiàn)上不同小渊。 Hashtable、HashMap都使用了 Iterator茫叭。而由于歷史原因酬屉,Hashtable還使用了Enumeration的方式 。
  4. 哈希值的使用不同,HashTable直接使用對象的hashCode呐萨。而HashMap重新計算hash值杀饵。
  5. Hashtable和HashMap它們兩個內(nèi)部實現(xiàn)方式的數(shù)組的初始大小和擴容的方式不同。 HashTable中hash數(shù)組默認大小是11谬擦,增加的方式是 old2+1切距。HashMap中hash數(shù)組的默認大小是16, 增加的方式是 old2惨远。

2.1 CopyOnWriteArrayList

/**
* Creates an empty list.
*/
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}

CopyOnWriteArrayList在做修改操作時谜悟,每次都是重新創(chuàng)建一個新的數(shù)組,在新數(shù)組上操作北秽,最終再將新數(shù)組替換掉原數(shù)組葡幸。因此,在做修改操作時贺氓,仍可以做讀取操作礼患,讀取直接操作的原數(shù)組。讀和寫操作的對象都不同掠归,因此讀操作和寫操作互不干擾。只有寫與寫之間需要進行同步等待悄泥。另外虏冻,原數(shù)組被聲明為volatile,這就保證了弹囚,一旦數(shù)組發(fā)生變化厨相,則結(jié)果對其它線程(讀線程和其它寫線程)是可見的。

CopyOnWriteArrayList并不像ArrayList一樣指定默認的初始容量鸥鹉。它也沒有自動擴容的機制蛮穿,而是添加幾個元素,長度就相應(yīng)的增長多少毁渗。

CopyOnWriteArrayList適用于讀多寫少践磅,既然是寫的情況少,則不需要頻繁擴容灸异。并且修改操作每次在生成新的數(shù)組時就指定了新的容量府适,也就相當(dāng)于擴容了,所以不需要額外的機制來實現(xiàn)擴容肺樟。

2.2 ArrayList<String> array=new ArrayList<>();

初始容量定義:10檐春。

/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
  • 擴容:oldCapacity + (oldCapacity >> 1),即原集合長度的1.5倍么伯。
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

2.3 Vector<String> vec=new Vector<>();

  • 初始容量定義:10疟暖。
public Vector() {
this(10);
}

擴容:當(dāng)擴容因子大于0時,新數(shù)組長度為原數(shù)組長度+擴容因子,否則新數(shù)組長度為原數(shù)組長度的2倍俐巴。

// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);

小結(jié):

  1. ArrayList與Vector初始容量都為10骨望。

  2. 擴容機制不同,當(dāng)超出當(dāng)前長度時ArrayList擴展為原來的1.5倍窜骄,而若不考慮擴容因子Vector擴展為原來的2倍锦募。

  3. ArrayList為非線程安全的,處理效率上較Vector快邻遏,若同時考慮線程安全和效率糠亩,可以使用 CopyOnWriteArrayList。

3.1 StringBuffer sb=new StringBuffer();

初始容量定義:16准验。

public StringBuffer() {
super(16);
}
public final class StringBuffer
extends AbstractStringBuilder
implements java.io.Serializable, CharSequence

擴容赎线,因為StringBuffer extends AbstractStringBuilder,所以實際上是用的是AbstractStringBuilder的擴容方法糊饱,當(dāng)用append(str),添加字符串時垂寥,假設(shè)字符串中已有字符長度為count的字符串,初始長度value=16,若要添加的字符串長度(count+str.length())<=(value2+2)則按value2+2長度擴容,并且value=value2+2另锋,若(count+str.length())>(value2+2)滞项,則按count+str.length()長度擴容,并且value=count+str.length()夭坪。下次超出時再按以上方法與value*2+2比較擴容文判。

private int newCapacity(int minCapacity) {
// overflow-conscious code
int newCapacity = (value.length << 1) + 2;
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;

3.2 StringBuilder sbu=new StringBuilder();

public final class StringBuilder
extends AbstractStringBuilder
implements java.io.Serializable, CharSequence
public StringBuilder() {
super(16);
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int newCapacity = (value.length << 1) + 2;
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;

小結(jié):

  1. StringBuilder是jdk1.5引進的,而StringBuffer在1.0就有了室梅;
  2. StringBuilder和StringBuffer都是可變的字符串戏仓。能夠通過append或者insert等方法改動串的內(nèi)容;
  3. StringBuffer是線程安全的而StringBuilder不是亡鼠,因而在多線程的環(huán)境下優(yōu)先使用StringBuffer赏殃,而其它情況下推薦使用StringBuilder,由于它更快间涵。
  4. StringBuilder和StringBuffer都繼承自AbstractStringBuilder類仁热,AbStractStringBuilder主要實現(xiàn)了擴容、append浑厚、insert方法股耽。StrngBuilder和StringBuffer的相關(guān)方法都直接調(diào)用的父類。
  5. StringBuilder和StringBuffer的初始容量都是16,程序猿盡量手動設(shè)置初始值钳幅。以避免多次擴容所帶來的性能問題物蝙;
  6. StringBuilder和StringBuffer的擴容機制是這種:首先試著將當(dāng)前數(shù)組容量擴充為原數(shù)組容量的2倍加上2,假設(shè)這個新容量仍然小于預(yù)定的最小值(minimumCapacity)敢艰,那么就將新容量定為(minimumCapacity)诬乞,最后推斷是否溢出,若溢出,則將容量定為整型的最大值0x7fffffff震嫉。
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末森瘪,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子票堵,更是在濱河造成了極大的恐慌扼睬,老刑警劉巖,帶你破解...
    沈念sama閱讀 206,968評論 6 482
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件悴势,死亡現(xiàn)場離奇詭異窗宇,居然都是意外死亡,警方通過查閱死者的電腦和手機特纤,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,601評論 2 382
  • 文/潘曉璐 我一進店門军俊,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人捧存,你說我怎么就攤上這事粪躬。” “怎么了昔穴?”我有些...
    開封第一講書人閱讀 153,220評論 0 344
  • 文/不壞的土叔 我叫張陵镰官,是天一觀的道長。 經(jīng)常有香客問我吗货,道長朋魔,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 55,416評論 1 279
  • 正文 為了忘掉前任卿操,我火速辦了婚禮,結(jié)果婚禮上孙援,老公的妹妹穿的比我還像新娘害淤。我一直安慰自己,他們只是感情好拓售,可當(dāng)我...
    茶點故事閱讀 64,425評論 5 374
  • 文/花漫 我一把揭開白布窥摄。 她就那樣靜靜地躺著,像睡著了一般础淤。 火紅的嫁衣襯著肌膚如雪崭放。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,144評論 1 285
  • 那天鸽凶,我揣著相機與錄音币砂,去河邊找鬼。 笑死玻侥,一個胖子當(dāng)著我的面吹牛决摧,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播,決...
    沈念sama閱讀 38,432評論 3 401
  • 文/蒼蘭香墨 我猛地睜開眼掌桩,長吁一口氣:“原來是場噩夢啊……” “哼边锁!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起波岛,我...
    開封第一講書人閱讀 37,088評論 0 261
  • 序言:老撾萬榮一對情侶失蹤茅坛,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后则拷,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體贡蓖,經(jīng)...
    沈念sama閱讀 43,586評論 1 300
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,028評論 2 325
  • 正文 我和宋清朗相戀三年隔躲,在試婚紗的時候發(fā)現(xiàn)自己被綠了摩梧。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,137評論 1 334
  • 序言:一個原本活蹦亂跳的男人離奇死亡宣旱,死狀恐怖仅父,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情浑吟,我是刑警寧澤笙纤,帶...
    沈念sama閱讀 33,783評論 4 324
  • 正文 年R本政府宣布,位于F島的核電站组力,受9級特大地震影響省容,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜燎字,卻給世界環(huán)境...
    茶點故事閱讀 39,343評論 3 307
  • 文/蒙蒙 一腥椒、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧候衍,春花似錦笼蛛、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,333評論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至妖异,卻和暖如春惋戏,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背他膳。 一陣腳步聲響...
    開封第一講書人閱讀 31,559評論 1 262
  • 我被黑心中介騙來泰國打工响逢, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人棕孙。 一個月前我還...
    沈念sama閱讀 45,595評論 2 355
  • 正文 我出身青樓龄句,卻偏偏與公主長得像回论,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子分歇,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 42,901評論 2 345

推薦閱讀更多精彩內(nèi)容