以JDK1.7源码为例进行分析
(一)Hashing的概念
将字符串转换成固定长度(一般是更短的长度)的数值或索引值的方法,也称为散列法或哈希法。常用于数据库中建索引,或是用于各种加解密算法中。
完成转换功能的函数一般称为哈希函数,哈希函数设计的好坏将直接影响到哈希表的优劣。
(二)哈希表
可高效进行增加、删除、查找等操作的数据结构,不考虑哈希冲突的情况下,仅需要一次定位即可完成,时间复杂度为O(1)。
哈希表的主干是数组,在数组中根据下标查找某个元素,一次定位即可达到,正是利用这种特性,达到高效的操作。
(三)哈希冲突
两个不同元素,通过hashing后,有极小的概率得到相同的数值(实际的存储地址),对这个存储地址进行插入操作时,发现已经被其他元素占用,这就是所谓的哈希冲突,也叫哈希碰撞。
好的哈希函数会尽量保证计算简单和散列地址分布均匀,但也不能保证得到的存储地址绝对没有冲突。
HashMap解决哈希冲突采用的是链地址法,即数组+链表的方式。
(四)原理分析
1、HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。数组是主体,链表是为了解决哈希冲突。如果定位到的数组位置不含链表(Entry的指针指向null),此时操作仅需一次寻址即可;如果定位到的位置包含链表,则遍历链表,通过key对象的equals方法逐一对比查找,此时时间复杂度为O(n)。因此HashMap中出现链表越少,其性能越好。
结构图如下:
Entry代码片断及解析:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;//final
V value;
Entry<K,V> next;//指针(也可以叫引用)
int hash;//key对应的hash值
Entry(int h, K k, V v, Entry<K,V> n) {
……//略,构造方法体
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = 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 Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
}
上面equals方法中, if 判断k1 == k2、v1 == v2这2处,旨在说明“null==null”返回true,在此进行说明,并且我们在平时编码中也应该注意这一点。
(五)几个重要属性(字段)
1、static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默认初始容量,必须是2的次方
2、static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认装载因子,大小为0.75。
3、static final Entry<?,?>[] EMPTY_TABLE = {};
默认初始化的空表Entry
4、transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
HashMap实际存储数据的表,长度必须总是2的幂,默认为空表
5、transient int size;
实际的键值对数量
6、int threshold;
扩容临界值:下一个要调整大小的值(总容量*装载因子),当键值对数量size达到此值时(size >= threshold),对容量进行扩容操作(resize(2 * table.length))
特此说明:
上述对“临界值”的描述看似正确,而实际上并非如此。假设当前容量为8,装载因子0.75,则threshold=6,当size为6时会对HashMap进行扩容吗?经实验证明,不一定会。
查看源码,在put操作时扩容的条件为“(size >= threshold) && (null != table[bucketIndex])”,也就是说还需要同时满足后面条件,那么bucketIndex又是什么呢?直译为“桶的下标”,即下一个存放Entry的桶的位置,这个位置的获取来自方法“indexFor”,如下:
static int indexFor(int h, int length) {//hash值,table的总容量
return h & (length-1);
}
length-1的二进值低位都是1,h & (length-1)的与运算,实质就是h% (length-1),只要hash不相等,理想情况下,需要容量被全部占用时才会扩容。
简而言之,仅当size >= threshold且发生Hash值%(length-1)冲突(或修改已存在的值或)时,才会进行扩容。
关于扩容的验证,请参见文章:https://blog.csdn.net/u010188178/article/details/86527792
7、final float loadFactor;
装载因子,当使用容量达到总容量*装载因子容量时,可能会对集合进行扩容操作;如果实例化时不指定装载因子的大小,其初始化为默认大小0.75。
(六)构造方法
1、直接构造(指定容量+装载因子)
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: " +
loadFactor);
this.loadFactor = loadFactor;//装载因子赋值
threshold = initialCapacity;//扩容临界值赋值
init();
}
此处threshold赋值为传入的初始值,比如传入5,初始化时,threshold=5,而在第一次put操作时,通过5计算HashMap的初始容量应该为8(2的冥且>=5),再通过装载因子(默认0.75)计算出扩容临界值threshold=6。
并且实例化时并没有为数组table分配内存空间,而是在put第一个元素时才构建table数组。
2、直接构造(指定容量)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3、无参构造
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
4、通过实现Map接口的对象构造
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
1、数据结构
JDK1.7使用数组+链表的数据结构,而1.8使用数组+链表+红黑树。
如果插入key的hashcode相同,使用链表方式解决冲突,当链表长度达到8个(默认设置的阈值)时,调用treeifyBin函数,将链表转换为红黑树。红黑树的时间复杂度为O(log n),即put/get最坏时间复杂度为O(log n)。
2、数据存储机制
发生hash冲突时,JDK1.7采用链地址法+头插法,而1.8采用链地址法+尾插法+红黑树。
头插入法插入效率较高,但容易出现逆序且环形链表死循环问题,尾插法可避免此问题。
1、如果使用的HashMap容量可能会很大,实例化时设置初始容量,比如new HashMap(2048)。
这样建议的理由无非就是说,当容器持续增长时,可能会导致其频繁扩容,影响性能。而实际生产中是否有这样的必要呢?先做个实验。
JDK1.7环境下,插入元素数量16777216,其对应默认临界值为12582912
(1)设置初始值的情况
public static void testHashMap(){
//插入元素数量16777216,其对应默认临界值为12582912
int size = 16777216;
long start = System.currentTimeMillis();
Map<Integer, Integer> map2 = new HashMap<>(12582912);
for(int i=0; i<size; i++){
map2.put(i, i);
}
long end = System.currentTimeMillis();
System.out.println("设置初始值耗时:"+(end-start));
}
以上情况需要扩容一次,运行时长:18270(多次运行,时长18000ms左右)
(2)不设置初始值的情况
public static void testHashMap1(){
//插入元素数量16777216,其对应默认临界值为12582912
int size = 16777216;
long start = System.currentTimeMillis();
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<size; i++){
map.put(i, i);
}
long end = System.currentTimeMillis();
System.out.println("不设置初始值耗时:"+(end-start));
}
以上情况需要扩容很多次,运行时长:14057(多次运行,时长在此值左右)
现在将JDK环境修改为1.8,再次测试,2次运行结果分别如下:
设置初始值耗时:20866
不设置初始值耗时:17707
因此:
** 在JDK1.7、1.8环境下,对较大容量HashMap设置初始值(实质上为扩容临界值),并不会对实际效率有所提高。**
2、我在查看同事的源码时经常看到new HashMap(4),**new HashMap(6)**之类的写法。
我肯定他们的初衷是在知道容器存放总量的情况下,设置初始容量以减少内存消耗。但这里需要注意的是:
** 入参并不是容器的初始容量,而是扩容临界值。在实例化HashMap时,并不会初始化其容量,此时默认容量为0;在执行第一次put操作时,默认装载因子为0.75的情况下,其初始容量由传入的参数除以0.75,得到的值为N,再计算2的冥得到Y,保证Y>=N且Y最接近N,此时的Y才是HashMap的初始容量;用Y乘以0.75得到真实扩容临界值。**
1、HashMap可以接受null键值和值,而Hashtable则不能
2、HashMap是非synchronized
3、String、Integer这样的包装类适合作为key。它们由final修饰,具有不可变性;内部重写了equals()、hashCode()方法 ,具有计算准确性,有效减少了发生Hash碰撞的机率。
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/u010188178/article/details/86534944
内容来源于网络,如有侵权,请联系作者删除!