一直对jdk的map内部结构很是困惑，鼓起勇气啃了源码，自己写了一个简单版本map，希望对java小萌新有点帮助。
源码
/**带有自动扩容能力**/
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扩容【ExpansiontThreshold=capacity*2*DEFAULT_LOAD_FACTOR】**/
private int expansiontThreshold;
/**数组长度,size>ExpansiontThreshold扩容[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进行hash
* hash和数组长度得到index数组下标
* 判断为空：直接存储
* 判读不为空：冲突--用链表解决
* 返回数据
*
* @param k
* @param v
* @return
*/
public V put(K k, V v) {
if (k == null) {
throw new IllegalArgumentException("key should not null");
}
/**确保容量可用，不可用扩容**/
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) {
/**已经存在相同的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;
}
// /**
// * 扩容重新计算存入新的table的时候用
// *
// * @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) {
/**扩容**/
grow(miniCapacity);
}
}
/**
* 扩容数组
*
* @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];
/**扩容后，需要将原来table中所有的值，重新计算存入新的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和数组长度取模
*
* @param k
* @return
*/
private int hash(K k) {
int hash = k.hashCode() % this.capacity;
return Math.abs(hash);
}
/**
* 1.通过key进行hashcode计算index
* 2.index下表数组查询得到Entry
* 3.Entry==null,没有找到value
* 4.Entry！=null。判断得到的hashcode是否相等
* 5.hashcode不相等，判断是否有next，next为空返回null，不存在值
* 6.hashcode不相等，判断是否有next，next不为空，用下一个重复5.6.7动作
* 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;
}
}
}
简单测试--测试是否自动扩容
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));
}
}
}
自动扩容测试结果
image.png
扩容条件
数组长度size>ExpansiontThreshold需要扩容，扩容后数组的新容量为：capacity=capacity*2
扩容后的下次再扩容阈值为
ExpansiontThreshold=2*（capacity * DEFAULT_LOAD_FACTOR)
说明：jdk中DEFAULT_LOAD_FACTOR默认为0.75，这里沿用即可
网友评论