几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,
知道Hashtable和HashMap之间的区别,
那好,我们以面试题的方式来谈一谈HasnMap!
先来些简单的问题
“你用过HashMap吗?” “什么是HashMap?”
HashMap实现了Map接口,Map接口对键值对进行映射。 Map中不允许重复的键 。
Map接口有两个基本的实现,HashMap和TreeMap。
TreeMap保存了对象的排列次序,而HashMap则不能。
HashMap允许键和值为null。 HashMap是非synchronized的;
简单的说HashMap的存储结构是由 数组和链表 共同完成的
HashMap是Y轴方向是数组,X轴方向就是链表的存储方式
“你知道HashMap的工作原理吗?” “你知道HashMap的get()方法的工作原理吗?”
HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,
使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,
我们先 将 Key 做 Hash 算法,取得 Key 所对应的数据用于找到bucket位置来储存Entry对象。
然后再调用equals方法,来判断他们是不是内容相同,是做覆盖处理还是链表操作;
“当两个对象的hashcode相同怎么储存?”
因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。
因为HashMap使用链表存储对象,
这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。
后面还可以说
String, Interger这样的wrapper类作为HashMap的键是再适合不过了,
而且String最为常用。
因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了
“如果两个键的hashcode相同,你如何获取值对象?”
当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,
找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,
最终找到要找的值对象。
“如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?”
默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,
和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,
来重新调整map的大小,并将原来的对象放入新的bucket数组中。
这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。
“你了解重新调整HashMap大小存在什么问题吗?”
当重新调整HashMap大小的时候,存在条件竞争,
因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。
在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,
HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。
如果条件竞争发生了,那么就死循环了。
这个时候,你可以质问面试官,为什么这么奇怪,要在多线程的环境下使用HashMap呢?:)
好下面我们简单看看hashMap的源代码吧(jdk1.7)
1 -HashMap的定义
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
可以看出HashMap集成了AbstractMap抽象类,实现了Map,Cloneable,Serializable接口,
AbstractMap抽象类继承了Map提供了一些基本的实现。
2.底层存储
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
// 默认初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子为0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final Entry<?,?>[] EMPTY_TABLE = {};
// 空Entry[]
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 已存储元素的数量
transient int size;
// 扩容临界值
int threshold;
// 加载因子
final float loadFactor;
可以看出来, 默认初始容量为16, 最大容量为2的30次方,
默认加载因子为0.75f, table是一个空Entry数组
-下面我们来看一下, Entry数组结构
static class Entry<K,V> implements Map.Entry<K,V> {
//key(键)
final K key;
//value(值)
V value;
//指向下一个Entry对象(单向链表)
Entry<K,V> next;
//hash(哈希值)
int hash;
//初始话Entry[]
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
图表的形式
数组 链表的根节点 下一个节点(next)
4.构造方法
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
我们可以看到,调用双参构造器 传入初始容量16,和加载因子0.75
/**
* 构造一个指定初始容量和加载因子的HashMap
*/
public HashMap( int initialCapacity, float loadFactor) {
//【1】 初始容量和加载因子合法校验
if (initialCapacity < 0)
throw new IllegalArgumentException( "Illegal initial capacity: " +
initialCapacity);
//【2】
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException( "Illegal load factor: " +
loadFactor);
//【3】 赋值加载因子
this.loadFactor = loadFactor;
// 赋值扩容临界值
threshold = initialCapacity;
init();
}
【1】
,首先是判断传入的容量是不是小于0,what? 不是说好传入的是默认容量16吗?
为什么有这个判断?这样判断是不是傻!
no!no!no!
我们退一步,如果我们初始化HashMap调用的不是无参的构造器,而是单参构造器呢
(这货可不是一个构造器)
其实初始化HashMap时,我们可以定义Map的容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
【2】
,接下来判断的是定义Map的容量是否超过 1 <<30,这是一个好大的数,不做计算,
有兴趣的小伙伴可以拿出一张纸和一根笔计算一下,
【3】
,我们可以看到把加载因子 和容量 复制给了属性loadfactor,和threshold,
我们先记住这两个属性
然后没然后了,是的,只是初始化了属性!
5.增加
public V put(K key, V value) {
//【1】 如果key为null,调用putForNullKey方法进行存储
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//【2】 如果key为null,调用putForNullKey方法进行存储
if (key == null)
return putForNullKey(value);
//【3】 计算key对应的hash值
int hash = hash(key);
// 通过key的hash值查找在数组中的index位置
int i = indexFor(hash, table.length);
//【4】 取出数组index位置的链表,遍历链表找查看是有已经存在相同的key
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 通过对比hash值、key判断是否已经存在相同的key
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 如果存在,取出当前key对应的value,供返回
V oldValue = e.value;
// 用新value替换之旧的value
e.value = value;
e.recordAccess(this);
// 返回旧value,退出方法
return oldValue;
}
}
// 如果不存在相同的key
// 修改版本+1
modCount++;
//【5】 在数组i位置处添加一个新的链表节点
addEntry(hash, key, value, i);
// 没有相同key的情况,返回null
return null;
}
【1】 -首先判断属性table是不是为空,第一次肯定是空(上面的属性已经说了),然后就是初始化Entry数组了
private void inflateTable(int toSize) {
//对容量进行取值,只能是2的倍数,比如如果传入的threshold是15,那么这里取值为16
int capacity = roundUpToPowerOf2(toSize);
// 扩容临界值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY +1;
//为table赋值了,就是初始化HashMap了(Entry对象数据加单向链表)
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
为什么一定要是2的倍数,我们下面说
接着,就是加载因子的作用了,首先是容量乘以加载因子,这里我们传入的容量是16,乘以加载因子,那么就是12了对吧!,
然后就是在12和1<<30值中取最小值,
所以threshold的值不再是16,而变成了16的0.75倍了! 好这里分析为什么容量的大小一定要是2的倍数,
如果容量是15.那15的0.75倍是多少?请自行脑补!
【2】 -这里就是hashMap和HashTable的区别之一,hashMap键可以为空值;
【3】 -这个是通过哈希算法得到键的哈希值(有兴趣的小伙伴可以研究一下hash算法);
接着就是拿得到的哈希值 和容量的大小做与运算(这样得到的值才在容量的大小的范围内),
确定放在Entry数组的哪个位置
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must
be a non-zero power of 2";
return h & (length-1);
}
【4】 -遍历当前Entry[],
判断这个键是否在Entry[] 中已经存在,我们可以看到,首先判断的是键的hash值,
讲道理,对于这种算法,我并不知道,键不一样,hash是否可以一样!
我只能拿jdk的hashCode来参考一下!按照jdk的String的hashCode,
即使是不同的字符串也有可能他们的hashCode也相同;下面我们一起来看一下源码
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
其实上面的实现也就是数学表达式的实现:
s[i]是string的第i个字符,n是String的长度。
举个简单的例子把
- String str = "java";
-
- h = 0
- value.length = 4
-
- val[0] = j
- val[1] = a
- val[2] = v
- val[3] = a
-
- h = 31*0 + j
- = j
-
- h = 31 * (31*0 + j) + a
- = 31 * j + a
-
- h = 31 * (31 * (31*0 + j) + a) + v
- = 31 * (31 * j + a) + v
- = 31 * 31 * j + 31 * a + v
-
- h = 31 * (31 * 31 * j + 31 * a + v) + a
- = 31 * 31 * 31 * a + 31 * 31 * a + 31 * v + a
-
- h = 31 ^ (n-1) * val[0] + 31 ^ (n-2) * val[1] + 31 ^ (n-3) * val[2] + ...+ val[n-1]
我们会注意那个狗血的31这个系数为什么总是在里面乘来乘去?为什么不适用32或者其他数字?
大家都知道,计算机的乘法涉及到移位计算。当一个数乘以2时,就直接拿该数左移一位即可!
选择31原因是因为31是一个素数!
所谓素数:
质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。
在存储数据计算hash地址的时候,我们希望尽量减少有同样的hash地址,所谓“冲突”。
如果使用相同hash地址的数据过多,那么这些数据所组成的hash链就更长,从而降低了查询效率!
所以在选择系数的时候要选择尽量长(31 = 11111[2])的系数并且让乘法尽量不要溢出
(如果选择大于11111的数,很容易溢出)的系数,因为如果计算出来的hash地址越大,所谓的“冲突”就越少,查找起来效率也会提高。
31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化,
使用31的原因可能是为了更好的分配hash地址,并且31只占用5bits!
在java乘法中如果数字相乘过大会导致溢出的问题,从而导致数据的丢失.
而31则是素数(质数)而且不是很长的数字,最终它被选择为相乘的系数的原因不过与此!
得出的结论是
equals()相等的两个对象,hashcode()一定相等;
equals()方法不相等的两个对象,hashcode()有可能相等。
好好好,现在我们回到判断上,后面判断这个键是否是一块内存地址,再判断值是否内容是相同的
既然上面谈了那么多的hashCode废话,那么我们再谈谈String的equals的废话吧!上源码
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String) anObject;
int n = value.length;
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}
把字符传拆成字符数组,然后一个一个比较是否相等!
第【5】步
往Entry[]添加数据了
void addEntry(int hash, K key, V value, int bucketIndex) {
//【5.1】判断当前添加的数量已经超过的threshold(这个值是容量乘以0.75哦)
// 如果超过,马上给Entry[]扩容成现在容量的两倍;
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//【5.2】 添加数据
createEntry(hash, key, value, bucketIndex);
}
【5.2】 添加数据
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
首先取出Entry【】中计算出的位置中是否已经有数据,如果有的话,那么把他放到链表的下一个节点!
也就是说, 新节点一直插入在最前端,新节点始终是单向列表的头节点;
最后找一段程序试试链表的储存
补充,现在各种存储比如redis,以及阿里的云存储等
从根本上说都是key-value!深刻理解一下吧。
代码读不懂画画图唱唱歌吧,啦啦啦。