首先我们来看看HashMap的底层源码
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the 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();
}
我们可以看到底层其实就是一个数组,而且是一个Entry类型的数组,我们来看看Entry类的源码
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
final int hash;
Entry<K,V> next;
它是一个静态内部类,成员变量有我们放进去的key,value以及指向下一个Entry对象的引用当我们调用put方法时
public V put(K key, V value) {
K k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
if (e.hash == hash && eq(k, e.key)) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, k, value, i);
return null;
}
它首先根据key值生成一个hash值,并通过以下方法
static int indexFor(int h, int length) {
return h & (length-1);
}
得到数组的存放位置,如果该位置已经有对象存在了,就顺着此对象的链开始寻找,如果e.hash == hash && eq(k, e.key)返回为真就用新的对象替换旧的对象并将旧的对象返回,如果都不成功,表示在链上不存在,这个时候就直接添加到数组,同时将添加的这个Entry的next指向被替换的那个Entry对象,实现如下
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
总的来说HashMap底层是用数组来实现,而每一个数组元素又可以当成一个链表的头,这样做是为了提高查询的效率,使得查找时间不会随Map的大小而改变
分享到:
相关推荐
HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别。HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)...
HashMap底层实现原理共6页.pdf.zip
02-JDK1.7中的HashMap底层实现分析.mp4
03-JDK1.8中的HashMap底层实现分析.mp4
java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法
Java集合,HashMap底层实现和原理(1.7数组+链表与1.8+的数组+链表+红黑树) 数组和链表.pdf
HashMap底层原理.md
HashMap底层原理
08-HashMap底层实现原理总结与展望.mp4
构造 首先来看下hashMap的构造方法 HashMap hashMap = new HashMap();...直接来看下hashMap的两个参数构造方法,在默认值初始化的时候,tableSizeFor控制着hashMap size的大小,具体的实现下看: public HashMap
老规矩先上框架图: 代码部分: 1. 测试ArrayList类的方法: package RongQI.Collection; import java.util.ArrayList; import java.util.Collection; import java.util.List;... * 测试Collection接口中的方法 ...
hashmap的底层及源码解析,很适合大家的学习,不要积分。
源码解析jdk8.0集合:HashMap的底层实现原理.pdf
源码解析jdk7.0集合(3):HashMap的底层实现原理.pdf
HashMap内部采用数组和链表的方式存储数据,每个元素都包含键值对,通过hash函数将键映射到数组的索引位置,实现高效的查找和插入。 HashMap的性能优化策略。 HashMap在性能优化方面采取多种策略,如扩容机制、负载...
主要介绍了对HashMap原理的理解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
说起HashMap,我们可以先从底层实现说起,HashMap是通过hash算法,基于数组、链表和红黑树实现的,hash算法是一种思想,只要符合该思想的算法都是hash算法,其核心就是给定一个key,通过hash可以对应一个h(key),举...
首先会将传入的可以、做hash运算计算出...由于数组的长度有限,所以难免出现不同放入key通过运算得到的index相同,这种情况可以利用链表来解决,HashMap会在table[index]出形成链表,采用头插法将数据插入链表中