BAT面试必问;
关于hashmap,你知道多少?你知道hashmap的工作原理吗?
1.该问题很有深度
2.能答出多少决定岗位和薪资.
3.问题的方式多种多样
一.首先我们了解下HashMap是什么
HashMap是Java常用的用来储存键值对的数据结构,它是线程不安全的,可以储存null键值,这些大家经常用,也都知道,接下来根据源码分析一下HashMap的实现。
1、实现原理
HashMap采用数组散列+链表的方式来储存键值对,键值对的对象实现如下:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
通过一个Entry的数组table就实现了多个对象的保存,使用哈希值和键值解决了在插入和查找时的冲突。
2、put方法,写入键值对
public V put(K key, V value){
//如果 key 为 null,调用 putForNullKey 方法写入null键的值
if (key == null){
return putForNullKey(value);
}
//根据 key 的 keyCode 计算 Hash 值
int hash = hash(key.hashCode());
//查找hash值在table中的索引
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null,通过循环不断遍历链表查找是否在链表中有相同key的Entry
for (Entry<K,V> e = tablei; e != null; e = e.next) {
Object k;
//找到与插入的值的key和hash相同的Entry
if (e.hash == hash && ((k = e.key) == key|| key.equals(k)){
//key值相同时直接替换value值,跳出函数
V oldValue = e.value;
e.value = value; e.recordAccess(this); return oldValue; } }
// 如果 i 索引处的 Entry 为 null 或者key的hash值相同而key不同 ,则需要新增Entry
modCount++;
// 将 key、value 添加到 i 索引处
addEntry(hash, key, value, i);
return null;
}
在put方法中解决hash碰撞的方式很清楚,即当两个entry的hash值相同时,需要对key值是否相同进行判断,只有key和hash都相同,才能进行修改,否则认为不是同一个entry。
3.addEntry的实现
代码:
void addEntry(int hash, K key, V value, int bucketIndex) { // 获取指定 bucketIndex 索引处的 Entry
Entry<K,V> e = tablebucketIndex;
tablebucketIndex = new Entry<K,V>(hash, key, value, e); // 如果 Map 中的 key-value 对的数量超过了极限
if (size++ >= threshold)
resize(2 table.length);
}
在创建新Entry时如果table的bucketIndex处有元素的话,创建时需要将entry的next设置为原先存储的元素。
二,HashMap工作原理
以下为目录,有需要完整进阶视频可以加Android进阶群;701740775免费获取
1.目录
2.顺序表与链表
3.Hsh表
4.Hash源码
5.碰撞
需要完整进阶视频详解可以加Android进阶群;701740775免费获取!
附录Android高级技术大纲和进阶视频;