Java8 HashMap键与Comparable接口小结

目录
  • Java8 HashMap键与Comparable接口
    • 这也是我在面试的时候经常问面试者的问题
  • 容器(LinkedList、HashMap、Compare)
    • 1.内部比较器|自然排序
    • 2.外部比较器|自定义排序

Java8 HashMap键与Comparable接口

最容易使 HashMap 发生哈希冲突的方法是什么呢?我们可以创建一个类,让它的哈希函数返回一个最糟糕的结果 —— 比如一个常数。

这也是我在面试的时候经常问面试者的问题

哈希方法返回常数会造成什么结果?有很多次面试者会回答说 map 集合里会有且仅有一个元素,因为 map 中的旧元素总会被新的覆盖。这个回答当然是错误的。

哈希冲突并不会导致 HashMap 覆盖一个已经存在于集合中的元素,这种情况只会在使用者试图向集合中放入两个元素,并且它们的键对于 equal() 方法是相等的时候才会发生。

键不相等但又会产生哈希冲突的不同元素最终会以某种数据结构存储在 HashMap 的同一个桶中(注意,在这种情况下,因为插入和查找的操作都要耗费更长的时间,所以整体的性能就会受到影响)。

首先,我们用一个小程序来模拟哈希冲突。下面的写法可能比较夸张,因为它造成的冲突比现实中多得多,但这个程序对于证实哈希冲突的条件还是很重要的。

我们使用一个 Person 对象作为 map 的键,以字符串作为值。下面是 Person 的具体实现,有一个 firstName 字段,一个 lastName 字段和一个 ID 属性,其中 ID 属性以 UUID 对象表示。

public class Person {
    private String firstName;
    private String lastName;
    private UUID id;
    public Person(String firstName, String lastName, UUID id) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.id = id;
    }
    @Override
    public int hashCode() {
        return 5;
    }
    @Override
    public boolean equals(Object obj) {
        // ... pertty good equals here taking into account the id field...
    }
    // ...
}

现在我们可以开始制造一些冲突。

private static final int LIMIT = 500_000;
private void fillAndSearch() {
     Person person = null;
     Map<Person, String> map = new HashMap<>();
     for (int i=0;i<LIMIT;i++) {
        UUID randomUUID = UUID.randomUUID();
        person = new Person("fn", "ln", randomUUID);
        map.put(person, "comment" + i);
     }
     long start = System.currentTimeMillis();
     map.get(person);
     long stop = System.currentTimeMillis();
     System.out.println(stop-start+" millis");
}

上面的代码在一台高性能计算机上运行了两个半小时。其中,最后的查找操作耗费了大约 40 毫秒。现在我们对 Person 类进行修改:使它实现 Comparable 接口,并且添加了下面的方法:

@Override
public int compareTo(Person person) {
    return this.id.compareTo(person.id);
}

再一次运行之前的程序,这一次在我的机器上它耗费的时间少于 1 分钟。其中,最终的查找操作耗费的时间接近为 0 毫秒 —— 比之前提高了 150 倍!

就像前面说的,Java 8 做了很多优化,其中也包括HashMap 类。在 Java 7 中,两个不同的元素,如果它们的键产生了冲突,那么会被存储在同一个链表中。而从 Java 8 开始,如果发生冲突的频率大于某一个阈值(8),并且 map 的容量超过了另一个阈值(64),整个链表就会被转换成一个二叉树。

原来如此!所以,对于没有实现 Comparable 的键,最终的树是不平衡的;而对于实现了 Comparable 的键,其二叉树就会是高度平衡的。事实是这样吗?不是。HashMap 内部是红黑树,也就是说它总是平衡的。我通过反射机制,查看了最终的树结构。对于拥有 50000 个元素(不敢让数字更大了)的 HashMap 来说,两种不同的情况下(实现或是不实现 Comparable 接口)树的高度都是 19 。

那么,为什么之前的实验结果会有那么大的差别呢?原因在于,当 HashMap 想要为一个键找到对应的位置时,它会首先检查新键和当前检索到的键之间是否可以比较(也就是实现了 Comparable 接口)。如果不能比较,它就会通过调用 tieBreakOrder(Object a,Object b) 方法来对它们进行比较。这个方法首先会比较两个键对象的类名,如果相等再调用 System.identityHashCode 方法进行比较。这整个过程对于我们要插入的 500000 个元素来说是很耗时的。另一种情况是,如果键对象是可比较的,整个流程就会简化很多。因为键对象自身定义了如何与其它键对象进行比较,就没有必要再调用其他的方法,所以整个插入或查找的过程就会快很多。值得一提的是,在两个可比的键相等时(compareTo 方法返回 0)的情况下,仍然会调用 tieBreakOrder 方法。

总而言之,在 Java 8 的 HashMap 里,如果一个桶里存放了大量的元素,它在达到阈值时就会被转换为一棵红黑树,对于实现了 Comparable 接口的键来说,插入或删除的操作会比没有实现 Comparable 接口的键更简单。

通常,如果一个桶不会发生那么多次冲突的话,这整个机制不会带来多大的性能提升,但起码现在我们对 HashMap 的内部原理有了更多了解。

容器(LinkedList、HashMap、Compare)

HashSet的底层是HashMap,TreeSet的底层是TreeMap。

TreeSet中存放自定义类时应该先指定比较的规则(compare)

1.内部比较器|自然排序

要当前比较的类型实现一个借口Comparable接口,重写compareTo方法,方法的内部制定比较规则, 硬编码习惯,不够灵活,每次修改源代码。

public class Student implements Comparable<Student>{
    .........
    //重写compareTo方法
    @Override
    public int compareTo(Student o) {
        return this.stuName.length()-o.stuName.length();
    }
}

2.外部比较器|自定义排序

使用任何一个实现类实现一个接口Comparator,重写compare方法,方法的内部制定比较规则。

public class CompareDemo {
    public static void main(String[] args) {
        Comparator<Student> comparator=new Home();
        //lambda表达式
        comparator=(Student o1, Student o2)->{return o1.getStuName().length()-o2.getStuName().length();};
        //指定使用参数比较器
        //TreeSet(Comparator<? super E> comparator)
        TreeSet treeSet=new TreeSet(comparator);
        treeSet.add(new Student("张三爸",40,158));
        treeSet.add(new Student("张三",20,168));
        treeSet.add(new Student("张三爷爷",60,178));
        System.out.println(treeSet);
    }
}
class Home implements Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2) {
        return o1.getStuName().length()-o2.getStuName().length();
    }
}

HashMap应该注意的事项 :

手写HashMap应该注意对key值进行比较,如果key相同则新的value覆盖旧的value。table是上图中横向的数组,默认初始值为16,计算key在数组中的位置时使用:key.hashcode%table.length,这种方式效率较低,一般使用 key.hashcode&(table.length-1)。

class MyHashMap{
    private Node [] table;
    private int size;
    public void put(Object key, Object value) {
        if(table==null){
            table=new Node[16];
        }
        int hash=getHash(key);
        Node node=table[hash];//获取他在数组上的位置
        Node newNode=new Node(hash,key,value,null);
        if(node==null){
            table[hash]=newNode;
            size++;
        }else{
            while(true){
                //进行key值的比较
                if(node.getKey().equals(key)){
                    node.setValue(value);
                    break;
                }
                if(node==null){
                    break;
                }
                node=node.getNext();
            }
            node.setNext(newNode);
            size++;
        }
    }
    public int getHash(Object key){
        return key.hashCode()&(table.length-1);
    }
    @Override
    public String toString() {
        StringBuilder sbr=new StringBuilder("{");
        for(Node node:table){
            while(node!=null){
                sbr.append(node.getKey()+"--->"+node.getValue()+",");
                node=node.getNext();
            }
        }
        sbr.setCharAt(sbr.length()-1,'}');
        return sbr.toString();
    }
}
  • Properties:用来代替hashMap,实现了Map接口,线程安全的
  • HashTable:可以代替hashMap,线程安全

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Java案例之HashMap集合存储学生对象并遍历

    一.需求:创建一个HashMap集合,键是学号(String),值是学生对象(Student),存储三个键值对元素,并遍历 分析: 1.定义学生类 2.创建HashMap集合对象 3.创建学生对象 4把学生添加到集合中 5.遍历集合 public class StudentDemo {   public static void main(String[] args) {       //创建Map集合对象       Map<String,Student> m=new HashMap<S

  • Java集合-HashMap

    目录 概述 重要的参数 put函数的实现 get函数的实现 hash函数的实现 RESIZE的实现 概述 ①以数组+链表+红黑树实现.主要用来处理具有键值对特征的数据.②当链表长度大于阈值(或者红黑树的边界值,默认为 8 )并且当前数组的长度大于 64 时,此时此索引位置上的所有数据改为使用红黑树存储.③补充:将链表转换成红黑树前会判断,即便阈值大于 8,但是数组长度小于 64,此时并不会将链表变为红黑树,而是选择逬行数组扩容.④每个Node节点存储着用来定位数据索引位置的hash值,K键,V值

  • java哈希算法HashMap经典面试题目汇总解析

    目录 1.HashMap的数据结构? 2.HashMap的工作原理? 3.当两个对象的hashCode相同会发生什么? 4.你知道hash的实现吗?为什么要这样实现? 5.为什么要用异或运算符? 6.HashMap的table的容量如何确定? 7.HashMap中put方法的过程? 8.数组扩容的过程? 9.为什么不一直使用红黑树? 10.说说你对红黑树的见解? 11.jdk8中对HashMap做了哪些改变? 12.HashMap,LinkedHashMap,TreeMap有什么区别? 13.H

  • Java 详解Map集合之HashMap和TreeMap

    目录 HashMap 创建HashMap 添加元素 访问元素 删除元素 TreeMap 创建TreeMap 添加元素 访问元素 删除元素 HashMap.TreeMap区别 Map接口储存一组成对的键-值对象,提供key(键)到value(值)的映射,Map中的key不要求有序,不允许重复.value同样不要求有序,但可以重复.最常见的Map实现类是HashMap,他的储存方式是哈希表,优点是查询指定元素效率高. Map接口被HashMap和TreeMap两个类实现. HashMap HashM

  • Java中HashMap与String字符串互转的问题解决

    目录 背景: 原因: 背景: 当我们有需求将HashMap转为Json格式的String时,切记不要使用HashMap的toString()方法,需要使用FastJson/Gson将HashMap转为String.如果使用toString()方法进行转换时,是无法将字符串再转为HashMap的.它只会出现序列化报错: demo代码: HashMap<String, String> dataMap = new HashMap<>(4); dataMap.put("key1&

  • Java手写简易版HashMap的使用(存储+查找)

    HashMap的基本结构 package com.liuyuhe; public class Node { int hash; Object key; Object value; Node next; } package com.liuyuhe; public class MyHashMap { Node[] table; //位桶数组 int size; //存放键值对的个数 public MyHashMap() { table=new Node[16]; } } put()方法存储键值对 p

  • Java8 HashMap键与Comparable接口小结

    目录 Java8 HashMap键与Comparable接口 这也是我在面试的时候经常问面试者的问题 容器(LinkedList.HashMap.Compare) 1.内部比较器|自然排序 2.外部比较器|自定义排序 Java8 HashMap键与Comparable接口 最容易使 HashMap 发生哈希冲突的方法是什么呢?我们可以创建一个类,让它的哈希函数返回一个最糟糕的结果 —— 比如一个常数. 这也是我在面试的时候经常问面试者的问题 哈希方法返回常数会造成什么结果?有很多次面试者会回答说

  • 浅析Java中comparator接口与Comparable接口的区别

    Comparable 简介 Comparable 是排序接口. 若一个类实现了Comparable接口,就意味着"该类支持排序".  即然实现Comparable接口的类支持排序,假设现在存在"实现Comparable接口的类的对象的List列表(或数组)",则该List列表(或数组)可以通过 Collections.sort(或 Arrays.sort)进行排序. 此外,"实现Comparable接口的类的对象"可以用作"有序映射(如

  • java 实现Comparable接口排序,升序、降序、倒叙

    本人由于项目开发中需要对查询结果list进行排序,这里根据的是每一个对象中的创建时间降序排序.本人讲解不深,只实现目的,如需理解原理还需查阅更深的资料. 1.实现的效果 2.创建排序的对象 package com.practice.test.comparable; import java.util.Date; /** * 描述:要比较的对象 * * @author cui * @create 2018-12-18 14:07 */ public class MySortBean implemen

  • 一文带你掌握Java8中Lambda表达式 函数式接口及方法构造器数组的引用

    目录 函数式接口概述 函数式接口示例 1.Runnable接口 2.自定义函数式接口 3.作为参数传递 Lambda 表达式 内置函数式接口 Lambda简述 Lambda语法 方法引用 构造器引用 数组引用 函数式接口概述 只包含一个抽象方法的接口,称为函数式接口. 可以通过 Lambda 表达式来创建该接口的对象. 可以在一个接口上使用 @FunctionalInterface 注解,这样做可以检查它是否是一个函数式接口.同时 javadoc 也会包含一条声明,说明这个接口是一个函数式接口.

  • java中实现Comparable接口实现自定义排序的示例

    实例如下所示: class Student implements Comparable{ String name; int gpa; @Override public int compareTo(Object arg0) { // TODO Auto-generated method stub Student s = (Student)arg0; if(gpa == s.gpa) return name.compareTo(s.name); else if(gpa < s.gpa) return

  • 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比较器Comparable接口与Comaprator接口的深入分析

    java的比较器有两类,分别是Comparable接口和Comparator接口.在为对象数组进行排序时,比较器的作用非常明显,首先来讲解Comparable接口.让需要进行排序的对象实现Comparable接口,重写其中的compareTo(T o)方法,在其中定义排序规则,那么就可以直接调用java.util.Arrays.sort()来排序对象数组,实例如下: 复制代码 代码如下: class Student implements Comparable<Student>{    priv

  • Java8 HashMap扩容算法实例解析

    这篇文章主要介绍了Java8 HashMap扩容算法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java8的HashMap扩容过程主要就是集中在resize()方法中 final Node<K,V>[] resize() { // ...省略不重要的 } 其中,当HashMap扩容完毕之后,需要对原有的数据进行转移.因为容量变大了,部分元素的位置因此要变更,因而出现了下面的这个转移过程. 转移过程大致是:依次从旧数组里取值,然后从

  • JAVA中Comparable接口和自定义比较器示例讲解

    自然排序 TreeSet集合在存储数据时有一定的顺序,它会将一些数据进行比较,比较调用的是comparaTo()方法,该方法是在Comparable中定义的,自然排序要求TreeSet集合中存储的数据必须实现Comparable接口,并且重写ComparaTo()方法 public class 自然排序 { public static void main(String[] args) { //定义一个TreeSet集合 TreeSet treeSet = new TreeSet(); Teach

  • JAVA8之函数式编程Function接口用法

    从这章开始,会介绍几个常用的函数式接口工具,首先先来看下这个大家族: 首先从Function接口开始介绍 一. 概述 该接口顾名思义,函数的意思,就像是数学,是给定一个参数然后返回结果.该类方法如下: package java.util.function; import java.util.Objects; @FunctionalInterface public interface Function<T, R> { R apply(T t); default <V> Functio

随机推荐