HashMap的数据结构和底层原理以及在JDK1.6、1.7和JDK8中的演变差异
这里是一篇关于HashMap的数据结构、底层原理和代码演变的技术博客:
HashMap的数据结构和原理
HashMap的数据结构采用“链表散列”结构,即一个链表和一个数组,数组称为hash table,链表成为链表数组。HashMap通过key的hashCode来计算index,然后将key-value对存放在hash table的对应位置。如果出现hash冲突,就将数据存放在链表中。HashMap主要由Node[] table、size和loadFactor三个字段组成。
- Node[] table:数组,默认大小为16,扩容时大小一般为原来的2倍。
- size:HashMap中键值对的数量。
- loadFactor:负载因子,默认为0.75。扩容条件是size大于loadFactor和table的长度的乘积。
获取数据的步骤:
- 计算key的hashCode,然后通过hashCode映射到table数组的index。
- 如果table的index位置没有数据,直接添加。
- 如果table的index位置有数据,查看key是equals()。如果equals,则覆盖旧值;如果不equals,进行加链表或树化操作。如果链表长度超过8,则转换为红黑树。
- 添加后,检查是否需要扩容。如果size超过loadFactor*table.length,进行扩容操作。扩容操作是创建一个新的table,新table的大小为旧table的2倍。
JDK1.6、1.7和1.8中的HashMap源码演变
JDK1.6
JDK1.6中的HashMap是非线程安全的,扩容使用synchronized来锁定整个table。
代码语言：javascript复制public V put(K key, V value) {
// 扩容
if (table == EMPTY_TABLE) {
inflateTable(threshold);
} else if (size >= threshold) {
resize(2 * table.length);
}
// 如果key为null,存储在table[0]中
if (key == null) {
return putForNullKey(value);
}
// 计算key的hash值
int hash = hash(key);
int i = indexFor(hash, table.length);
// 进行拉链操作
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果key存在,则覆盖旧值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// 添加新Entry
modCount ;
addEntry(hash, key, value, i);
return null;
}JDK1.7
JDK1.7中的HashMap是非线程安全的,采用“链表 红黑树”的结构。当链表长度超过8时会将链表转换为红黑树。扩容时使用synchronized锁定table[0]和table[table.length-1]。
代码语言：javascript复制public V put(K key, V value) {
// 扩容
if (table == EMPTY_TABLE)
inflateTable(threshold);
// 如果key为null,存储在table[0]中
if (key == null)
return putForNullKey(value);
int hash = hash(key);
// 找到对应的桶
int i = indexFor(hash, table.length); // 先找出是否已经存在该key,如果存在则更新值并返回
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
if (e.hash == hash && eq(key, e.key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
} // 如果不存在,添加到链表尾部或树中
modCount ;
addEntry(hash, key, value, i); // 确定是否需要扩容
if (size >= threshold)
resize(2 * table.length); return null;
}JDK1.8
JDK1.8中HashMap是非线程安全的,默认采用"链表 红黑树"的结构,当链表长度超过8时会将链表转换为红黑树。
JDK1.8对扩容做了优化,不再锁定整个table,而是采用"synchronized CAS"的方式来控制并发度。同时引入了红黑树,减少了链表过长的情况。
代码语言：javascript复制final V putVal(K key, V value, boolean onlyIfAbsent) {
// 或获取 key 的 hash 值
int hash = spread(key.hashCode());
// 找到对应桶的索引
int i = indexFor(hash, table.length);
// 链表或红黑树的节点
Node<K,V> p;
boolean newEntry = true;
// 如果桶中第一个节点为 TreeNode,则为红黑树结构
if ((p = tab[i]) == null)
// CAS 控制并发,初始化首节点
tab[i] = newNode(hash, key, value, null);
else {
K k;
// 如果键 hash 值和节点 hash 值相等,并且键 equals 节点键,则更新节点键值对
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 更新节点值
p.val = value;
else {
// 判断是否是红黑树
if (p instanceof TreeNode)
// 调用红黑树插入方法插入新节点
((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 若为链表,则插入链表尾部
for (int binCount = 0; ; binCount) {
// 插入新节点到链表尾部
if (newEntry && binCount >= TREEIFY_THRESHOLD - 1)
// 链表长度达 TREEIFY_THRESHOLD 则转化为红黑树
treeifyBin(tab, hash);
// 遍历至链表尾部,插入新节点
if (p.next == null) {
p.next = newNode(hash, key, value, null);
break;
}
p = p.next;
}
}
}
}
// 判断是否需要扩容
if ( size > threshold)
// 将容量扩大两倍
resize();
return onlyIfAbsent ? oldValue : null;
}总结
通过HashMap的代码演变,我们可以看出:
- JDK1.8引入了红黑树,降低了链表过长的可能性,提高了效率。
- JDK1.8使用synchronized CAS控制并发扩容,避免锁定整个table,提高了并发度。
- JDK1.8对null key做了优化,null键值对存储在table[0]位置。
- 三个版本的HashMap都采用链表散列结构,通过key的hashCode映射到table,如果hash冲突就采用链表存储。
- 扩容的阈值loadFactor在三个版本都是0.75,阈值size和table大小的乘积超过loadFactor时触发扩容。
自己实现一个简单的HashMap
- 定义Node节点,存储键值对和下一个节点的引用。
static class Node {
int key;
int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}- 初始化HashMap,定义数组table的初始大小和加载因子loadFactor。
private static int CAPACITY = 16;
private static float LOAD_FACTOR = 0.75f;
private Node[] table;
private int size = 0;- 计算key的hash值,然后通过hash值&(table.length - 1)确定其在数组中的位置。
private int hash(int key) {
return key & (table.length - 1);
}- 添加元素,先确定索引位置,如果不存在 hash 冲突则直接插入。如果存在 hash 冲突,则采用拉链法解决冲突。
public void put(int key, int value) {
if (size >= LOAD_FACTOR * table.length) {
// 进行扩容
}
int hash = hash(key);
Node node = table[hash];
if (node == null) {
// 插入新节点,无hash冲突
table[hash] = new Node(key, value);
size ;
} else {
// 有hash冲突,采用拉链法解决
Node pre = null;
while (node != null) {
if (node.key == key) {
node.value = value;
return;
}
pre = node;
node = node.next;
}
// 插入新节点到链表尾部
pre.next = new Node(key, value);
size ;
}
}- 扩容机制,新table的大小为原来的2倍,并重新计算每个键值对的位置,迁移数据。
private void resize() {
Node[] newTable = new Node[table.length * 2];
for (Node node : table) {
if (node != null) {
Node next = null;
while (node != null) {
next = node.next;
int hash = hash(node.key);
if (newTable[hash] == null) {
newTable[hash] = node;
} else {
Node n = newTable[hash];
while (n.next != null)
n = n.next;
n.next = node;
}
node = next;
}
}
}
table = newTable;
} 这就是一个简单的HashMap的实现,通过数组 链表实现“拉链法”解决哈希冲突。当链表长度过长时进行扩容,采用重新计算位置的方式迁移节点。
HashMap的时间复杂度分析
我们来分析一下HashMap的时间复杂度:
- 查找:
- 平均情况下,查找的时间复杂度为O(1)。因为我们可以通过hash值直接定位到数据所在的bucket,然后再通过key的equals方法判断是否命中。
- 最坏情况下,如果HashMap中所有键值对所hash得到的index都是同一个,此时查找的时间复杂度为O(n),需要遍历整个链表。但这种情况的概率很小,可以忽略。
- 添加:
- 平均情况下,添加的时间复杂度也为O(1)。和查找一样,可以通过hash值直接定位到数据所在的bucket,然后再插入。
- 最坏情况下,如果HashMap中所有键值对所hash得到的index都是同一个,此时添加的时间复杂度为O(n),需要遍历整个链表。但这种情况的概率很小,可以忽略。
- 删除:
- 平均情况下,删除的时间复杂度为O(1)。可以通过hash值直接定位到数据所在的bucket,然后再进行删除。
- 最坏情况下,如果要删除的键值对在链表的尾部,需要遍历整个链表,时间复杂度为O(n)。但这种情况概率也很小,可以忽略。
- 扩容:
- 扩容的时间复杂度为O(n),需要重新计算每个键值对的位置,然后迁移数据。但扩容操作很少发生,一般来说可以忽略扩容对时间复杂度的影响。
所以,总体来说,HashMap的时间复杂度可以看作O(1)。除非数据分布极不均匀,导致链表过长或频繁扩容,但这在实际使用中很少出现。HashMap之所以能达到O(1)的时间复杂度,主要得益于它采用的“拉链法”来解决哈希冲突。相比直接在数组中查找,拉链法大大减少了查找的时间复杂度。
HashMap的空间复杂度分析
空间复杂度主要取决于 HashMap 的容量(table的大小)和键值对的数量。
- 容量:HashMap的默认容量为16,之后每次扩容的时候容量都会翻倍。所以如果一共扩容了n次,HashMap的容量大小为16*(2^n)。
- 键值对数量:HashMap最大可以存储2^32个键值对。
所以:
- 如果键值对数量远远小于2^32,则空间复杂度可以看作O(n),n为扩容次数。
- 如果键值对数量接近上限232,则空间复杂度可以看作O(232)。
但由于扩容操作消耗性能,也会浪费一定的空间(相当于目前使用了容量的1/2),所以我们应该在初始化HashMap的时候就指定一个合适的容量,避免过多的扩容操作。
如果我们指定HashMap的初始容量,那么空间复杂度可以简单的分析如下:
- 指定初始容量为n,键值对数量为m,如果m<<n,则空间复杂度为O(n)。
- 如果m>n,又进行了k次扩容,则空间复杂度为O(n 2^k)。
- 如果一共扩容了32次,达到上限,则空间复杂度为O(2^32)。
所以我们可以得出结论:
- 当键值对数量远小于初始容量时,空间复杂度可看作O(初始容量)。
- 当键值对数量接近HashMap的上限时,空间复杂度为O(2^32)。
- 其余情况下,空间复杂度介于O(初始容量)和O(2^32)之间。
因此,我们在初始化HashMap的时候,应该设置一个合适的初始容量,既不会造成过多扩容,也不会有太大的空间浪费,这需要根据实际场景来判断。
HashMap的应用场景
HashMap是Java中最常用的Map之一,它有以下主要应用场景:
- 缓存:HashMap是实现缓存机制的理想选择,因为它的时间复杂度为O(1),可以快速存取缓存数据。
- 大数据量的键值存储:HashMap是基于哈希表实现的,可以快速地完成大量键值对的存储和查找。
- 数据去重:我们可以把所有数据放入HashMap,然后判断put操作的返回值是否为null来判断该键值对是否已经存在,实现数据去重的功能。
- 数据搜索:我们可以把所有数据categorize到不同的HashMap中,这样可以通过键值快速搜索到所需的数据。例如,在leetcode第一次出现的问题可以存在一个HashMap,出现频率最高的10道题可以存在一个HashMap。这样我们就可以快速搜索到这两个信息。
- 保存在数据库中查重:在示例入库之前,可以先将数据放入HashMap,然后判断HashMap中是否已经存在该数据,如果存在则不入库,这样可以避免数据库中出现重复数据。
- 实现LRU缓存机制:我们可以使用HashMap与双向链表相结合的方式来实现LRU缓存机制。HashMap用来快速存取键值对,双向链表保证最近使用的节点靠近头部,这样我们就可以快速找到最近最少使用的节点进行删除。
class LRUCache {
class Node {
int key;
int value;
Node prev;
Node next;
}
private HashMap<Integer, Node> map;
private Node head;
private Node tail;
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
}
public int get(int key) {
if (map.containsKey(key)) {
// 如果key存在,先从链表中删除该节点
Node node = map.get(key);
removeFromList(node);
// 然后重新插到头部
addToHead(node);
return node.value;
} else {
return -1;
}
}
public void put(int key, int value) {
if (map.containsKey(key)) {
// 如果key已存在,先从链表中删除该节点
Node node = map.get(key);
removeFromList(node);
}
// 将新节点添加到头部
Node node = new Node(key, value);
addToHead(node);
map.put(key, node);
// 如果容量已满,删除链表尾部节点
if (map.size() > capacity) {
Node tail = removeTail();
map.remove(tail.key);
}
}
}这就是使用HashMap和双向链表实现的LRU缓存机制。我们利用HashMap的O(1)时间复杂度快速存取键值对,利用双向链表保证最近使用的数据靠近头部,这样在容量满的时候可以快速删除最近最少使用的节点。
HashMap的弊端及解决方案
HashMap也有一些弊端,主要包括:
- 线程不安全:HashMap是非线程安全的,在多线程环境下使用时需要外部同步机制来保证线程安全,这会影响性能。解决方案:可以使用ConcurrentHashMap,它是HashMap的线程安全版本,内部采用了锁分段技术来实现高度并发下的线程安全。
- 键值对顺序不保证:HashMap的键值对顺序是由hash值决定的,所以遍历HashMap时的顺序是不确定的。如果需要保证顺序,HashMap不太适用。解决方案:可以使用TreeMap,它是基于红黑树实现的,可以保证键值对的顺序。也可以使用LinkedHashMap,它是HashMap的子类,可以保证键值对的插入顺序。
- hash冲突:由于hash函数的局限性,不同的键可能会哈希到同一个位置,这种情况称为hash冲突。HashMap采用拉链法解决hash冲突,如果超出一定长度就会转化为红黑树,这样会消耗一定的时间和空间。解决方案:可以选择一个良好的hash函数来降低hash冲突的概率。也可以初始化HashMap的时候指定一个合理的容量,避免在容量过小的情况下就产生过多hash冲突。
- 空间占用可能很高:如果HashMap中的键值对数量远小于初始容量,就会造成空间的浪费。如果键值对数量不断增加,HashMap的空间占用会急剧上升(每次扩容为原来的2倍)。解决方案:初始化HashMap的时候指定一个合理的容量,既不会造成空间的浪费,也不会由于频繁扩容导致空间占用急剧上升。也可以使用ConcurrentHashMap,它的扩容机制可以避免空间的浪费。
- 键为null的问题:如果KeyValue中键为null,那么它会被存储在table[0]的bucket中,这会影响get和put的性能。解决方案:可以选择不允许null作为键,或者使用ConcurrentHashMap,它对null键进行了优化,不会影响性能。
综上,ConcurrentHashMap可以很好的解决HashMap的上述弊端,所以在高并发环境下,ConcurrentHashMap通常被用来替代HashMap。但当键值对数量较小,并发度不高的场景下,HashMap也是一种非常高效的数据结构。
HashMap与HashSet的关系
HashSet底层实际上是基于HashMap实现的。它使用HashMap的key来存储元素,value使用默认对象PRESENT。HashSet的主要方法底层实际上是调用的HashMap的方法。例如:
- add(E e) -> put(e, PRESENT)
- remove(E e) -> remove(e)
- contains(E e) -> containsKey(e)
- size() -> size()
- isEmpty() -> isEmpty()
- iterator() -> keySet().iterator()
所以我们可以总结:
- HashSet底层使用HashMap来实现。
- HashSet中的元素实际上被当作HashMap的键。
- HashSet不允许存储重复元素,是由于HashMap的键也不允许重复导致的。
- HashSet的迭代顺序取决于HashMap的键迭代顺序,这是不确定的。
- HashSet不保证元素的顺序,这也是由HashMap决定的。
下面通过一个示例体现他们的关系:
代码语言：javascript复制HashSet<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("c");
HashMap<String, Object> map = (HashMap<String, Object>) set;
// map是 {a=PRESENT, b=PRESENT, c=PRESENT}
// set和map的方法调用是相同的
set.remove("a");
map.remove("a");
set.contains("b");
map.containsKey("b");
set.size();
map.size(); 从此示例可以很清楚的看出,HashSet仅仅是在HashMap上做了一层包装,它使用HashMap的键来存储元素,value使用默认的PRESENT对象。 所以每当我们调用HashSet的方法时,实际上都是在调用HashMap对应的方法,二者之间的关系十分密切。理解了HashSet和HashMap的关系,也就很容易理解HashSet的实现原理和工作机制了。所以这是一个比较重要的知识点,值得我们深入学习和理解。
HashMap与 Hashtable的区别
HashMap和Hashtable都是基于哈希表实现的Map,但是在实现上有一定的区别。主要区别如下:
- 线程安全性:HashMap是非线程安全的,Hashtable是线程安全的。Hashtable内部的方法基本都经过synchronized修饰,达到了线程安全。
- Null键和值:HashMap允许null键和null值,Hashtable不允许任何null键和null值。
- 容量和扩容:HashMap的默认初始容量是16,扩容时容量翻倍。Hashtable的默认初始容量是11,之后每次扩容时容量翻倍加1。
- 扩容方式:HashMap的扩容方式是在旧表中取值,Hashtable的扩容方式是创建一个新表,将旧表的值拷贝到新表中。HashMap的扩容方式更加高效。
- 迭代器:HashMap的迭代器是fail-fast的,而Hashtable的迭代器是fail-safe的。所以在遍历的时候,Hashtable更加适合高并发的场景。
- 底层数据结构:JDK1.8以前,HashMap和Hashtable的底层都采用数组 链表实现。JDK1.8后,HashMap采用了数组 链表 红黑树实现,Hashtable依然保持数组 链表。所以HashMap的性能优于Hashtable。
除了以上区别外,HashMap和Hashtable的方法使用方式基本相同,功能也基本相同。所以除非对线程安全有较高要求,否则更推荐使用HashMap来代替Hashtable。
下面通过一个示例来体现他们的一些区别:
代码语言：javascript复制// HashMap
HashMap<String, String> map = new HashMap<>();
map.put(null, null);
map.put("a", "a");
map.put(null, "b");
// Hashtable
Hashtable<String, String> table = new Hashtable<>();
table.put("a", "a"); // OK
table.put(null, null); // java.lang.NullPointerException
table.put(null, "b"); // java.lang.NullPointerException从示例可以看出HashMap允许null键null值,而Hashtable则抛出异常。这就是二者在这一点的重要区别。
所以总体来说,除非对线程安全有较高要求,HashMap在大多数情况下都优于Hashtable。Hashtable相比来说耗时耗空间,体现不出现代计算机异构计算能力。
HashMap的长度为什么是2的幂次方
HashMap的长度为什么要取2的幂(一般初始化为2的4次方16),这是因为:
- hash算法的最后一步通常是对表长length取模运算(hash%length),如果length是2的幂,那么length-1的二进制码全部为1,这种情况下取模运算等价于与运算(hash&(length-1)),与运算的效率高于取模运算。所以将长度定为2的幂可以提高hash寻址的效率。
- 如果存在大量hash冲突,链表会变得较长。如果表长为2的幂,容易通过二进制码与运算定位到冲突的链表,否则需要取模运算,效率较低。
- 扩容时,如果新表长仍然是2的幂,原来的hash值仍然有效。只需要将原来的hash值对新表长取与运算,就可以直接定位到数据位置。否则所有的hash值都需要重新hash,效率较低。
举个例子,假设当前HashMap的容量为16(10000),扩容后容量变为32(100000)。
如果是2的幂,只需要将原本的hash值(如11011)与新的表长-1(11111)做与运算(11011)。得到新的位置(11011)。如果不是2的幂,需要重新hash。
比如原来位置是hash=11,新位置应该是hash2=19。这需要重新计算hash值,效率较低。
所以总结来说,HashMap的长度取2的幂主要出于3个方面的考虑:
- hash寻址的效率。
- 2的幂的length-1全部为1,适合用与运算代替取模运算。解决hash冲突时,容易通过与运算定位到冲突链表。
- 扩容时,可以通过与运算重新定位,无需全表rehash。
这也就是HashMap容量为什么要选用2的幂的原因了。这在一定程度上也提高了HashMap的性能,值得我们学习和理解。
JDK1.8对HashMap的优化
在JDK1.8之前,HashMap采用数组 链表实现,数组是HashMap的主体,链表则是解决哈希冲突的手段。
但是当链表长度过长时,HashMap的性能会受到比较大的影响。JDK1.8对这一点进行了优化,引入了红黑树。
当链表长度太长(默认超过8)时,链表就转化为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能。
所以JDK1.8的HashMap底层采用数组 链表 红黑树实现,当链表长度不足8时仍然采用链表解决冲突,当链表长度超过8时转化为红黑树,这样既发挥了链表在冲突少的情况下性能高的优点,又利用了红黑树在冲突多的情况下性能高的优点。
tips: 其中红黑树的插入、删除、查找时间复杂度均为O(logN),效率很高。
除此之外,JDK1.8的HashMap还有其他优化:
- 引入红黑树之前,HashMap扩容是一个比较消耗性能的操作(rehash),JDK1.8在扩容时做了优化,不再像之前那样全部rehash,而是采用相对高效的方式进行rehash。
- JDK1.8的HashMap中,链表转红黑树会选择比较高的阈值(8),这样可以尽量减少红黑树结点过少导致性能不如链表的情况出现。
- JDK1.8的HashMap中,链表转红黑树和红黑树转链表都采取了较为高效的方式,而不是全部重新构建,这也提高了性能。
- JDK1.8的HashMap废除了原来的Entry对象,取而代之的是Node对象。其中,Node是一个泛型类。这也带来了一定的性能提高。
- …
通过以上几点优化,JDK1.8的HashMap在时间和空间两方面都取得较大提高。它既解决了之前版本在大容量和高冲突率下性能下降的问题,也不失在一般场景下的高性能,这也是它成为如今最主流的Map实现的原因。
所以如果你的程序需要支持JDK1.8以上的环境,强烈建议使用JDK1.8及之后的HashMap,这会让你的程序既高效又具有很好的拓展性。理解JDK1.8对HashMap的优化,也有助于我们更深入地理解HashMap这个数据结构。
HashMap的遍历方式
HashMap提供了几种方式遍历所有键值对:
- entrySet()遍历:通过HashMap.entrySet()获得key-value的Set集合,然后进行遍历。这是最常用的遍历方式。
HashMap<String, Integer> map = new HashMap<>();
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
// do something
}- keySet()遍历:通过HashMap.keySet()获得所有的key,然后通过get(key)获得对应的value。
HashMap<String, Integer> map = new HashMap<>();
for (String key : map.keySet()) {
Integer value = map.get(key);
// do something
}- values()遍历:通过HashMap.values()获得所有的value,这种方式我们无法获取到key,只能遍历value。
HashMap<String, Integer> map = new HashMap<>();
for (Integer value : map.values()) {
// do something
}- 迭代器遍历:通过HashMap.entrySet().iterator()获取迭代器进行遍历。
HashMap<String, Integer> map = new HashMap<>();
Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<String, Integer> entry = iter.next();
String key = entry.getKey();
Integer value = entry.getValue();
// do something
}- Lambda表达式遍历(JDK1.8 ):JDK1.8提供了Lambda表达式,使我们可以更简洁地遍历HashMap。
HashMap<String, Integer> map = new HashMap<>();
map.forEach((k, v) -> {
// do something
});以上就是HashMap提供的几种遍历方式,entrySet()方法是最常用的方式,我们在学习和使用HashMap时可以灵活运用这几种遍历方式。
需要注意的是,无论使用哪种遍历方式,遍历过程中如果对HashMap进行修改(增加、删除键值对),都有可能会产生 ConcurrentModificationException,这是因为遍历时使用的迭代器或是HashMap的快照,并不反映在遍历过程中对原HashMap的修改。
所以在遍历HashMap的过程中,如果对其进行修改,应该使用Iterator.remove()等保证迭代器稳定的方法,或者捕获ConcurrentModificationException并在catch块中进行相应处理。
HashMap的常见面试题
- HashMap的工作原理?HashMap底层采用哈希表实现,它包含数组 链表/红黑树的结构。HashMap会根据键的hashCode计算出对应的数组下标,如果发生哈希冲突,就将键值对存储在链表或者红黑树中。JDK1.8之前,HashMap采用数组 链表结构,1.8之后引入了红黑树来优化链表过长的情况。
- HashMap的底层实现?JDK1.8之前,HashMap底层采用数组 链表实现,数组是HashMap的主体,链表用来解决哈希冲突。JDK1.8引入了红黑树,当链表长度过长时会转化为红黑树,以提高性能。
- HashMap的扩容机制是什么?当HashMap中存储的键值对个数超过数组大小*加载因子时,HashMap会进行扩容操作。扩容时,容量会翻倍,并进行rehash操作。JDK1.8在扩容时做了优化,只对哈希值和扩容后的索引不等的键值对进行rehash。
- HashMap的线程安全性?HashMap是非线程安全的,在多线程环境下使用时需要外部同步机制来保证线程安全。 HashTable是线程安全的,内部的方法基本都加了synchronized关键字进行同步。如果需要考虑线程安全,建议使用ConcurrentHashMap。
- HashMap判断两个键值对相等的标准?HashMap判断两个键值对相等的标准是两个键的hashCode相等,并且两个键通过equals方法比较也返回true。hashCode相等表明两个键可能相等,但需要进一步通过equals方法确定。
- HashMap允许存放null键null值吗?HashMap允许存放null键和null值。当键为null时,会存储在数组的第0个位置。
- HashMap的初始容量大小是多少?加载因子是多少?HashMap的默认初始容量是16,加载因子是0.75。加载因子用来控制HashMap的空间利用率,过小会导致HashMap大小增加过快,而过大会导致链表过长。
以上是HashMap常见的一些面试题,我们在学习和使用HashMap的时候需要理解这些概念和机制,这也有助于我们在面试时回答问题。如果有不理解的地方可以再回过头来复习。
