查询 | 新增删除 | |
---|---|---|
单向链表 | 头O(1),其他O(n) | 头O(1),其他O(n) |
双向链表 | 头尾O(1),其他O(n),给定节点O(1) | 头尾O(1),其他O(n),给定节点O(1) |
在HashMap中的最重要的一个数据结构就是散列表,在散列表中又使用到了红黑树和链表。
(散列表的概念、散列函数、散列冲突、拉链法)
1)散列表(Hash Table):又名哈希表/Hash表,是根据键(Key)直接访问在内存存储位置值(Value)的数据结构,它是由数组演化而来的,利用了数组支持按照下标进行随机访问数据的特性。
假设有100个人参加马拉松,不采用1-100的自然数对选手进行编号,编号有一定的规则比如:2023ZHBJ001,其中2023代表年份,ZH代表中国,BJ代表北京,001代表原来的编号,那此时的编号2023ZHBJ001不能直接作为数组的下标,此时应该如何实现呢?
2)散列冲突:也叫哈希冲突、哈希碰撞,指多个key映射到同一个数组下标位置
3)散列冲突-链表法(拉链):在散列表中,数组的每个下标位置我们可以称之为桶(bucket)或者槽(slot),每个桶(槽)会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。时间复杂度如下
我们分析源码 主要从以下几个方面来考虑:成员变量、构造函数、关键方法。
//默认的初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大数量,该数组最大值为2^30。
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子。如果构造的时候不传则为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//一个位置里存放的节点转化成树的阈值,也就是8,比如数组里有一个node,这个node链表的长度达到该值才会转化为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//当一个反树化的阈值,当这个node长度减少到该值就会从树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
//满足节点变成树的另一个条件,就是存放node的数组长度要达到64
static final int MIN_TREEIFY_CAPACITY = 64;
//具体存放数据的数组!!!
transient Node<K,V>[] table; //见下
//entrySet,一个存放k-v缓冲区
transient Set<Map.Entry<K,V>> entrySet;
//size是指hashMap中存放了多少个键值对
transient int size;
//对map的修改次数
transient int modCount;
//The next size value at which to resize (capacity * load factor).
int threshold;
//加载因子
final float loadFactor;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
注意HashMap中的 transient Node<K,V>[] table
,该table是真正存放数据的容器,该容器由一个又一个node组成,而node有三种实现,所以hashMap中存放的node的形式既可以是Node也可以是TreeNode。可见HashMap是基于数组、链表或者树实现的。
【HashMap 的定义是一个散列表,这是一种支持快速查找元素的数据结构,那么其背后就必然会使用到数组随机访问的特点。因此,HashMap 的一维结构就是一个数组,数组元素是一个包含 Key、Value 和 hashcode 的 Entry 节点。当我们需要访问集合元素时,其实就是先通过 key 计算 hashcode,再将 hashCode 对数组长度取余得到数组下标,最后通过下标去数组中找到对应的 Value】
DEFAULT_INITIAL_CAPACITY 默认的初始容量
DEFAULT_LOAD_FACTOR 默认的加载因子
扩容阈值 == 数组容量 * 加载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//当容量大于2^31就取最大值1<<31;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//当前数组table的大小,一定是2的幂次方
// tableSizeFor保证了数组一定是2的幂次方,是大于initialCapacity最接近的值。
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
HashMap是懒惰加载,在创建对象时并没有初始化数组;在无参的构造函数中,设置了默认的加载因子是0.75。
构造方法一共重载了四个,主要初始化了三个参数:
我们最常使用的是无参构造,在这个构造方法里面仅仅设置了加载因子为默认值,其他两个参数会在resize方法里面进行初始化,在这里知道这个结论就可以了,下面会在源码里面进行分析; 另外一个带有两个参数的构造方法,里面对初始容量和阈值进行了初始化,对阈值的初始化方法为 tableSizeFor(int cap),看一下源码:
//找到大于或等于 cap 的最小2的幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
tableSizeFor()方法保证了数组大小一定是2的幂次方,是如何实现的呢? —— 该方法将一个二进制数第一位1后边的数字全部变成1,然后再加1,这样这个二进制数就一定是100…这样的形式。此处实现在ArrayDeque的实现中也用到了类似的方法来保证数组长度一定是2的幂次方。
对于无符号右移运算符不了解的,可以看一下这篇文章了解一下,下面偷一张图 以10为例进行分析:
另外,需要注意一下的是,第一步 int n = cap - 1; 这个操作,执行这个操作的主要原因是为了防止在cap已经是2的n次幂的情况下,经过运算后得到的结果是cap的二倍的结果,例如如果n为l6,经过一系列运算之后,得到的结果是0001 1111,此时最后一步n+1 执行之后,就会返回32,有兴趣的可以自己进行尝试
在hashMap源码中,put方法逻辑是最为复杂的,接下来先看一下源码:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//如果table尚未初始化,则此处进行初始化数组,并赋值初始容量,重新计算阈值
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//通过hash找到下标,如果hash值指定的位置数据为空,则直接将数据存放进去。这儿p赋值成了table该位置的node值
tab[i] = newNode(hash, key, value, null);
else {
//如果通过hash找到的位置有数据,发生碰撞
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果需要插入的key和当前hash值指定下标的key一样,先将p赋值给e
e = p;
else if (p instanceof TreeNode)
//如果此时桶中数据类型为 treeNode,使用红黑树进行插入,调用putTreeVal方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果此时桶中数据类型为链表,遍历
// 进行循环。注意e = p.next这个一直将下一节点赋值给e,直到尾部,注意开头是++binCount
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//如果链表中没有最新插入的节点,将新放入的数据放到链表的末尾
p.next = newNode(hash, key, value, null);
//如果链表过长,达到树化阈值,将链表转化成红黑树,树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果链表中有新插入的节点位置数据不为空,则此时e 赋值为节点的值,跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//经过上面的循环后,如果e不为空,则说明上面插入的值已经存在于当前的hashMap中,那么更新指定位置的键值对
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果此时hashMap size大于阈值,则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
从代码来看,put方法分为三种情况
首先分析table尚未初始化的情况:
n = (tab = resize()).length; //table尚未初始化的时候,会调用resize()方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//1.table已经初始化,且容量 > 0
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//如果旧的容量已近达到最大值,则不再扩容,阈值直接设置为最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果旧的容量不小于默认的初始容量,则进行扩容,容量扩张为原来的二倍
newThr = oldThr << 1; // double threshold
}
//2.阈值大于0 threshold 使用 threshold 变量暂时保存 initialCapacity 参数的值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//3.threshold 和 table 皆未初始化情况,此处即为首次进行初始化
//也就在此处解释了构造方法中没有对threshold 和 初始容量进行赋值的问题
else { // zero initial threshold signifies using defaults
//如果阈值为零,表示使用默认的初始化值。这种情况在调用无参构造的时候会出现,此时使用默认的容量和阈值
newCap = DEFAULT_INITIAL_CAPACITY;
//此处阈值即为 threshold=initialCapacity*loadFactor
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr 为 0 时,按阈值计算公式进行计算,容量*负载因子
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新阈值
threshold = newThr;
//更新数组桶
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果之前的数组桶里面已经存在数据,由于table容量发生变化,hash值也会发生变化,需要重新计算下标
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果指定下标下有数据
if ((e = oldTab[j]) != null) {
//1)将指定下标数据置空
oldTab[j] = null;
//2)指定下标只有一个数据
if (e.next == null)
//直接将数据存放到新计算的hash值下标下
newTab[e.hash & (newCap - 1)] = e;
//3)如果是TreeNode数据结构
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//4)对于链表,数据结构
else { // preserve order
//如果是链表,重新计算hash值,根据新的下标重新分组
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize方法逻辑比较复杂,需要静下心来一步步的分析,但是总的下来,分为以下几步:
put方法分析完成之后,剩下的就很简单了,先看一下源码:
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//1)根据hash算法找到对应位置的第一个数据,如果是指定的key,则直接返回。
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//如果该节点为红黑树,则通过树进行查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果该节点是链表,则遍历查找到数据。当链表后续为null 退出循环
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get方法相对于put来说,逻辑简单很多:
在这个方法里面,需要注意的有两个地方:hash(key)和hash的取模运算 (n - 1) & hash。
hash(key)源码
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这段代码叫做扰动函数,也是hashMap中的hash运算,主要分为下面几步:
取模运算 (n - 1) & hash
在hashMap的代码中,在很多地方都会看到类似的代码:
first = tab[(n - 1) & hash])
hash算法中,为了使元素分布的更加均匀,很多都会使用取模运算,在hashMap中并没有使用hash%n这样进行取模运算,而是使用(n - 1) & hash进行代替,原因是在计算机中,&的效率要远高于%;需要注意的是,只有容量为2的n次幂的时候,(n - 1) & hash 才能等效hash%n,这也是hashMap 初始化初始容量时,无论传入任何值,都会通过tableSizeFor(int cap) 方法转化成2的n次幂的原因,这种巧妙的设计真的很令人惊叹; 至于为什么只有2的n次幂才能这样进行取模运算,这里就不再详细叙述了,有兴趣的可以看一下一位大佬写的文章:由HashMap哈希算法引出的求余%和与运算&转换问题
了解完get方法之后,我们再最后了解一下remove方法:
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//根据key和key的hash值,查找到对应的元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//如果查找到了元素node,移除即可
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果是TreeNode,通过树进行移除
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//如果是第一个节点,移除第一个节点,将index下标的位置指向第二个节点
else if (node == p)
tab[index] = node.next;
else
//如果不是链表的第一个节点,则移除该节点
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
从源码可以看出来,通过key找到需要移除的元素操作过程和get方法几乎一致,最后在查找到key对应的节点之后,根据节点的位置和类型,进行相应的移除操作就完成了,过程非常简单。
HashMap的数据结构: 底层使用hash表数据结构,即数组和链表或红黑树。jdk1.7使用的是 数组+链表,jdk1.8 当链表长度大于阈值(默认为8)并且数组长度达到64时 会转换为红黑树
初始容量:HashMap 的初始容量是 0,这是一种懒加载机制,直到第一次 put 操作才会初始化数组大小,默认大小是 16。
扩容逻辑:
HashMap 使用的是拉链法来解决散列冲突,扩容并不是必须的,但是不扩容的话会造成拉链的长度越来越长,导致散列表的时间复杂度会倾向于 O(n) 而不是 O(1)。
HashMap 扩容的触发时机出现在元素个数超过阈值(容量 * loadFactor)的时候时,会将集合的一维数组扩大一倍,然后重新计算每个元素的位置。
注意:链表的长度大于8 且 数组长度大于64转换为红黑树
面试官追问:HashMap的jdk1.7和jdk1.8有什么区别
这是为了尽量将集合元素均摊到数组的不同位置上。
jdk7的的数据结构是:数组+链表
在数组进行扩容的时候,因为链表是头插法,在进行数据迁移的过程中,有可能导致死循环【下面代码是HashMap的扩容操作,重新定位每个桶的下标,并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转,这也是形成死循环的关键点】
参考回答:
在jdk1.7的hashmap中在数组进行扩容的时候,因为链表是头插法,在进行数据迁移的过程中,有可能导致死循环。
比如说,现在有两个线程
线程一:读取到当前的hashmap数据,数据中一个链表,在准备扩容时,线程二介入
线程二:也读取hashmap,直接进行扩容。因为是头插法,链表的顺序会进行颠倒过来。比如原来的顺序是AB,扩容后的顺序是BA,线程二执行结束。
线程一:继续执行的时候就会出现死循环的问题。
线程一先将A移入新的链表,再将B插入到链头,由于另外一个线程的原因,B的next指向了A,所以B->A->B,形成循环。当然,JDK 8 将扩容算法做了调整,不再将元素加入链表头(而是保持与扩容前一样的顺序),尾插法,就避免了jdk7中死循环的问题。
1、不可变类 String 可以避免修改后无法定位键值对: 假设 String 是可变类,当我们在 HashMap 中构建起一个以 String 为 Key 的键值对时,此时对 String 进行修改,那么通过修改后的 String 是无法匹配到刚才构建过的键值对的,因为修改后的 hashCode 可能是变化的。而不可变类可以规避这个问题。
2、String 能够满足 Java 对于 hashCode() 和 equals() 的通用约定: 既两个对象 equals() 相同,则 hashCode() 相同,如果 hashCode() 相同,则 equals() 不一定相同。这个约定是为了避免两个 equals() 相同的 Key 在 HashMap 中存储两个独立的键值对,引起矛盾。
Hashtable和HashMap都是 基于hash表实现的K-V结构的集合,Hashtable是jdk1.0引入的一个线程安全的集合类,内部使用数组+链表的形式来实现
从功能特性的角度来说
1、Hashtable是线程安全的(HashTable 对每个方法都增加了 synchronized),而HashMap不是
2、HashMap的性能要比Hashtable更好,因为Hashtable采用了全局同步锁来保证安全性,对性能影响较大
从内部实现的角度来说
1)Hashtable使用数组加链表,HashMap采用了数组+链表+红黑树
2)HashMap初始容量是16,Hashtable初始容量是11
3)HashMap可以使用null作为key;而Hashtable不允许 null 作为 Key,会抛出NullPointerException
异常
他们两个的key的散列算法不同:Hashtable直接是使用key的hashcode对数组长度取模;而HashMap对key的hashcode做了二次散列,从而避免key的分布不均匀影响到查询性能
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。