Java中Map的排序问题详解

Map的种类

在Java中,Map的主要作用是存储键值对。由于是根据键得到值,所以不允许键重复。它主要有如下几个类别:

HashMap:

最常用的Map,它根据键的HashCode值存储数据,根据键可以直接获取它的值,具有很快的访问速度,遍历时,取得数据的顺序是完全随机的。HashMap最多只允许一条记录的键为Null;允许多条记录的值为Null;HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步,可以用Collections的synchronizedMap方法使HashMap具有同步的能力,或者使用ConcurrentHashMap。Hashtable与HashMap类似,它继承自Dictionary类,不同的是:它不允许记录的键或者值为空;它支持线程的同步,即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

LinkedHashMap

保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的.也可以在构造时用带参数,按照应用次数排序。在遍历的时候会比HashMap慢,不过有种情况例外,当HashMap容量很大,实际数据较少时,遍历起来可能会比LinkedHashMap慢,因为LinkedHashMap的遍历速度只和实际数据有关,和容量无关,而HashMap的遍历速度和他的容量有关。

TreeMap

实现SortMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator 遍历TreeMap时,得到的记录是排过序的。

按键排序

从上面Map的种类介绍我们可以看出,TreeMap是自带按键排序的功能的,只需要在创建的时候同时实现一个Compare的接口就可以了,例子如下:

private static void sort_by_key(){
    Map<Integer, Integer> treeMap = new TreeMap<>(new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return o2-o1; //倒序.这里说明一下,如果返回负值,则o1先输出,反之则o2
      }
    });

    //填充数据
    for(int i = 0; i < 100;i++){
      int key = (int)(10000*Math.random());
      int value = (int)(10000*Math.random());
      treeMap.put(key, value);
    }
    outMap(treeMap);
  }

public static void outMap(Map<Integer, Integer> map){
    for(Integer integer:map.keySet()){
      System.out.println("key="+integer+"  value="+map.get(integer));
    }
}
/* 结果如下:
key=9977  value=80
key=9684  value=7108
key=9422  value=1706
key=9264  value=1210
key=9248  value=4758
key=9024  value=7048
key=8892  value=3124
key=8879  value=6414
key=8814  value=8171
key=8728  value=1538
key=8513  value=4956
key=8462  value=5617
key=8355  value=8912
*/

从上面可以看出,按键排序是不难的,而安置排序就比较麻烦一些,需要将Map转一下。

按值排序

由于Java中Map并没有此功能,所以我们需要自己实现。思路如下:

Java中List是可以使用compare接口的。
Map实际上就是Entry<>的集合
那么使用List<Entry<>>就可以实现排序
将排好序的元素再插入到LinkedMap中

代码实现如下:

 private static Map<Integer, Integer> sortMap(Map<Integer, Integer> linkedMap) {

    List<Map.Entry<Integer, Integer>> cache = new ArrayList<>(linkedMap.entrySet());

    //重写比较函数
    Collections.sort(cache,new Comparator<Map.Entry<Integer, Integer>>() {
      @Override
      public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
        //若返回值小于0,则o1在o2前面
        return o2.getValue()-o1.getValue();
      }
    });

    Map<Integer, Integer> resultMap = new LinkedHashMap<>();
    //将结果插入LinkedMap然后返回
    for(int i = 0; i < cache.size();i++){
      resultMap.put(cache.get(i).getKey(), cache.get(i).getValue());
    }
    return resultMap;
  }
/*结果:
7965  9966
1067  9963
1720  9833
3257  9738
3934  9578
777  9348
1924  9315
3472  9270
3649  9114
5892  9078
*/

这样,按值排序和按键排序就都可以实现了。

时间: 2016-01-27

Java8 HashMap的实现原理分析

前言:Java8之后新增挺多新东西,在网上找了些相关资料,关于HashMap在自己被血虐之后痛定思痛决定整理一下相关知识方便自己看.图和有些内容参考的这个文章:http://www.jb51.net/article/80446.htm HashMap的存储结构如图:一个桶(bucket)上的节点多于8个则存储结构是红黑树,小于8个是单向链表. 1:HashMap的一些属性 public class HashMap<k,v> extends AbstractMap<k,v> impl

java如何对map进行排序详解(map集合的使用)

今天做统计时需要对X轴的地区按照地区代码(areaCode)进行排序,由于在构建XMLData使用的map来进行数据统计的,所以在统计过程中就需要对map进行排序. 一.简单介绍Map 在讲解Map排序之前,我们先来稍微了解下map.map是键值对的集合接口,它的实现类主要包括:HashMap,TreeMap,Hashtable以及LinkedHashMap等.其中这四者的区别如下(简单介绍): HashMap:我们最常用的Map,它根据key的HashCode 值来存储数据,根据key可以直接

java中HashMap的原理分析

我们先来看这样的一道面试题: 在 HashMap 中存放的一系列键值对,其中键为某个我们自定义的类型.放入 HashMap 后,我们在外部把某一个 key 的属性进行更改,然后我们再用这个 key 从 HashMap 里取出元素,这时候 HashMap 会返回什么? 文中已给出示例代码与答案,但关于HashMap的原理没有做出解释. 1. 特性 我们可以用任何类作为HashMap的key,但是对于这些类应该有什么限制条件呢?且看下面的代码: public class Person { priva

Java HashMap的工作原理

大部分Java开发者都在使用Map,特别是HashMap.HashMap是一种简单但强大的方式去存储和获取数据.但有多少开发者知道HashMap内部如何工作呢?几天前,我阅读了java.util.HashMap的大量源代码(包括Java 7 和Java 8),来深入理解这个基础的数据结构.在这篇文章中,我会解释java.util.HashMap的实现,描述Java 8实现中添加的新特性,并讨论性能.内存以及使用HashMap时的一些已知问题. 内部存储 Java HashMap类实现了Map<K

Java Map 按照Value排序的实现方法

Map是键值对的集合接口,它的实现类主要包括:HashMap,TreeMap,Hashtable以及LinkedHashMap等. •TreeMap:基于红黑树(Red-Black tree)的 NavigableMap 实现,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法. •HashMap的值是没有顺序的,它是按照key的HashCode来实现的,对于这个无序的HashMap我们要怎么来实现排序呢?参照TreeMap的va

java HashMap通过value反查key的代码示例

复制代码 代码如下: import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.Set;public class MapValueGetKey {  public static void main(String[] args) {    Map map = new HashMap<>();    map.put(1,&qu

java多线程之线程同步七种方式代码示例

为何要使用同步?  java允许多线程并发控制,当多个线程同时操作一个可共享的资源变量时(如数据的增删改查),     将会导致数据不准确,相互之间产生冲突,因此加入同步锁以避免在该线程没有完成操作之前,被其他线程的调用,     从而保证了该变量的唯一性和准确性. 1.同步方法  即有synchronized关键字修饰的方法.     由于java的每个对象都有一个内置锁,当用此关键字修饰方法时,     内置锁会保护整个方法.在调用该方法前,需要获得内置锁,否则就处于阻塞状态.     代码

Java语言Consistent Hash算法学习笔记(代码示例)

本文研究的主要是ConsistentHashing算法代码. 一致性哈希(Consistent Hash) 协议简介 一致性哈希算法在1997年由麻省理工学院提出(参见0),设计目标是为了解决因特网中的热点(Hot pot)问题,初衷和CARP十分类似.一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用. 哈希算法 一致性哈希提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件: 平衡性(Balance) 平衡性是指哈希的结果能够尽可能分

Java编程Iterator迭代器设计原理及实现代码示例

我们知道迭代器(Iterator)是一种对象,它能够用来遍历标准模板库容器中的部分或全部元素.那么Iterator迭代器的设计原理是什么呢?迭代器问什么定义了一个借口,而不是一个类呢? 我们假设迭代器迭代数据的功能定义为了一个类,那么,会有这样的问题.不同的集合,由于数据结构不一样,所以他们的存储方式也是不一样的.也就是说,迭代器获取的时候,获取的方式是变化的,也就是不固定的.所以把这种方式定义为具体的实现是不合理的. 无论何种集合,他们肯定都有获取的功能,而且不知道什么时候就没有数据了.所有他

Java编程小实例—数字时钟的实现代码示例

本文的实例是Java编程实现一个数字时钟,代码测试可用,练练手吧.代码如下: package me.socketthread; import java.awt.Color; import java.awt.Dimension; import java.awt.Font; import java.awt.Graphics; import java.awt.Graphics2D; import java.util.Calendar; import java.util.GregorianCalenda

Java设计模式之访问者模式使用场景及代码示例

Java设计模式访问者模式 模式概念 访问者模式表示一个作用于某对象结构中的各元素的操作,它使你可以在不改变各元素类的前提下定义作用于这些元素的新操作.访问者模式适用于数据结构相对稳定算法又易变化的系统,若系统数据结构对象易于变化,则不适合使用访问者模式.访问者模式的优点是增加操作很容易,因为增加操作意味着增加新的访问者. Visitor应用场景 一定会有的疑问:visitor和iterator的区别: visitor可以访问不同的对象(只需要在Element定义对应的accept),但是Ite

java数据结构之树基本概念解析及代码示例

Java中树的存储结构实现 一.树 树与线性表.栈.队列等线性结构不同,树是一...节点与节点之间的父子关系,可以为每个节点增加一个parent域,用以记录该节点的父点 树是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点组成一个具有层次关系的集合.把 它叫做"树"是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的. 树定义和基本术语 定义 树(Tree)是n(n≥0)个结点的有限集T,并且当

Java自带的加密类MessageDigest类代码示例

MessageDigest 类 MessageDigest 类为应用程序提供信息摘要算法的功能,如 MD5 或 SHA 算法.信息摘要是安全的单向哈希函数,它接收任意大小的数据,并输出固定长度的哈希值. MessageDigest 对象开始被初始化.该对象通过使用 update()方法处理数据.任何时候都可以调用 reset()方法重置摘要.一旦所有需要更新的数据都已经被更新了,应该调用digest() 方法之一完成哈希计算. 对于给定数量的更新数据,digest 方法只能被调用一次.在调用 d

Java实现判断浏览器版本与类型简单代码示例

简单的Java获取浏览器版本和类型方法,不是很完美,但是可以用: 希望大家加以完善! public static void main(String[] args) { String agent=request.getHeader("User-Agent").toLowerCase(); System.out.println(agent); System.out.println("浏览器版本:"+getBrowserName(agent)); } public Str

Java压缩文件工具类ZipUtil使用方法代码示例

本文实例通过Java的Zip输入输出流实现压缩和解压文件,前一部分代码实现获取文件路径,压缩文件名的更改等,具体如下: package com.utility.zip; import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import