文档章节

HashMap,LinkedHashMap,TreeMap的有序性

小杰java
 小杰java
发布于 2018/03/08 10:06
字数 703
阅读 18
收藏 0

HashMap 是将 Key 做 Hash 算法,然后将 Hash 值映射到内存地址,直接取得 Key 所对应的数据。在 HashMap 中,底层数据结构使用的是数组,所谓的内存地址即数组的下标索引。HashMap 的高性能需要保证以下几点:

  1. Hash 算法必须是高效的;
  2. Hash 值到内存地址 (数组索引) 的算法是快速的;
  3. 根据内存地址 (数组索引) 可以直接取得对应的值。

HashMap 实际上是一个链表的数组。基于 HashMap 的链表方式实现机制,只要 HashCode() 和 Hash() 方法实现得足够好,能够尽可能地减少冲突的产生,那么对 HashMap 的操作几乎等价于对数组的随机访问操作,具有很好的性能。但是,如果 HashCode() 或者 Hash() 方法实现较差,在大量冲突产生的情况下,HashMap 事实上就退化为几个链表,对 HashMap 的操作等价于遍历链表,此时性能很差。

HashMap 的一个功能缺点是它的无序性,被存入到 HashMap 中的元素,在遍历 HashMap 时,其输出是无序的。如果希望元素保持输入的顺序,可以使用 LinkedHashMap 替代。

LinkedHashMap 继承自 HashMap,具有高效性,同时在 HashMap 的基础上,又在内部增加了一个链表,用以存放元素的顺序。

HashMap 通过 hash 算法可以最快速地进行 Put() 和 Get() 操作。TreeMap 则提供了一种完全不同的 Map 实现。从功能上讲,TreeMap 有着比 HashMap 更为强大的功能,它实现了 SortedMap 接口,这意味着它可以对元素进行排序。TreeMap 的性能略微低于 HashMap。如果在开发中需要对元素进行排序,那么使用 HashMap 便无法实现这种功能,使用 TreeMap 的迭代输出将会以元素顺序进行。LinkedHashMap 是基于元素进入集合的顺序或者被访问的先后顺序排序,TreeMap 则是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。

LinkedHashMap 是根据元素增加或者访问的先后顺序进行排序,而 TreeMap 则根据元素的 Key 进行排序。

 

测试代码:

package mapKeySet;  
  
import java.util.HashMap;  
import java.util.LinkedHashMap;  
import java.util.Map;  
import java.util.TreeMap;  
  
/** 
 * 2015年4月9日下午3:33:44 
 * @version 1.0 
 */  
public class KeySetTest {  
    public static void main(String[] args) {  
        Map<String, String> map = new HashMap<String, String>();  
        map.put("a", "1");  
        map.put("b", "2");  
        map.put("c", "3");  
        map.put("d", "4");  
          
        System.out.print("HashMap:");  
        for(String key : map.keySet()) {  
            System.out.print(map.get(key) + " ");  
        }  
          
        Map<String, String> linkedMap = new LinkedHashMap<String, String>();  
        linkedMap.put("a", "1");  
        linkedMap.put("b", "2");  
        linkedMap.put("c", "3");  
        linkedMap.put("d", "4");  
          
        System.out.print("LinkedHashMap:");  
        for(String key : linkedMap.keySet()) {  
            System.out.print(linkedMap.get(key) + " ");  
        }  
          
        Map<String, String> treeMap = new TreeMap<String, String>();  
        treeMap.put("a", "1");  
        treeMap.put("b", "2");  
        treeMap.put("c", "3");  
        treeMap.put("d", "4");  
          
        System.out.print("TreeMap:");  
        for(String key : treeMap.keySet()) {  
            System.out.print(treeMap.get(key) + " ");  
        }  
    }  
}  

输出结果为:

HashMap:4 2 3 1 LinkedHashMap:1 2 3 4 TreeMap:1 2 3 4  

 

本文转载自:http://blog.csdn.net/zhuhao717/article/details/47444763

上一篇: 7. redis.conf解说
下一篇: javashop
小杰java
粉丝 13
博文 51
码字总数 31927
作品 0
西安
后端工程师
私信 提问
LinkedHashMap源码分析-java8

得益于昨天网易的面试,所以重新认识了一个集合,回来后赶紧做了分析,继续努力~ps:面试官真的很nice,希望好运~ 1.特性分析 说明:因为LinkedHashMap单词太长,所以以下都用LHM替代 基本...

caoxiaohong1005
2018/04/12
0
0
HashMap,TreeMap以及LinkedHashMap的区别

HashMap:HashMap数据是无序的,根据键的hashCode进行数据的存取,对数据的访问速度非常快,在map中插入删除 和定位元素,hashMap无疑是最好的选择, TreeMap:里面的数据是有序的,底层是一个...

J星星点灯
2018/02/03
0
0
重识java-LinkedHashMap

重识java-LinkedHashMap 使用场景 如果需要使用的Map中的key无序,选择;如果要求key有序,则选择。但是选择TreeMap就会有性能问题,因为TreeMap的get操作的时间复杂度是的,相比于HashMap的...

hgfgoodcreate
2016/03/09
70
0
LinkedHashMap了解一下

前言 LinkedHashMap类继承图 LinkedHashMap简述 LinkedHashMap的属性 LinkedHashMap的构造函数 LinkedHashMap常见Api解析 总结 前言 本文使用用的是jdk1.8 LinkedHashMap类继承图 我们先来了...

HikariCP
2018/05/11
0
0
Java容器源码分析-HashMap vs TreeMap vs LinkedHashMap

这里我采用的分析方式是帖子博客加上自己翻看jdk源码。有些情况下写一些测试的算法小例子加深印象。我这里只描述一下自己的总结想法 上一篇文章我们研究了set接口下的几个容器,由于其Set集合...

贾浩v
2017/10/19
26
0

没有更多内容

加载失败,请刷新页面

加载更多

3_数组

3_数组

行者终成事
23分钟前
3
0
经典系统设计面试题解析:如何设计TinyURL(二)

原文链接:https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR 编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助...

APEMESH
今天
7
0
使用logstash同步MySQL数据到ES

概述   在生成业务常有将MySQL数据同步到ES的需求,如果需要很高的定制化,往往需要开发同步程序用于处理数据。但没有特殊业务需求,官方提供的logstash就很有优势了。   在使用logstas...

zxiaofan666
今天
10
0
X-MSG-IM-分布式信令跟踪能力

经过一周多的鏖战, X-MSG-IM的分布式信令跟踪能力已基本具备, 特点是: 实时. 只有要RX/TX就会实时产生信令跟踪事件, 先入kafka, 再入influxdb待查. 同时提供实时sub/pub接口. 完备. 可以完整...

dev5
今天
7
0
OpenJDK之CyclicBarrier

OpenJDK8,本人看的是openJDK。以前就看过,只是经常忘记,所以记录下 图1 CyclicBarrier是Doug Lea在JDK1.5中引入的,作用就不详细描述了,主要有如下俩个方法使用: await()方法,如果当前线...

克虏伯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部