知识的领域是无限的,我们的学习也是无限期的。这篇文章主要讲述Android面试之HashMap的实现原理相关的知识,希望能为你提供帮助。
1、HashMap与HashTable的区别
- HashMap允许key和value为null;
- HashMap是非同步的,线程不安全,也可以通过Collections.synchronizedMap()方法来得到一个同步的HashMap
- HashMap存取速度更快,效率高
- HashMap去掉了HashTable中的contains方法,加上了containsValue和containsKey方法
一句话理解HashMap:HashMap就是Hash表的Map实现。 Hash表就是Hash数组,Map实现是指实现了Map接口。
文章图片
- HashMap的数据结构
HashMap的底层是基于数组和链表实现的,存储速度快的原因是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。如果存储的对象对多了,就有可能不同的对象所算出来的hash值是相同的,这就出现了所谓的hash冲突。解决hash冲突的方法有很多,HashMap底层是通过链表来解决hash冲突的。
static class Entry< K,V> implements Map.Entry< K,V> {
final K key;
V value;
Entry< K,V> next;
final int hash;
Entry(int h, K k, V v, Entry< K,V> n) {
value = https://www.songbingjia.com/android/v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = https://www.songbingjia.com/android/value;
value = https://www.songbingjia.com/android/newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null & & k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null & & v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value=https://www.songbingjia.com/android/=null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
void recordAccess(HashMap< K,V> m) {
}
void recordRemoval(HashMap< K,V> m) {
}
}
HashMap其实就是一个Entry数组,Entry对象中包含了键和值,其中next也是一个Entry对象,它就是用来处理hash冲突的,形成一个链表。
2. HashMap的几个变量
transient Entry[] table; //存储Entry的数组
transient int size; //存放entry的个数
int threshold; //下限,临界值,数组长度超过这个值会扩容,threshold = loadFactor*容量;
final float loadFactory;//加载因子,加载因子越大表示当前数组填满的元素越多,空间利用率高,不方便查询;加载因子越小,表示填满元素越少,空间利用率低,方便速度快。默认值是0.75;
transient int modCount;//被修改的次数
3. HashMap的构造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY; if (loadFactor < = 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " +
【Android面试之HashMap的实现原理】loadFactor); // Find a power of 2 > = initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity < < = 1; this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
允许我们自己指定初始容量和加载因子
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
只指定初始容量,加载因子使用默认的0.75;
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
初始容量和加载因子全部使用默认的值,默认初始的加载容量是16,加载因子是0.75;
4. 存储数据put方法
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry< K,V> e = table[i]; e != null; e = e.next) {
Object k; if (e.hash == hash & & ((k = e.key) == key || key.equals(k))) {
V oldValue = https://www.songbingjia.com/android/e.value;
e.value = https://www.songbingjia.com/android/value;
e.recordAccess(this); return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); return null;
}
可以看出,HashMap存放数据的时候,会先拿到key的hashCode值,对其进行hash运算,得到具体的hash值,然后根据hash值查找存放的位置,找到存放的位置后,然后遍历table数组找到对应位置的entry,如果当前的key已经存在,且对比entry的hash值和key相同的话,那么就更新value值;否则就将key和value值加到数组中;
这里需要注意:判断是否2个Entry相同,需要从2方面判断:1、2个Entry的key必须相同(k = e.key||key.equals(k));2、2个Entry的hashCode,也就是hash值必须相同(这里说的hash是经过hash(hashCode)换算后的值);上述2个条件都满足的话,才可以认定当前Entry已经存在,新的Entry才会替换旧的Entry。
下面给出put过程中,涉及到的2个方法
- 根据hashCode求hash码的实现
static int hash(int h) {
h ^= (h > > > 20) ^ (h > > > 12); return h ^ (h > > > 7) ^ (h > > > 4);
}
- 根据hash码求存储在数组中的索引
static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值2 return h & (length-1); //这里不能随便算取,用hash& (length-1)是有原因的,这样可以确保算出来的索引是在数组大小范围内,不会超出3 }
这里有些同学会好奇,为什么索引值是h & (length-1)? 其实,这里面的故事还是挺多的。 一般对哈希表求散列我们会使用hash值对length取模,HashTable就是这样实现的,这种方法可以保证元素在哈希表中散列均匀,但取模会用到除法运算,效率非常低,HashMap是对HashTable进行改进后的实现,为了提高效率,使用h& (length-1)取代除法运算,在保证散列均匀的基础上还保持了效率的提升。
5. resize方法
用于重新扩大缩小数组的大小
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
其实就是新建一个大的数组,把原来的数据重新添加进去。什么时候才会触发resize方法呢?当当前元素的数量达到数组总size的loadFactor(默认0.75)时候,会调用resize方法,将数组扩大为原来大小的2倍;
6. HashMap的get方法
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry< K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash & & ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
可以看出,首先拿到key的hashcode,求出hash码,根据hash码找到索引的位置,然后去数组中获取对应索引的元素,如果key的hash相同,key相同的话,那么这就是我们要找的entry,把entry的值返回出去就Ok了。
如果大家觉得好,大家转载的同时,也点点文章最下面“androidDeveloper”的订阅按钮,关注“AndroidDeveloper”
推荐阅读
- 安卓进程
- android 通知(android 8.0可用)
- android 一步一步教你集成tinker(热修复)
- call和apply;this;闭包
- 社群系统ThinkSNS+第4阶段安卓端更新播报
- NetApp配置NetApp控制器与Linux NTP服务器同步
- Android Studio无法打印Logout日志
- github版本控制 android studio
- (转 )Android那些高逼格的写法InvocationHandler与代理模式