AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

HashMap vs TreeMap vs Hashtable vs LinkedHashMap

2017-11-16 1462
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

Map概览

 

Java中有四种常见的Map实现，HashMap，TreeMap，HashTable和LinkedHashMap，我们可以使用一句话来描述各个Map，如下：

  • HashMap：基于散列表实现，是无序的；
  • TreeMap：基于红黑树实现，按Key排序；
  • LinkedHashMap：保存了插入顺序；
  • Hashtable：是同步的，与HashMap类似；

HashMap

如果HashMap的Key是自己定义的对象，那么一般需要覆盖equals()和hashCode()方法，且要遵循他们之间的约定。

复制代码 
package simplejava;

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

class Dog {
    String color;

    Dog(String c) {
        color = c;
    }

    public String toString() {
        return color + " dog";
    }
}

public class Q26 {

    public static void main(String[] args) {
        HashMap<Dog, Integer> hashMap = new HashMap<Dog, Integer>();
        Dog d1 = new Dog("red");
        Dog d2 = new Dog("black");
        Dog d3 = new Dog("white");
        Dog d4 = new Dog("white");
        hashMap.put(d1, 10);
        hashMap.put(d2, 15);
        hashMap.put(d3, 5);
        hashMap.put(d4, 20);
        //print size
        System.out.println(hashMap.size());
        //loop HashMap
        for (Entry<Dog, Integer> entry : hashMap.entrySet()) {
        System.out.println(entry.getKey().toString() + " - " +
        entry.getValue());
        }
    }

}
复制代码

结果输出：

4
white dog - 5
red dog - 10
white dog - 20
black dog - 15

注意，我们不小心添加了两个"white dogs“，但是HashMap仍然存储它。这是不合理的，现在我们困惑到底有多少条白狗存入了HashMap，5还是20呢。

其实，Dog类应该是这样定义的：

复制代码 
class Dog {
    String color;

    Dog(String c) {
        color = c;
    }

    public boolean equals(Object o) {
        return ((Dog) o).color.equals(this.color);
    }

    public int hashCode() {
        return color.length();
    }

    public String toString() {
        return color + " dog";
    }
}
复制代码

结果输出：

3
red dog - 10
white dog - 20
black dog - 15

原因是因为HashMap不允许两个相同的元素存入，默认情况下，Object的hashCode()和equals()会被用于判断两个对象是否相同。默认的hashCode()方法对于不同的对象会返回不同的值，而equals()方法只有当两个引用相等，即指向同一个对象的时候才返回true。如果你不是很清楚，可以自己检验下hashCode()和equals()之间的关系。

举个例子，可以检验下HashMap中最常用的方法，如iteration,print等。

TreeMap

TreeMap是按key排序的，让我们先看下如下代码，了解其“按key排序”思想。

复制代码 
package simplejava;

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

class Dog {
    String color;

    Dog(String c) {
        color = c;
    }

    public boolean equals(Object o) {
        return ((Dog) o).color.equals(this.color);
    }

    public int hashCode() {
        return color.length();
    }

    public String toString() {
        return color + " dog";
    }
}

public class Q26 {

    public static void main(String[] args) {
        Dog d1 = new Dog("red");
        Dog d2 = new Dog("black");
        Dog d3 = new Dog("white");
        Dog d4 = new Dog("white");
        TreeMap<Dog, Integer> treeMap = new TreeMap<Dog, Integer>();
        treeMap.put(d1, 10);
        treeMap.put(d2, 15);
        treeMap.put(d3, 5);
        treeMap.put(d4, 20);

        for (Entry<Dog, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " - " + entry.getValue());
        }
    }

}
复制代码

结果输出：

Exception in thread "main" java.lang.ClassCastException: simplejava.Dog cannot be cast to java.lang.Comparable
    at java.util.TreeMap.compare(TreeMap.java:1188)
    at java.util.TreeMap.put(TreeMap.java:531)
    at simplejava.Q26.main(Q26.java:34)

由于TreeSet是基于Key排序的，所以作为key的对象需要相互比较，这就是为什么key需要实现Comparable接口。举个例子，你可以使用字符串作为Key，因为String已经实现了Comparable接口。

现在，让我们改变一下Dog，让它可比较，如下：

复制代码 
package simplejava;

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

class Dog implements Comparable<Dog> {
    String color;
    int size;

    Dog(String c, int s) {
        color = c;
        size = s;
    }

    public String toString() {
        return color + " dog";
    }

    @Override
    public int compareTo(Dog o) {
        return o.size - this.size;
    }
}

public class Q26 {

    public static void main(String[] args) {
        Dog d1 = new Dog("red", 30);
        Dog d2 = new Dog("black", 20);
        Dog d3 = new Dog("white", 10);
        Dog d4 = new Dog("white", 10);
        TreeMap<Dog, Integer> treeMap = new TreeMap<Dog, Integer>();
        treeMap.put(d1, 10);
        treeMap.put(d2, 15);
        treeMap.put(d3, 5);
        treeMap.put(d4, 20);
        for (Entry<Dog, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " - " + entry.getValue());
        }
    }

}
复制代码

结果打印：

red dog - 10
black dog - 15
white dog - 20

在这个例子中，我们是按dog的size来排序的；

如果"Dog d4 = new Dog("white", 10);"被替换成"Dog d4 = new Dog("white",40);"，结果将输出如下信息:

white dog - 20
red dog - 10
black dog - 15
white dog - 5


这是因为当前TreeMap使用compareTo()去比较key，不同的size意味着不同的dogs。

HashTable

参考java文档：HashMap与HashTable基本类似，除了非同步和允许null外。

LinkedHashMap

LinkedHashMap是HashMap的子类，意味着它继承了HashMap的特性，除此之外，LinkedHashMap还保存了插入顺序。

让我们使用同样的代码，然后将HashMap替换成LinkedHashMap，如下：

复制代码 
package simplejava;

import java.util.LinkedHashMap;
import java.util.Map.Entry;

class Dog {
    String color;

    Dog(String c) {
        color = c;
    }

    public boolean equals(Object o) {
        return ((Dog) o).color.equals(this.color);
    }

    public int hashCode() {
        return color.length();
    }

    public String toString() {
        return color + " dog";
    }
}

public class Q26 {

    public static void main(String[] args) {
        Dog d1 = new Dog("red");
        Dog d2 = new Dog("black");
        Dog d3 = new Dog("white");
        Dog d4 = new Dog("white");
        LinkedHashMap<Dog, Integer> linkedHashMap = new LinkedHashMap<Dog, Integer>();
        linkedHashMap.put(d1, 10);
        linkedHashMap.put(d2, 15);
        linkedHashMap.put(d3, 5);
        linkedHashMap.put(d4, 20);
        for (Entry<Dog, Integer> entry : linkedHashMap.entrySet()) {
            System.out.println(entry.getKey() + " - " + entry.getValue());
        }
    }

}
复制代码

输出结果：

red dog - 10
black dog - 15
white dog - 20

如果我们使用HashMap，结果如下，区别在于没有保存插入顺序：

red dog - 10
white dog - 20
black dog - 15

 本文转自风一样的码农博客园博客，原文链接：http://www.cnblogs.com/chenpi/p/5505705.html，如需转载请自行联系原作者

文章标签：
Java
C++
存储
关键词：
HashMap linkedhashmap
HashMap treemap linkedhashmap
HashMap treemap
HashMap vs
HashMap vs treemap
文艺小青年
目录
相关文章
Skyund
|
21天前
|
安全
HashTable与HashMap的区别
（1）HashTable的每个方法都用synchronized修饰，因此是线程安全的，但同时读写效率很低 （2）HashTable的Key不允许为null （3）HashTable只对key进行一次hash，HashMap进行了两次Hash （4）HashTable底层使用的数组加链表HashTable与HashMap的区别
Skyund
23 2
龙大吉
|
2月前
|
存储 Java
Java中的HashMap和TreeMap，通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap，通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称，而TreeMap则擅长于保持元素的自然排序或自定义排序，两者各具优势，适用于不同的开发场景。
龙大吉
47 1
东方睿赢
|
2月前
|
存储 安全 Java
Java Map新玩法：探索HashMap和TreeMap的高级特性，让你的代码更强大！
【10月更文挑战第17天】Java Map新玩法：探索HashMap和TreeMap的高级特性，让你的代码更强大！
东方睿赢
74 2
龙大吉
|
2月前
|
存储 Java API
详细解析HashMap、TreeMap、LinkedHashMap等实现类，帮助您更好地理解和应用Java Map。
【10月更文挑战第19天】深入剖析Java Map：不仅是高效存储键值对的数据结构，更是展现设计艺术的典范。本文从基本概念、设计艺术和使用技巧三个方面，详细解析HashMap、TreeMap、LinkedHashMap等实现类，帮助您更好地理解和应用Java Map。
龙大吉
64 3
众所周知
|
2月前
|
存储 缓存 安全
在Java的Map家族中，HashMap和TreeMap各具特色
【10月更文挑战第19天】在Java的Map家族中，HashMap和TreeMap各具特色。HashMap基于哈希表实现，提供O(1)时间复杂度的高效操作，适合性能要求高的场景；TreeMap基于红黑树，提供O(log n)时间复杂度的有序操作，适合需要排序和范围查询的场景。两者在不同需求下各有优势，选择时需根据具体应用场景权衡。
众所周知
34 2
东方睿赢
|
2月前
|
存储 安全 Java
Java Map新玩法：深入探讨HashMap和TreeMap的高级特性
【10月更文挑战第19天】Java Map新玩法：深入探讨HashMap和TreeMap的高级特性，包括初始容量与加载因子的优化、高效的遍历方法、线程安全性处理以及TreeMap的自然排序、自定义排序、范围查询等功能，助你提升代码性能与灵活性。
东方睿赢
28 2
Dylaniou
|
2月前
|
Java
让星星⭐月亮告诉你，HashMap中保证红黑树根节点一定是对应链表头节点moveRootToFront()方法源码解读
当红黑树的根节点不是其对应链表的头节点时，通过调整指针的方式将其移动至链表头部。具体步骤包括：从链表中移除根节点，更新根节点及其前后节点的指针，确保根节点成为新的头节点，并保持链表结构的完整性。此过程在Java的`HashMap$TreeNode.moveRootToFront()`方法中实现，确保了高效的数据访问与管理。
Dylaniou
30 2
Dylaniou
|
2月前
|
Java 索引
让星星⭐月亮告诉你，HashMap之往红黑树添加元素-putTreeVal方法源码解读
本文详细解析了Java `HashMap` 中 `putTreeVal` 方法的源码，该方法用于在红黑树中添加元素。当数组索引位置已存在红黑树类型的元素时，会调用此方法。具体步骤包括：从根节点开始遍历红黑树，找到合适位置插入新元素，调整节点指针，保持红黑树平衡，并确保根节点是链表头节点。通过源码解析，帮助读者深入理解 `HashMap` 的内部实现机制。
Dylaniou
36 2
Codelinghu
|
2月前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
Codelinghu
57 0
Dylaniou
|
2月前
|
存储
让星星⭐月亮告诉你，HashMap的put方法源码解析及其中两种会触发扩容的场景(足够详尽，有问题欢迎指正~)
`HashMap`的`put`方法通过调用`putVal`实现，主要涉及两个场景下的扩容操作：1. 初始化时，链表数组的初始容量设为16，阈值设为12；2. 当存储的元素个数超过阈值时，链表数组的容量和阈值均翻倍。`putVal`方法处理键值对的插入，包括链表和红黑树的转换，确保高效的数据存取。
Dylaniou
61 5

热门文章

最新文章

  • 1
    Java技术周刊第14期：浅谈HashMap，探索JDK（集合框架）
  • 2
    HashMap原理
  • 3
    java源码-HashMap
  • 4
    为什么 HashMap 的加载因子是0.75？
  • 5
    浅谈HashMap的实现原理
  • 6
    HashMap、HashSet、TreeMap、TreeSet判断元素相同
  • 7
    Rust 笔记：Rust 语言中哈希结构（哈希映射，HashMap）、集合（哈希集，HashSet）及其使用
  • 8
    HashMap深度解析（一）
  • 9
    （周期计划-8）常用集合的源码分析：HashMap
  • 10
    java HashMap 转Object对象 工具类
  • 1
    Java面试题：请解释Java内存模型，并说明如何在多线程环境下使用synchronized关键字实现同步，阐述ConcurrentHashMap与HashMap的区别，以及它如何在并发环境中提高性能
    44
  • 2
    Redis08命令-Hash类型，也叫散列，其中value是一个无序字典，类似于java的HashMap结构，Hash结构可以将对象中的每个字段独立存储，可以针对每字段做CRUD
    61
  • 3
    如何优化Java中的HashMap性能？
    162
  • 4
    Rust HashMap详解及单词统计示例
    48
  • 5
    《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问，你都会了？
    43
  • 6
    HashMap源码
    37
  • 7
    java使用HashMap对文件进行排序并输出
    33
  • 8
    java编程hashmap详解
    44
  • 9
    HashMap扩容为什么每次都是之前的2倍
    104
  • 10
    HashMap、lru、散列表
    35

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云对象存储OSS收费标准：存储、流量和请求等多个计费项详解