【面试长文】HashMap的数据结构和底层原理以及在JDK1.6、1.7和JDK8中的演变差异

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的长度的乘积。

获取数据的步骤:

1. 计算key的hashCode,然后通过hashCode映射到table数组的index。

2. 如果table的index位置没有数据,直接添加。

3. 如果table的index位置有数据,查看key是equals()。如果equals,则覆盖旧值;如果不equals,进行加链表或树化操作。如果链表长度超过8,则转换为红黑树。

4. 添加后,检查是否需要扩容。如果size超过loadFactor*table.length,进行扩容操作。扩容操作是创建一个新的table,新table的大小为旧table的2倍。

JDK1.6、1.7和1.8中的HashMap源码演变

JDK1.6

JDK1.6中的HashMap是非线程安全的,扩容使用synchronized来锁定整个table。

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; }}// 添加新EntrymodCount++;addEntry(hash, key, value, i); return null; 
}

JDK1.7

JDK1.7中的HashMap是非线程安全的,采用“链表+红黑树”的结构。当链表长度超过8时会将链表转换为红黑树。扩容时使用synchronized锁定table[0]和table[table.length-1]。

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"的方式来控制并发度。同时引入了红黑树,减少了链表过长的情况。

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的代码演变,我们可以看出:

1. JDK1.8引入了红黑树,降低了链表过长的可能性,提高了效率。
2. JDK1.8使用synchronized+CAS控制并发扩容,避免锁定整个table,提高了并发度。
3. JDK1.8对null key做了优化,null键值对存储在table[0]位置。
4. 三个版本的HashMap都采用链表散列结构,通过key的hashCode映射到table,如果hash冲突就采用链表存储。
5. 扩容的阈值loadFactor在三个版本都是0.75,阈值size和table大小的乘积超过loadFactor时触发扩容。

自己实现一个简单的HashMap

1. 定义Node节点,存储键值对和下一个节点的引用。

static class Node {int key;int value;Node next;public Node(int key, int value) {this.key = key;this.value = value;}
}

2. 初始化HashMap,定义数组table的初始大小和加载因子loadFactor。

private static int CAPACITY = 16;
private static float LOAD_FACTOR = 0.75f;
private Node[] table;
private int size = 0;

3. 计算key的hash值,然后通过hash值&(table.length - 1)确定其在数组中的位置。

private int hash(int key) {return key & (table.length - 1); 
}

4. 添加元素,先确定索引位置,如果不存在 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++;}
}

5. 扩容机制,新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的时间复杂度:

1. 查找:
   • 平均情况下,查找的时间复杂度为O(1)。因为我们可以通过hash值直接定位到数据所在的bucket,然后再通过key的equals方法判断是否命中。
   • 最坏情况下,如果HashMap中所有键值对所hash得到的index都是同一个,此时查找的时间复杂度为O(n),需要遍历整个链表。但这种情况的概率很小,可以忽略。
2. 添加:
   • 平均情况下,添加的时间复杂度也为O(1)。和查找一样,可以通过hash值直接定位到数据所在的bucket,然后再插入。
   • 最坏情况下,如果HashMap中所有键值对所hash得到的index都是同一个,此时添加的时间复杂度为O(n),需要遍历整个链表。但这种情况的概率很小,可以忽略。
3. 删除:
   • 平均情况下,删除的时间复杂度为O(1)。可以通过hash值直接定位到数据所在的bucket,然后再进行删除。
   • 最坏情况下,如果要删除的键值对在链表的尾部,需要遍历整个链表,时间复杂度为O(n)。但这种情况概率也很小,可以忽略。
4. 扩容:
   • 扩容的时间复杂度为O(n),需要重新计算每个键值对的位置,然后迁移数据。但扩容操作很少发生,一般来说可以忽略扩容对时间复杂度的影响。

所以,总体来说,HashMap的时间复杂度可以看作O(1)。除非数据分布极不均匀,导致链表过长或频繁扩容,但这在实际使用中很少出现。HashMap之所以能达到O(1)的时间复杂度,主要得益于它采用的“拉链法”来解决哈希冲突。相比直接在数组中查找,拉链法大大减少了查找的时间复杂度。

HashMap的空间复杂度分析

空间复杂度主要取决于 HashMap 的容量(table的大小)和键值对的数量。

1. 容量:HashMap的默认容量为16,之后每次扩容的时候容量都会翻倍。所以如果一共扩容了n次,HashMap的容量大小为16*(2^n)。
2. 键值对数量:HashMap最大可以存储2^32个键值对。

所以:

• 如果键值对数量远远小于2^32,则空间复杂度可以看作O(n),n为扩容次数。
• 如果键值对数量接近上限2^{32,则空间复杂度可以看作O(2}32)。

但由于扩容操作消耗性能,也会浪费一定的空间(相当于目前使用了容量的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之一,它有以下主要应用场景:

1. 缓存:HashMap是实现缓存机制的理想选择,因为它的时间复杂度为O(1),可以快速存取缓存数据。
2. 大数据量的键值存储:HashMap是基于哈希表实现的,可以快速地完成大量键值对的存储和查找。
3. 数据去重:我们可以把所有数据放入HashMap,然后判断put操作的返回值是否为null来判断该键值对是否已经存在,实现数据去重的功能。
4. 数据搜索:我们可以把所有数据categorize到不同的HashMap中,这样可以通过键值快速搜索到所需的数据。例如,在leetcode第一次出现的问题可以存在一个HashMap,出现频率最高的10道题可以存在一个HashMap。这样我们就可以快速搜索到这两个信息。
5. 保存在数据库中查重:在示例入库之前,可以先将数据放入HashMap,然后判断HashMap中是否已经存在该数据,如果存在则不入库,这样可以避免数据库中出现重复数据。
6. 实现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也有一些弊端,主要包括:

1. 线程不安全:HashMap是非线程安全的,在多线程环境下使用时需要外部同步机制来保证线程安全,这会影响性能。解决方案:可以使用ConcurrentHashMap,它是HashMap的线程安全版本,内部采用了锁分段技术来实现高度并发下的线程安全。
2. 键值对顺序不保证:HashMap的键值对顺序是由hash值决定的,所以遍历HashMap时的顺序是不确定的。如果需要保证顺序,HashMap不太适用。解决方案:可以使用TreeMap,它是基于红黑树实现的,可以保证键值对的顺序。也可以使用LinkedHashMap,它是HashMap的子类,可以保证键值对的插入顺序。
3. hash冲突:由于hash函数的局限性,不同的键可能会哈希到同一个位置,这种情况称为hash冲突。HashMap采用拉链法解决hash冲突,如果超出一定长度就会转化为红黑树,这样会消耗一定的时间和空间。解决方案:可以选择一个良好的hash函数来降低hash冲突的概率。也可以初始化HashMap的时候指定一个合理的容量,避免在容量过小的情况下就产生过多hash冲突。
4. 空间占用可能很高:如果HashMap中的键值对数量远小于初始容量,就会造成空间的浪费。如果键值对数量不断增加,HashMap的空间占用会急剧上升(每次扩容为原来的2倍)。解决方案:初始化HashMap的时候指定一个合理的容量,既不会造成空间的浪费,也不会由于频繁扩容导致空间占用急剧上升。也可以使用ConcurrentHashMap,它的扩容机制可以避免空间的浪费。
5. 键为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决定的。

下面通过一个示例体现他们的关系:

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,但是在实现上有一定的区别。主要区别如下:

1. 线程安全性:HashMap是非线程安全的,Hashtable是线程安全的。Hashtable内部的方法基本都经过synchronized修饰,达到了线程安全。
2. Null键和值:HashMap允许null键和null值,Hashtable不允许任何null键和null值。
3. 容量和扩容:HashMap的默认初始容量是16,扩容时容量翻倍。Hashtable的默认初始容量是11,之后每次扩容时容量翻倍加1。
4. 扩容方式:HashMap的扩容方式是在旧表中取值,Hashtable的扩容方式是创建一个新表,将旧表的值拷贝到新表中。HashMap的扩容方式更加高效。
5. 迭代器:HashMap的迭代器是fail-fast的,而Hashtable的迭代器是fail-safe的。所以在遍历的时候,Hashtable更加适合高并发的场景。
6. 底层数据结构:JDK1.8以前,HashMap和Hashtable的底层都采用数组+链表实现。JDK1.8后,HashMap采用了数组+链表+红黑树实现,Hashtable依然保持数组+链表。所以HashMap的性能优于Hashtable。

除了以上区别外,HashMap和Hashtable的方法使用方式基本相同,功能也基本相同。所以除非对线程安全有较高要求,否则更推荐使用HashMap来代替Hashtable。

下面通过一个示例来体现他们的一些区别:

// 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),这是因为:

1. hash算法的最后一步通常是对表长length取模运算(hash%length),如果length是2的幂,那么length-1的二进制码全部为1,这种情况下取模运算等价于与运算(hash&(length-1)),与运算的效率高于取模运算。所以将长度定为2的幂可以提高hash寻址的效率。
2. 如果存在大量hash冲突,链表会变得较长。如果表长为2的幂,容易通过二进制码与运算定位到冲突的链表,否则需要取模运算,效率较低。
3. 扩容时,如果新表长仍然是2的幂,原来的hash值仍然有效。只需要将原来的hash值对新表长取与运算,就可以直接定位到数据位置。否则所有的hash值都需要重新hash,效率较低。

举个例子,假设当前HashMap的容量为16(10000),扩容后容量变为32(100000)。

如果是2的幂,只需要将原本的hash值(如11011)与新的表长-1(11111)做与运算(11011)。得到新的位置(11011)。如果不是2的幂,需要重新hash。

比如原来位置是hash%16=11,新位置应该是hash%32=19。这需要重新计算hash值,效率较低。

所以总结来说,HashMap的长度取2的幂主要出于3个方面的考虑:

1. hash寻址的效率。
2. 2的幂的length-1全部为1,适合用与运算代替取模运算。解决hash冲突时,容易通过与运算定位到冲突链表。
3. 扩容时,可以通过与运算重新定位,无需全表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还有其他优化:

1. 引入红黑树之前,HashMap扩容是一个比较消耗性能的操作(rehash),JDK1.8在扩容时做了优化,不再像之前那样全部rehash,而是采用相对高效的方式进行rehash。
2. JDK1.8的HashMap中,链表转红黑树会选择比较高的阈值(8),这样可以尽量减少红黑树结点过少导致性能不如链表的情况出现。
3. JDK1.8的HashMap中,链表转红黑树和红黑树转链表都采取了较为高效的方式,而不是全部重新构建,这也提高了性能。
4. JDK1.8的HashMap废除了原来的Entry对象,取而代之的是Node对象。其中,Node是一个泛型类。这也带来了一定的性能提高。
5. …

通过以上几点优化,JDK1.8的HashMap在时间和空间两方面都取得较大提高。它既解决了之前版本在大容量和高冲突率下性能下降的问题,也不失在一般场景下的高性能,这也是它成为如今最主流的Map实现的原因。

所以如果你的程序需要支持JDK1.8以上的环境,强烈建议使用JDK1.8及之后的HashMap,这会让你的程序既高效又具有很好的拓展性。理解JDK1.8对HashMap的优化,也有助于我们更深入地理解HashMap这个数据结构。

HashMap的遍历方式

HashMap提供了几种方式遍历所有键值对:

1. 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
}

2. 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
}

3. values()遍历:通过HashMap.values()获得所有的value,这种方式我们无法获取到key,只能遍历value。

HashMap<String, Integer> map = new HashMap<>();
for (Integer value : map.values()) {// do something
}

4. 迭代器遍历:通过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
}

5. 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的常见面试题

1. HashMap的工作原理?HashMap底层采用哈希表实现,它包含数组+链表/红黑树的结构。HashMap会根据键的hashCode计算出对应的数组下标,如果发生哈希冲突,就将键值对存储在链表或者红黑树中。JDK1.8之前,HashMap采用数组+链表结构,1.8之后引入了红黑树来优化链表过长的情况。
2. HashMap的底层实现?JDK1.8之前,HashMap底层采用数组+链表实现,数组是HashMap的主体,链表用来解决哈希冲突。JDK1.8引入了红黑树,当链表长度过长时会转化为红黑树,以提高性能。
3. HashMap的扩容机制是什么?当HashMap中存储的键值对个数超过数组大小*加载因子时,HashMap会进行扩容操作。扩容时,容量会翻倍,并进行rehash操作。JDK1.8在扩容时做了优化,只对哈希值和扩容后的索引不等的键值对进行rehash。
4. HashMap的线程安全性?HashMap是非线程安全的,在多线程环境下使用时需要外部同步机制来保证线程安全。 HashTable是线程安全的,内部的方法基本都加了synchronized关键字进行同步。如果需要考虑线程安全,建议使用ConcurrentHashMap。
5. HashMap判断两个键值对相等的标准?HashMap判断两个键值对相等的标准是两个键的hashCode相等,并且两个键通过equals方法比较也返回true。hashCode相等表明两个键可能相等,但需要进一步通过equals方法确定。
6. HashMap允许存放null键null值吗?HashMap允许存放null键和null值。当键为null时,会存储在数组的第0个位置。
7. HashMap的初始容量大小是多少?加载因子是多少?HashMap的默认初始容量是16,加载因子是0.75。加载因子用来控制HashMap的空间利用率,过小会导致HashMap大小增加过快,而过大会导致链表过长。

以上是HashMap常见的一些面试题,我们在学习和使用HashMap的时候需要理解这些概念和机制,这也有助于我们在面试时回答问题。如果有不理解的地方可以再回过头来复习。