当前位置： 首页 > article >正文

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

article 2024/11/15 5:37:38

文章目录

  • HashMap的数据结构和底层原理以及在JDK1.6、1.7和JDK8中的演变差异
  • HashMap的数据结构和原理
  • JDK1.6、1.7和1.8中的HashMap源码演变
    • JDK1.6
    • JDK1.7
    • JDK1.8
  • 总结
  • 自己实现一个简单的HashMap
  • HashMap的时间复杂度分析
  • HashMap的空间复杂度分析
  • HashMap的应用场景
  • HashMap的弊端及解决方案
  • HashMap与HashSet的关系
  • HashMap与 Hashtable的区别
  • HashMap的长度为什么是2的幂次方
  • JDK1.8对HashMap的优化
  • HashMap的遍历方式
  • HashMap的常见面试题

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; 
    }
  }
  // 添加新Entry
  modCount++;
  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;
  }
}
  1. 初始化HashMap,定义数组table的初始大小和加载因子loadFactor。
private static int CAPACITY = 16;
private static float LOAD_FACTOR = 0.75f;
private Node[] table;
private int size = 0;
  1. 计算key的hash值,然后通过hash值&(table.length - 1)确定其在数组中的位置。
private int hash(int key) {
  return key & (table.length - 1); 
}
  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++;
  }
}
  1. 扩容机制,新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为扩容次数。
  • 如果键值对数量接近上限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之一,它有以下主要应用场景:

  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
}
  1. 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
}
  1. values()遍历:通过HashMap.values()获得所有的value,这种方式我们无法获取到key,只能遍历value。
HashMap<String, Integer> map = new HashMap<>();
for (Integer value : map.values()) {
    // do something
}
  1. 迭代器遍历:通过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
}
  1. 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的时候需要理解这些概念和机制,这也有助于我们在面试时回答问题。如果有不理解的地方可以再回过头来复习。


http://www.kler.cn/a/16470.html

相关文章：

  • Android Studio更新成2024.1.2版本后旧项目Gradle配置问题
  • 学习记录：js算法（九十二）：克隆图
  • C++ 的协程
  • 使用pytest+openpyxl做接口自动化遇到的问题
  • 28.医院管理系统（基于springboot和vue）
  • 编译ffmpeg动态库时设置RPATH为$ORIGIN
  • Blender启动场景的修改
  • 资讯汇总230503
  • 哈希表企业应用-DNA的字符串检测
  • CKA/CKS/CKAD认证考试攻略
  • 【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】
  • 【LeetCood206】反转链表
  • Python小姿势 - Python学习笔记——类与对象
  • ZooKeeper安装与配置集群
  • NECCS｜全国大学生英语竞赛C类｜词汇和语法｜词汇题｜21:03～21:53
  • 可视化绘图技巧100篇高级篇（一）-环状条形图（radial bar chart）
  • android基础知识
  • Redis高频面试题，使用场景
  • TiDB实战篇-操作系统参数TiDB Server
  • HDU5909 Tree Cutting（FWT）
  • 人人都可用chatgpt开发小项目
  • 第十二章 Transform组件（下）
  • numpy的下载、数据类型、属性、数组创建
  • Redis-列表(List)
  • 【23】linux进阶——linux的软链接和硬链接
  • NTT学习笔记（快速数论变换）