import java.util.Map;
import java.util.Objects;
public class HashMap <K,V>{
static final int DEFAULT_INITIAL_CAPACITY = 4;
static final int MAXIMUM_CAPACITY = 1 << 30; // 2 的 30 次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;
int initialCapacity ;
float loadFactor;
int threshold;// 表单阈值
transient int size;
// 表单
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
transient HashMapEntry<K, V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity) {
this(initialCapacity,DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if(initialCapacity<0){
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
}
if (initialCapacity>MAXIMUM_CAPACITY) {
initialCapacity=MAXIMUM_CAPACITY;
} else if(initialCapacity<DEFAULT_INITIAL_CAPACITY){
initialCapacity=DEFAULT_INITIAL_CAPACITY;
}
if(loadFactor<=0 || Float.isNaN(loadFactor)){
throw new IllegalArgumentException("Illegal load factor:"+loadFactor);
}
threshold = initialCapacity;
}
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key ==null) {
return putForNullKey(value);
}
// java 7 int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
// java 8 int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
int h;
int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
int i = indexFor(hash,table.length);
System.out.println("hash = "+hash +" i = "+i);
for (HashMapEntry<K, V> e=table[i];e!=null; e=e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
System.out.println("override");
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
addEntry(hash, key, value, i);
return null;
}
public V get(Object key) {
if (key == null) {
System.err.println("return null");
return getForNullKey(key);
}
int h;
int hash = (key == null) ? 0:(h = key.hashCode()) ^ (h >>> 16);
for (HashMapEntry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
System.out.println("get key = "+ e.key);
Object k;
if (e.hash == hash &&
((e.key == key || e.key.equals(key)))) {
System.out.println(" return "+ e.getValue());
return e.getValue();
}
}
System.err.println("key is null");
return null;
}
private V getForNullKey(Object key) {
if (size == 0) {
return null;
}
for (HashMapEntry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
return e.value;
}
}
return null;
}
public V remove(Object key) {
if (size == 0) {
return null;
}
int h;
int hash = (key == null) ? 0:(h = key.hashCode()) ^ (h >>> 16);
int i = indexFor(hash, table.length);
HashMapEntry<K, V> prev = table[i];
HashMapEntry<K, V> e = prev;
while (e!= null) {
HashMapEntry<K, V> next=e.next;
Object k;
if (e.hash == hash &&
((k = e.key ) == key || (key != null && key.equals(k)))) {
size -- ;
if (prev == e) {
table[i] = next;
}else {
prev.next = next;
}
return e.getValue();
}
prev = e;
e = next;
}
return e == null ?null: e.getValue();
}
/**
* Returns index for hash code h.
*/
private int indexFor(int hash, int length) {
// System.out.println(String.format("hash = %d , length = %d", hash,length));
return hash & (length-1);
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
System.out.println("inflate table");
int capacity = roundUpToPowerOf2(toSize);
float thresholdFloat = capacity * loadFactor;
if(thresholdFloat > MAXIMUM_CAPACITY+1){
thresholdFloat = MAXIMUM_CAPACITY+1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
private int roundUpToPowerOf2(int number) {
// assert number >=0
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) != 0
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
: 1;
System.out.println("rounded = "+rounded);
return rounded;
}
private V putForNullKey(V value) {
for (HashMapEntry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
addEntry(0,null,value,0);
return null;
}
private void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold)&& (null != table[bucketIndex])) {
resize(2 * table.length);
int h;
hash = (null != key)? (h = key.hashCode()) ^ (h >>> 16):0;
// System.out.println("hash is "+ hash);
}
createEntry(hash,key,value,bucketIndex);
}
private void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K, V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<K, V>(hash, key, value, e);
size++;
System.out.println("value = "+table[bucketIndex].getValue());
}
private void resize(int i) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable .length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold= Integer.MAX_VALUE;
return;
}
}
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
HashMapEntry<K,V> next;
int hash;
/**
* Creates new entry.
*/
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
void recordAccess(HashMap<K, V> hasMap) {
}
}
}
测试
HashMap<String , Integer> studentHashMap = new HashMap<>(15);
studentHashMap.put("lilei", 6);
studentHashMap.put("wangwu",11);
studentHashMap.put("lilei3", 12);
studentHashMap.put("lilei4", 9);
System.out.println(" lilei age "+ studentHashMap.get("lilei"));
System.out.println(" wangwu age "+ studentHashMap.get("wangwu"));
System.out.println(" lilei3 age "+ studentHashMap.get("lilei3"));
System.out.println(" lilei4 age "+ studentHashMap.get("lilei4"));
studentHashMap.remove("lilei");
System.out.println(" lilei age "+ studentHashMap.get("lilei"));
