摘要：经过上述讨论，我们发现，哈希查找的时间复杂度最小没有冲突是二是什么首先是中的一个接口。在中，有很多类实现了接口，就是其中的一个三是什么是一个实现了接口的基于哈希表的类。
我们要想知道HashMap是什么就先要了解Hash和Map是什么
一、Hash是什么
① 哈希查找是一种数据结构中用于 查找 的算法，相比于其他查找算法，他的时间复杂度更
低，所以在实际应用中大量采取了哈希表的方式，Hashmap就是java内置的哈希查找的方法
② 哈希函数的基本思想： 将记录的存储地址和关键字之间建立一个确定的对应关系。这样，当想查找某条记录时，我们根据记录的关键字就可以得到它的存储地址，进而快速判断这条记录是否存在，存储在哪里。
③负载因子：负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。hashmap默认负载因子为0.75，一般情况下我们是无需修改的。
④ 哈希函数的缺陷+改进方式： 在哈希存储中，不同的关键字可能映射到了相同的地址，这就叫产生冲突，我们必须相处冲突处理的方法。当然，前辈们已经相处了各种各样的方法，我在这里先不做深究。
⑤ 经过上述讨论，我们发现，哈希查找的时间复杂度最小（没有冲突）是O(1)
二、Map是什么
首先Map是java中的一个接口。它是java中的一种重要的数据结构。
Map是从键(关键字)到值(记录)的映射,键不允许重复,每个键最多能映射一个值。
在java中，有很多类实现了Map接口，HashMap就是其中的一个
三、Hashmap是什么
HashMap是一个实现了Map接口的基于哈希表的类 。
也就是说，HashMap既有map的键值对特点，也有哈希表的特点
简单点说，利用HashMap类：
查找时，给出一个关键字key，我们可以根据hash算法计算出key-value的存储位置然后取出value
存储时，我们根据哈希算法计算出该键值对应该存储的位置，将其存进去。
也就是说，当没有冲突时，HashMap存取的时间复杂度为O(1)
这是HashMap类的部分代码(部分数据域和构造函数)
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable {
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量
static final int MAXIMUM_CAPACITY = 1 << 30; //HashMap的最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认负载因子0.75
static final int TREEIFY_THRESHOLD = 8; //当某条链表中元素的个数大于8时//将转变为红黑树
transient Node[] table; // table数组，每一个元素都是一个Node对象，接下来会介绍Node是什么
transient Set> entrySet;
transient int size; //记录哈希表中的键值对个数
int threshold; //阈值，即当table中元素个数大于这个值就要resize()
final float loadFactor; //加载因子
HashMap有四种构造函数
①第一种 允许用户自己决定初始容量和加载因子，但这个初始容量不一定是HashMap真正的初始容量，下文会对此进行解释
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)//初始容量不可以小于0
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;//不可以大于最大容量
if (loadFactor <= 0 ||Float.isNaN(loadFactor))//加载因子不可以小于0
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
在构造函数中，我们可以看到，阈值利用tableSizeFor进行了计算，而此时的阈值并不是真正的阈值，是数组的容量，我们也会发现其实在构造函数中并没有给table分配内存，这是因为在插入键值对时，put函数会判断table是否为null，如果是那么用resize()函数为其分配空间并计算真正的阈值
其他三种构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
}
【小贴士】
1.AbstractMap抽象类是什么？
AbstractMap抽象类实现了Map接口的大部分方法，让HashMap继承它减少了实现Map接口的工作量。那它为什么是抽象类呢，因为它有唯一的一个抽象方法
Public abstract Set> entrySet();
当然在HashMap中有很多方法对AbstractMap的方法进行了覆盖
下一节：HashMap的数据结构
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/69987.html
