1.什么是HashMap
Hash：散列表，将一个任意长度通过某种算法（hash函数算法）转换成一个固定值。Java中采用移位算法。
Map：中文含义，地图（x，y轴），作用：存储
存储结构：Key-Value结构，数组+链表的数据结构
总结：通过Hash出来的值，然后通过值定位到这个map，然后value存储到这个map中
结构图如下图所示（使用visio画的图，比较搓）：
HashMap数据结构.png
2.源码分析
2.1 初始化参数说明
主要有以下几个初始化参数：
DEFAULT_INITIAL_CAPACITY（默认初始化容量）
MAXIMUM_CAPACITY（最大容量）
DEFAULT_LOAD_FACTOR（默认加载因子）
image.png
image.png
thresdhold：扩容时候的容量阈值
image.png
2.2 put方法分析
方法体如下图所示：
image.png
按红框序号说明如下：
- 如果刚初始化时候，table数组为空的话需要进行初始化table数组，并且初始化扩容阈值，初始化容量等变量的操作，具体方法如下：
image.png
- 如果输入的key值为空，则把value放入一个key为null的entry中
- 根据key值进行hash运算，并且计算出table数组中的index索引值
- 根据索引值i得到table数组中的Entry对象，然后变量Entry链表，找到key值相同的并且hash值一致的Entry对象，替换原有旧值，把新的值赋值给该对象。如果找不到，则跳转到第五步
- 新增一个Entry对象到entry链表中
image.png
图所示，如果当前的size大于等于容量阈值了，则进行扩容操作，容量扩容为原来容量的2倍
2.3 get方法分析
image.png
get方法比较简单，如果key值为null，则调用getForNullKey进行取值，如果不为空，则调用getEntry(key)方法进行取值操作
image.png
首先根据key值计算hash值，然后根据hash值跟key值进行比对，一致的情况下，返回该Entry对象进行取值操作。
2.4 Entry对象介绍
Entry对象只要是table数组中某个位置下的一个Entry链表中的具体对象，存有key value hash 和该对象的下一个entry对象。其结构如下图所示：
image.png
2.5 扩容机制（resize方法）
image.png
3.常见问题
- key可以为空吗？把null当场一个key来存储
- 如果Hash key重复了，value会覆盖吗？（会，如果重复了，会把旧的值返回，新的值存储在key中对应的entry）
- HashMap什么时候扩容？（put的时候，比且容量达到3/4时候会进行扩容操作，扩容原来容量的2倍）
4.不足之处
- key是否有重复的问题
- 时间复杂度：hash算法决定了效率的高低
- 伸缩性角度：每当hashMap需要扩容的时候，需要重新去add Entry对象，需要重新hash。然后重新放入新的Entry table数组中。如果在工作中，知道hashMap需要存储多少值（几千或者几万的时候），最好先指定它的扩容大小，防止在put的时候进行再次扩容很多次，造成效率低下。
5.自定义HashMap（简易版，未实现自动扩容）
先定义一个Map接口
package lyx.demo.hashmap;
/**
* Created by landyChris on 2017/10/29.
*/
public interface Map<K,V> {
V put(K key,V value);
V get(K key);
int size();
public interface Entry<K,V> {
K getKey();
V getValue();
}
}
然后实现Map接口即可，具体如下代码：
package lyx.demo.hashmap;
/**
* Created by landyChris on 2017/10/29.
*/
public class HashMap<K,V> implements Map<K,V> {
//默认容量
private static int defaultLength = 16;
//默认加载因子
private static double defualtLoaderFactor = 0.75;
private Entry<K,V> table[] = null;
private int size = 0;
public HashMap() {
this(defaultLength,defualtLoaderFactor);
}
public HashMap(int length,double loaderFactor) {
defaultLength = length;
defualtLoaderFactor = loaderFactor;
table = new Entry[defaultLength];
}
private int hash(K k) {
int m = defaultLength;
int i = k.hashCode() % m;
return i > 0 ? i : -i;
}
@Override
public V put(K key, V value) {
int index = hash(key);
Entry<K,V> entry = table[index];
if(entry == null) {
table[index] = new Entry(key,value,null);
}else {
table[index] = new Entry(key,value,entry);
System.out.println("oldVlaue=" + table[index].next.getValue());
}
size ++;
return table[index].getValue();
}
@Override
public V get(K key) {
int index = hash(key);
if(table[index] == null) {
return null;
}
return find(table[index],key);
}
private V find(Entry<K, V> entry, K key) {
if(key == entry.getKey()||key.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(entry.next,key);
}
}
return null;
}
@Override
public int size() {
return size;
}
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;
}
}
}
网友评论