1.什么是HashMap
Hash:散列表,将一个任意长度通过某种算法(hash函数算法)转换成一个固定值。Java中采用移位算法。
Map:中文含义,地图(x,y轴),作用:存储
存储结构:Key-Value结构,数组+链表的数据结构
总结:通过Hash出来的值,然后通过值定位到这个map,然后value存储到这个map中
结构图如下图所示(使用visio画的图,比较搓):

2.源码分析
2.1 初始化参数说明
主要有以下几个初始化参数:
DEFAULT_INITIAL_CAPACITY(默认初始化容量)
MAXIMUM_CAPACITY(最大容量)
DEFAULT_LOAD_FACTOR(默认加载因子)


thresdhold:扩容时候的容量阈值

2.2 put方法分析
方法体如下图所示:

按红框序号说明如下:
- 如果刚初始化时候,table数组为空的话需要进行初始化table数组,并且初始化扩容阈值,初始化容量等变量的操作,具体方法如下:

- 如果输入的key值为空,则把value放入一个key为null的entry中
- 根据key值进行hash运算,并且计算出table数组中的index索引值
- 根据索引值i得到table数组中的Entry对象,然后变量Entry链表,找到key值相同的并且hash值一致的Entry对象,替换原有旧值,把新的值赋值给该对象。如果找不到,则跳转到第五步
- 新增一个Entry对象到entry链表中

图所示,如果当前的size大于等于容量阈值了,则进行扩容操作,容量扩容为原来容量的2倍
2.3 get方法分析

get方法比较简单,如果key值为null,则调用getForNullKey进行取值,如果不为空,则调用getEntry(key)方法进行取值操作

首先根据key值计算hash值,然后根据hash值跟key值进行比对,一致的情况下,返回该Entry对象进行取值操作。
2.4 Entry对象介绍
Entry对象只要是table数组中某个位置下的一个Entry链表中的具体对象,存有key value hash 和该对象的下一个entry对象。其结构如下图所示:

2.5 扩容机制(resize方法)

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;
}
}
}
网友评论