社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
首先关于本篇文章的阐述,既非笔者完全原创,更非照搬源抄,而是在学习和借鉴的基础上,添加了自己的理解。
hashMap是咱们项目开发过程中,经常使用到的数据结构,但是关于hashMap的底层,你又知道多少呢?
大家都知道,hashMap是一个用于存储(key,value)型数据的键值对集合。每一个键值对(key,value)也叫做Entry。每个键值对(Entry)分散存储在一个数组(HashMap的主干)当中。hashMap数据当中的每一个元素的初始值都是null。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。它不保证映射的顺序,特别是不保证HashMap里键值对的顺序恒久不变。
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
从上面的代码片段,我们不难发现,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。Entry就是数组中的元素,每个 Map.Entry 其实就是一个key-value对,它持有一个指向下一个元素的引用,这就构成了链表。
public V put(K key, V value) {
// HashMap允许存放null键和null值。
// 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
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,通过循环不断遍历 e 元素的下一个元素。
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 = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果i索引处的Entry为null,表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;
}
从上面的源代码中可以看出:当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标), 但是当插入的Entry越来越多的时候,再完美的Hash函数也难免会出现下表索引冲突的情况,如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,通过链表来解决下标冲突,主要是因为,HashMap数组中的每一个元素不仅仅是一个Entry对象,也是一个链表的头节点,每一个Entry对象通过上一个例子中的Next指针,指向它的下一个Entry节点。新加入的放在链头,最先加入的放在链尾(这种插入方法,也被称为“头插法”,至于为什么不是链表“尾插法”,主要是考虑到查询效率的问题,HashMap创建者认为,后插入的Entry被查询的可能性更大)。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。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;
}
从上面的源代码中可以看出:从HashMap中get元素时,首先计算key的hashCode,HashMap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。找到数组中对应位置的某一元素后,然后通过key的equals方法在对应位置的链表中找到需要的元素。static int indexFor(int h, int length) {
return h & (length-1);
}
当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,这是一个常用的操作,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。
那么HashMap什么时候进行扩容呢?当HashMap中的元素个数超过数组大小loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过160.75=12的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
HashMap 包含如下几个构造器:
1、HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
2、ashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。
3、HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。
HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数,它们是初始容量initialCapacity和负载因子loadFactor。
负载因子loadFactor衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
方式二:效率低,不推荐使用Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!