HashMap、TreeMap的特点、实现、优缺点比较

原创

堕落飞鸟

发布于 2023-04-04 07:10:27

9060

发布于 2023-04-04 07:10:27

文章被收录于专栏：飞鸟的专栏

HashMap和TreeMap都是Java中常用的Map接口的实现类，它们都可以存储键值对，并提供快速的查找、插入、删除操作。

HashMap的特点：

基于哈希表实现，查找、插入、删除的时间复杂度为O(1)；
可以存储null值和null键；
内部无序，不能保证元素的顺序；
迭代HashMap的顺序是不确定的。

HashMap的实现：

HashMap的内部实现是由数组和链表（或红黑树）组成的。数组的每个元素都是一个链表（或红黑树），链表（或红黑树）中存储的是键值对。当发生哈希冲突时，新的键值对会被添加到链表（或红黑树）的尾部。当链表（或红黑树）中元素的个数超过了一个阈值时，链表（或红黑树）就会被转换成红黑树。这样可以保证HashMap的性能在最坏情况下也能达到O(log n)。

HashMap的优点：

查找、插入、删除的时间复杂度为O(1)；
可以存储null值和null键；
内存占用比较小；
适合于快速查找、插入、删除元素的场景。

HashMap的缺点：

迭代HashMap的顺序是不确定的；
当哈希冲突比较严重时，性能会下降；
不支持按照键值对的键或值进行排序。

示例代码：

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
  public static void main(String[] args) {
    Map<String, Integer> map = new HashMap<>();

    // 添加键值对
    map.put("apple", 3);
    map.put("orange", 2);
    map.put("banana", 1);

    // 遍历键值对
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
      System.out.println(entry.getKey() + " = " + entry.getValue());
    }

    // 删除键值对
    map.remove("orange");

    // 判断是否包含某个键
    System.out.println(map.containsKey("apple"));
  }
}

TreeMap的特点：

基于红黑树实现，查找、插入、删除的时间复杂度为O(log n)；
可以按照键值对的键进行排序；
不能存储null键；
内部有序，可以保证元素的顺序；
迭代TreeMap的顺序是按照键值对的键的顺序输出的。

TreeMap的实现：

TreeMap的内部实现是由红黑树组成的。红黑树是一种自平衡的二叉搜索树，可以保证插入、删除、查找操作的时间复杂度都是O(log n)。在插入键值对时，TreeMap会按照键进行排序，这样可以保证遍历TreeMap时的顺序是按照键的顺序输出的。

TreeMap的优点：

可以按照键值对的键进行排序；
内部有序，可以保证元素的顺序；
性能比HashMap更稳定，不会因为哈希冲突而导致性能下降。

TreeMap的缺点：

查找、插入、删除的时间复杂度为O(log n)，相比于HashMap稍微慢一些；
不能存储null键；
内存占用比较大；
不支持按照键值对的值进行排序。

示例代码：

import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample {
  public static void main(String[] args) {
    Map<String, Integer> map = new TreeMap<>();

    // 添加键值对
    map.put("apple", 3);
    map.put("orange", 2);
    map.put("banana", 1);

    // 遍历键值对
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
      System.out.println(entry.getKey() + " = " + entry.getValue());
    }

    // 删除键值对
    map.remove("orange");

    // 判断是否包含某个键
    System.out.println(map.containsKey("apple"));
  }
}

在上面的示例代码中，我们先创建了一个TreeMap对象，然后添加了几个键值对。遍历键值对时，我们可以看到输出的顺序是按照键的顺序输出的。接着我们删除了一个键值对，然后判断是否包含某个键。可以看到，即使删除了一个键值对，TreeMap的内部仍然保持着有序状态。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

登录后参与评论

0 条评论

热度