摘要：通過鏈表法解決沖突問題，每個都有一個指針指向下一個，沖突元素不是鍵相同，而是值相同會構(gòu)成一個鏈表。并且最新插入的鍵值對始終位于鏈表首部。
哈希表定義：根據(jù)設(shè)定的hash函數(shù)和處理沖突的方式（開放定址、公共溢出區(qū)、鏈地址、重哈希...）將一組關(guān)鍵字映射到一個有限的連續(xù)的地址集上（即bucket數(shù)組或桶數(shù)組），并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表稱為hash表；這一映射過程稱為散列，所得存儲位置稱為哈希地址或散列地址。
一、定義
HashMap實現(xiàn)了Map接口，繼承AbstractMap。其中Map接口定義了鍵映射到值的規(guī)則，而AbstractMap類提供 Map 接口的骨干實現(xiàn)，以最大限度地減少實現(xiàn)此接口所需的工作。
public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable
二、構(gòu)造函數(shù)
HashMap提供了三個構(gòu)造函數(shù)：
HashMap()：構(gòu)造一個具有默認初始容量 (16) 和默認加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：構(gòu)造一個帶指定初始容量和默認加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個帶指定初始容量和加載因子的空 HashMap。
容量表示哈希表中桶的數(shù)量，初始容量是創(chuàng)建哈希表時的容量； 裝載因子：loadfactor = 表中填入的記錄數(shù)/哈希表的長度
所以loadfactor標志著哈希表的裝滿程度，直觀的看，裝載因子越小，發(fā)生沖突的概率越小（因為桶中還沒裝幾個數(shù)據(jù)，就需要擴容），也就是查找性能越好，但同時浪費的空間就變大。相反，裝載因子越大，發(fā)生沖突的概率越大（等到桶快填滿時才能擴容，比如，采用鏈表法處理沖突，在此種情況下，會導(dǎo)致鏈表過長），查找性能越差，同時浪費的空間會減少。
三、數(shù)據(jù)結(jié)構(gòu)
我們知道在Java中最常用的兩種結(jié)構(gòu)是數(shù)組和模擬指針(引用)，幾乎所有的數(shù)據(jù)結(jié)構(gòu)都可以利用這兩種來組合實現(xiàn)，HashMap也是如此。實際上HashMap是一個“鏈表散列”（數(shù)組和鏈表的結(jié)合體）。
可見，HashMap底層實現(xiàn)還是數(shù)組（橫行），只是數(shù)組的每一項（縱列）都是一條鏈。Entry為HashMap的內(nèi)部類，它包含了鍵key、值value、下一個節(jié)點next，以及hash值，這是非常重要的，正是由于Entry才構(gòu)成了table數(shù)組的項為鏈表。
總結(jié)
*1.HashMap的默認大小為16，即桶數(shù)組的默認長度為16；
2.HashMap的默認裝載因子是0.75；
3.HashMap內(nèi)部的桶數(shù)組存儲的是Entry對象，也就是鍵值對對象。
4.構(gòu)造器支持指定初始容量和裝載因子，為避免數(shù)組擴容帶來的性能問題，建議根據(jù)需求指定初始容量。裝載因子盡量不要修改，0.75是個比較靠譜的值。
5.桶數(shù)組的長度始終是2的整數(shù)次方（大于等于指定的初始容量），這樣做可以減少沖突概率，提高查找效率。（可以從indexfor函數(shù)中看出，h&(length-1),若length為奇數(shù)，length-1為偶數(shù)那么h&(length-1)結(jié)果的最后一位必然為0，也就是說所有鍵都被散列到數(shù)組的偶數(shù)下標位置,這樣會浪費近一半空間。另外，length為2的整數(shù)次方也保證了h&(length-1)與h%length等效）.
6.HashMap接受null鍵；
7.HashMap不允許鍵重復(fù)，但是值是可以重復(fù)的。若鍵重復(fù)，那么新值會覆蓋舊值。
8.HashMap通過鏈表法解決沖突問題，每個Entry都有一個next指針指向下一個Entry，沖突元素（不是鍵相同，而是hash值相同）會構(gòu)成一個鏈表。并且最新插入的鍵值對始終位于鏈表首部。
9.當容量超過閾值（threshold）時,會發(fā)生擴容，擴容后的數(shù)組是原數(shù)組的兩倍。擴容操作需要開辟新數(shù)組，并對原數(shù)組中所有鍵值對重新散列，非常耗時。我們應(yīng)該盡量避免HashMap擴容。
10.HashMap非線程安全。*
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/66106.html
