一、HashMap
Hash：散列将一个任意的长度通过某种（hash函数算法)算法转换成一个固定的值
Map：键值对存储
总结：通过Hash出来的值，通过值定位到这个map，然后value存储这个map中
1.Key可以为空，Null
2.相同的key重复put，后一个会覆盖前一个
3.HashMap什么时候做扩容？当进行put操作，并且达到0.75阈值时，扩容都是2的 倍数去扩容。
4.HashMap table:数组+链表
二.自己实现HashMap
package com;
public interface Map<K,V> {
public V put(K k ,V v);
public V get(K k);
public int size();
public interface Entry<K,V>{
public K getKey();
public V getValue();
}
}
package com;
public class HashMap<K, V> implements Map<K, V> {
private static int defaultLength = 16;
private static double defaultLoader = 0.75;
private Entry[] table = null;
private int size = 0;
public HashMap() {
this(defaultLength, defaultLoader);
}
public HashMap(int length, double loader) {
defaultLength = length;
defaultLoader = loader;
table = new Entry[defaultLength];
}
@Override
public V put(K k, V v) {
size++;
int index = hash(k);
Entry<K, V> entry = table[index];
if (entry == null) {
table[index] = newEntry(k, v, null);
} else {
table[index] = newEntry(k, v, entry);
// System.out.println(table[index].next.getValue());
}
return (V) table[index].getValue();
}
@Override
public V get(K k) {
int index = hash(k);
if (table[index] == null) {
return null;
}
return (V) find(k, table[index]);
}
public V find(K k, Entry<K, V> entry) {
if (k == entry.getKey() || k.equals(entry.getKey())) {
if (entry.next != null) {
System.out.println("OldValue1:" + entry.next.getValue());
}
return entry.getValue();
} else {
if (entry.next != null) {
System.out.println("OldValue2:" + entry.next.getValue());
return find(k, entry.next);
}
}
return null;
}
@Override
public int size() {
return size++;
}
public int hash(K k) {
int m = defaultLength;
int i = k.hashCode() % m;
return i >= 0 ? i : -i;
}
public Entry<K, V> newEntry(K k, V v, Entry<K, V> next) {
return new Entry<K, V>(k, v, next);
}
public class Entry<K, V> implements Map.Entry<K, V> {
K k;
V v;
Entry<K, V> next;
public Entry(K k, V v, Entry<K, V> next) {
this.k = k;
this.v = v;
this.next = next;
}
@Override
public K getKey() {
return k;
}
@Override
public V getValue() {
return v;
}
}
}
三.不足之处：
与Key是否重复有关
1、伸缩性
2、时间复杂度
伸缩性角度：
每当HashMap扩容的时候需要重新去add entry对象 需要重新Hash。然后放入我们新的entry table数组里面。
如果知道我们工作中HashMap大概需要多少值，几千或者几万时最好先指定好他们的扩容大小，防止在put的时候进行多次扩容
