一直對(duì)jdk的map內(nèi)部結(jié)構(gòu)很是困惑赡模，鼓起勇氣啃了源碼，自己寫了一個(gè)簡單版本map，希望對(duì)java小萌新有點(diǎn)幫助觅廓。
源碼
/**帶有自動(dòng)擴(kuò)容能力**/
public class myHashMapPlus<K, V> implements Map<K, V> {
volatile int size = 0;
private Entry<K, V>[] table;
private static int DEFAULT_INITIAL_CAPACITY = 16;
private int MAXIMUM_CAPACITY = Integer.MAX_VALUE;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
private float loadFactor;
/**size>ExpansiontThreshold擴(kuò)容【ExpansiontThreshold=capacity*2*DEFAULT_LOAD_FACTOR】**/
private int expansiontThreshold;
/**數(shù)組長度,size>ExpansiontThreshold擴(kuò)容[capacity=capacity*2]**/
private int capacity;
public myHashMapPlus() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public myHashMapPlus(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public myHashMapPlus(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
}
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
}
if(initialCapacity<DEFAULT_INITIAL_CAPACITY){
initialCapacity=DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
}
this.loadFactor = loadFactor;
this.expansiontThreshold = (int) (initialCapacity * this.loadFactor);
this.capacity = initialCapacity;
this.table = new Entry[capacity];
}
/**
* 通過key進(jìn)行hash
* hash和數(shù)組長度得到index數(shù)組下標(biāo)
* 判斷為空：直接存儲(chǔ)
* 判讀不為空：沖突--用鏈表解決
* 返回?cái)?shù)據(jù)
*
* @param k
* @param v
* @return
*/
public V put(K k, V v) {
if (k == null) {
throw new IllegalArgumentException("key should not null");
}
/**確保容量可用，不可用擴(kuò)容**/
ensureCapacityInternal(size + 1);
int index = hash(k);
Entry<K, V> entry = table[index];
Entry<K, V> bakEntry =entry;
if (entry == null) {
table[index] = new Entry<K, V>(k, v, k.hashCode(), null);
size++;
return v;
}
/**頭插法**/
while (entry != null) {
/**已經(jīng)存在相同的key**/
if(entry.k.equals(k)){
entry.v=v;
return v;
}
entry=entry.next;
}
/**不存在不相同的key**/
table[index] = new Entry<K, V>(k, v, k.hashCode(), bakEntry);
size++;
return v;
}
// /**
// * 擴(kuò)容重新計(jì)算存入新的table的時(shí)候用
// *
// * @param k
// * @param v
// * @param newTable
// * @return
// */
// public V put(K k, V v,Entry[] newTable) {
// if (k == null) {
// throw new IllegalArgumentException("key should not null");
// }
// int index = hash(k);
// Entry<K, V> entry = newTable[index];
// if (entry == null) {
// newTable[index] = new Entry<K, V>(k, v, k.hashCode(), null);
// } else {
// //頭插法
// newTable[index] = new Entry<K, V>(k, v, k.hashCode(), entry);
// }
// size++;
// return v;
// }
private void ensureCapacityInternal(int miniCapacity) {
if (miniCapacity > expansiontThreshold) {
/**擴(kuò)容**/
grow(miniCapacity);
}
}
/**
* 擴(kuò)容數(shù)組
*
* @param miniCapacity
*/
private void grow(int miniCapacity) {
System.out.println("grow table----------------");
if (miniCapacity > Integer.MAX_VALUE) {
throw new IllegalArgumentException("capacity is max, cannot put " +
"any element");
}
int newCapacity = capacity * 2;
if (newCapacity > Integer.MAX_VALUE) {
newCapacity = Integer.MAX_VALUE;
}
this.capacity = newCapacity;
this.expansiontThreshold = (int) (capacity * loadFactor);
Entry[] newTable = new Entry[newCapacity];
/**擴(kuò)容后涵但，需要將原來table中所有的值杈绸，重新計(jì)算存入新的table**/
ReHashOriginalValue(newTable);
this.table = newTable;
}
/**
* Transfers all entries from current table to newTable.
*
* @param newTable
*/
private void ReHashOriginalValue(Entry[] newTable) {
System.out.println("Transfers all entries from current table to newTable.");
for (Entry<K, V> e : table) {
while (null != e) {
Entry<K, V> next = e.next;
int index = hash(e.getKey());
e.next = newTable[index];
newTable[index] = e;
e = next;
}
}
}
/**
* key的hashcode和數(shù)組長度取模
*
* @param k
* @return
*/
private int hash(K k) {
int hash = k.hashCode() % this.capacity;
return Math.abs(hash);
}
/**
* 1.通過key進(jìn)行hashcode計(jì)算index
* 2.index下表數(shù)組查詢得到Entry
* 3.Entry==null,沒有找到value
* 4.Entry！=null矮瘟。判斷得到的hashcode是否相等
* 5.hashcode不相等瞳脓，判斷是否有next，next為空返回null澈侠，不存在值
* 6.hashcode不相等劫侧，判斷是否有next，next不為空哨啃，用下一個(gè)重復(fù)5.6.7動(dòng)作
* 7.hashcode相等烧栋，返回值
*
* @param k
* @return
*/
public V get(K k) {
if (size == 0) {
return null;
} else {
int index = hash(k);
Entry<K, V> entry = findValue(k, table[index]);
if (entry != null) {
return entry.getValue();
}
}
return null;
}
private Entry<K, V> findValue(K k, Entry<K, V> kvEntry) {
if (kvEntry == null) {
return null;
}
if (k.equals(kvEntry.getKey())) {
return kvEntry;
} else {
if (kvEntry.next != null) {
return findValue(k, kvEntry.next);
}
}
return null;
}
public int size() {
return this.size;
}
class Entry<K, V> implements Map.Entry<K, V> {
K k;
V v;
int hash;
Entry<K, V> next;
public Entry(K k, V v, int hash, Entry<K, V> next) {
this.k = k;
this.v = v;
this.hash = hash;
this.next = next;
}
public K getKey() {
return k;
}
public V getValue() {
return v;
}
}
}
簡單測試--測試是否自動(dòng)擴(kuò)容
public class myHashMapPlusTest {
public static void main(String[] args) {
myHashMapPlus map = new myHashMapPlus();
for (int i = 0; i < 1024; i++) {
map.put(i, i);
}
for (int i = 0; i < 1024; i++) {
System.out.println(map.get(i));
}
}
}
自動(dòng)擴(kuò)容測試結(jié)果
image.png
擴(kuò)容條件
數(shù)組長度size>ExpansiontThreshold需要擴(kuò)容，擴(kuò)容后數(shù)組的新容量為：capacity=capacity*2
擴(kuò)容后的下次再擴(kuò)容閾值為
ExpansiontThreshold=2*（capacity * DEFAULT_LOAD_FACTOR)
說明：jdk中DEFAULT_LOAD_FACTOR默認(rèn)為0.75棘催，這里沿用即可
