精华内容
下载资源
问答
  • HashMap是不是有序的,LinkedHashMap是不是有序的,详细解说一下
  • HashMap有序LinkedHashMap实现对比

    万次阅读 2017-07-05 12:29:51
    LinkedHashMap:LinkedHashMap简单来说是一个有序HashMap,其是HashMap的子类,HashMap是无序的。接下来我们通过对比分析HashMap和LinkedHashMap来了解一下LinkedHashMap是如何实现有序的。首先HashMap及子类...

    LinkedHashMap:LinkedHashMap简单来说是一个有序的HashMap,其是HashMap的子类,HashMap是无序的。接下来我们通过对比分析HashMap和LinkedHashMap来了解一下LinkedHashMap是如何实现有序的。首先HashMap及子类LinkedHashMap都提供了一个数组。

     Node<K,V>[] table  
     不同key的hash值是分布在这个数组中的,key值不同,经过hash计算的hash值相同的话节点会作为相同hash值节点的next节点
     class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    }
    LinkedHashMap提供的节点添加了两个属性before和after节点,用来生成双向循环列表的,这样每次在Map中添加值都会追加到链表的最后一位,这样就按照插入顺序生成了一个链表
    class Entry<K,V> extends HashMap.Node<K,V> {
            Entry<K,V> before, after;
            Entry(int hash, K key, V value, Node<K,V> next) {
                super(hash, key, value, next);
            }
    }
    在LinkedHashMap中添加了链表的head和tail节点

    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;


    总结:LinkedHashMap实现有序key值的关键就是根据插入顺序另外维护了一个按照插入顺序作为标记的双向循环列表,这样在获取所有数据进行循环获取时获取到的数据就是有序的数据。


    LinkedHashMap从迭代器获取到的数据就是有序的

     LinkedHashIterator() {
                next = head;
                expectedModCount = modCount;
                current = null;
            }
    
            public final boolean hasNext() {
                return next != null;
            }
    
            final LinkedHashMap.Entry<K,V> nextNode() {
                LinkedHashMap.Entry<K,V> e = next;
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                if (e == null)
                    throw new NoSuchElementException();
                current = e;
    			//获取双向链表的下一个数据
                next = e.after;
                return e;
            }
    
    HashMap从迭代器中获取到的数据就是hash值的相对排序的数据

    HashIterator() {
                expectedModCount = modCount;
                Node<K,V>[] t = table;
                current = next = null;
                index = 0;
                if (t != null && size > 0) { // advance to first entry
                    do {} while (index < t.length && (next = t[index++]) == null);
                }
            }
    
            public final boolean hasNext() {
                return next != null;
            }
    
            final Node<K,V> nextNode() {
                Node<K,V>[] t;
                Node<K,V> e = next;
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                if (e == null)
                    throw new NoSuchElementException();
    			//从不断的从table中获取数据,table
                if ((next = (current = e).next) == null && (t = table) != null) {
                    do {} while (index < t.length && (next = t[index++]) == null);
                }
                return e;
            }
    总结:从上面两段HashMap和LinkedHashMap迭代器实现就可以看出LinkedHashMap的实现原理了,简单来说就是访问队列。




    展开全文
  • Hash算法 在说HashMap之前先来了解一下Hash算法。在数据结构中学习过线性表,我们知道在线性表中查询一个值最坏的情况可能是从头遍历到尾,其平均时间复杂度为O(n),并不理想,而hash表能将查询的时间复杂度降为O(1),...

    Hash算法

    在说HashMap之前先来了解一下Hash算法。在数据结构中学习过线性表,我们知道在线性表中查询一个值最坏的情况可能是从头遍历到尾,其平均时间复杂度为O(n),并不理想,而hash表能将查询的时间复杂度降为O(1),因为Hash算法会通过hash函数计算出地址直接取值,其查询次数只有一次。

    通过下面例子简单了解一下hash表的查询方式,下面是一个hash表,首先假设hash函数为n%10,hash函数计算出来的结果就是其hash表中该元素的地址,所以10、13和26的存储结果如下图。

    b22e10f53669803adc708e6ce4c83efc.png

    可能实际的hash函数能很好地避免地址的冲突,但是还是有地址冲突的可能性,比如10和20。java中hashMap解决方式是"链地址法",如下图,将hash值冲突的值使用链表连接起来,这样查询到地址0的时候就会依次比较10和20,看到底哪个才是要找的。

    9e4ca63c015ee3b0fb32831fd7ff6e44.png

    HashMap

    下面来了解什么是HashMap,"**Map集合即Key-Value的集合,前面加个Hash,即散列,无序的。所以HashMap即散着的,无序的Key-Value集合**",这是最初我看到的一个对我个人而言比较好理解的解释。当我们使用的hashMap的键值为对象的时候可能就要重写hashCode和eqals。

    先看下面一段代码

    public class User {private String name;private String password;public User() {super();}public User(String name, String passed) {super();this.name = name;this.passed = passed;}public class Demo {public static void main(String[] args) {User user1=new User("name", "passed");User user2=new User("name", "passed");//定义hashMapHashMap hashmap=new HashMap();//添加hashmap.put(user1, "value1");//通过user2获取添加的valueString str=hashmap.get(user2);System.out.println("输出结果:"+str);}}

    通过代码可知,实体类User中只有两个属性name和password,Main函数中声明了两个User的实例,他们的两个属性都是相同的,那我们现在希望使用user2取出user1对应的value值,看下是否能成功。

    运行结果:

    输出结果:null

    为什么不是想象的结果呢。因为当我们向hashmap添加user1时,hashmap首先会调用User的hashCode来计算hash值作为地址,因为本例中没有重写hashCode方法,所以hashmap是调用的Object的hashCode方法来计算hash值,Object中hashCode计算出来的hash值其实就是对象的地址,所以user1与user2存储的的地址肯定不同,下面就重写User的hashCode

    @Overridepublic int hashCode() {final int prime = 31;int result = 1;result = prime * result + ((name == null) ? 0 : name.hashCode());result = prime * result + ((passed == null) ? 0 : passed.hashCode());return result;}

    运行结果:

    输出结果:null

    运行结果还是null,既然重写了hashCode方法,寻找user2时候理论上是能够正确寻找到user1存储地址的,为什么结果还是null?这里就要了解一下HashMap找到地址后动作。前面已经说过,java中HashMap解决hash值冲突,使用了链地址法,也就是在通过user2获取user1的value的时候并不是通过User重写的hashCode计算出user2的地址后就直接从该地址中取相应的值,而是还要调用equals方法来进行比较,这就和没有重写hashCode造成错误的原因类似了,没有重写equals方法,就要被迫调用Object类的equals方法,而Object类的equals方法是直接比较两个对象的内存地址,所以输出结果是null。

    现在重写equals方法

    @Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;User other = (User) obj;if (name == null) {if (other.name != null)return false;} else if (!name.equals(other.name))return false;if (passed == null) {if (other.passed != null)return false;} else if (!passed.equals(other.passed))return false;return true;}

    运行结果:

    输出结果:value1

    成功。

    总结

    由上面的分析可知,当键值为对象类型的时候就需要重写hashCode和equals方法。

    展开全文
  • 在有些特定的场景下,我们需要使用到有序的键值对——LinkedHashMap 比如我下面的场景,要求添加ip+端口号的键值对,同时接口要求端口从0开始。 我们比较一下haspMap和LinkedHashMap的区别,直接看代码结果: ...

    在有些特定的场景下,我们需要使用到有序的键值对——LinkedHashMap

    比如我下面的场景,要求添加ip+端口号的键值对,同时接口要求端口从0开始。

    我们比较一下haspMap和LinkedHashMap的区别,直接看代码结果:

     public static void main(String[] args) {
    //-------HashMap
    Map<String,Integer> map=new HashMap<>();
    map.put("127.0.0.1",0);
    map.put("127.0.0.2",1);
    map.put("127.0.0.3",2);
    map.put("127.0.0.4",3);
    Set<String> ips = map.keySet();
    for (String ip :ips ) {
      Integer port = map.get(ip);
      System.out.println("key:"+ip+"----------value:"+port);
    }
    System.out.println("--------------------------------------");
    //-------LinkedHashMap
    Map<String,Integer> linkMap=new LinkedHashMap();
    linkMap.put("127.0.0.1",0);
    linkMap.put("127.0.0.2",1);
    linkMap.put("127.0.0.3",2);
    linkMap.put("127.0.0.4",3);
    Set<String> ips2 = linkMap.keySet();
    for (String ip :ips2 ) {
      Integer port = linkMap.get(ip);
      System.out.println("key:"+ip+"===========value:"+port);
    }
    

    }
    结果:

    在这里插入图片描述
    结果明显HaspMap根据输出是无序的,而LindedHashMap输出是有序的。
    看了一下LindedHashMap的实现:
    在这里插入图片描述
    在这里插入图片描述
    他底层也是用的哈希表,还用了链表作为排序,所以产生的结果对比HaspMap多个顺序

    展开全文
  • hashmap有序吗?

    2021-02-04 09:28:19
    1.hashmap有序吗? 不是有序的. 2.有没有有顺序的Map实现类? 有TreeMap和LinkedHashMap。 3.TreeMap和LinkedHashMap是如何保证它的顺序的? LinkedHashMap 是根据元素增加或者访问的先后顺序进行排序,而 TreeMap是...

    1.hashmap有序吗?
    不是有序的.

    2.有没有有顺序的Map实现类?

    有TreeMap和LinkedHashMap。

    3.TreeMap和LinkedHashMap是如何保证它的顺序的?

    LinkedHashMap 是根据元素增加或者访问的先后顺序进行排序,而 TreeMap是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。

    4.哪个的有序实现比较好?

    TreeMap TreeMap则实现了 SortedMap 接口。

    5.你觉得还有没有比它更好或者更高效的实现方式?

    参照TreeMap的value排序,我们一样的也可以实现HashMap的排序

    展开全文
  • 在LeetCode刷题的时候,在一道返回 字符串中最早出现的只出现一次的字符下标的题目中,使用大HashMap的遍历方式,我选择了使用map.entrySet()获取节点集合的方式进行遍历。 题目和代码如下: 在一个字符串(0<=...
  • 今天学习Map集合时书上说HashMap是无序的,TreeMap是有序的(有序无序是针对key的),但是实际去敲的时候发现不是这样,有时HashMap有序的,有时TreeMap是无序的。于是就做了以下测试来探究: 测试代码: //第一...
  • HashMap无序 LinkedHashMap有序

    千次阅读 2015-08-04 17:12:28
    HashMap为什么无序?  HashMap数据结构是table[entry], entry是一个链表结构,数据的每个元素是一个链表。不同key,但具有相同hashcode便会落在table[hashcode]的链表上。 即,hashMap顺序是由key的hash值决定...
  • HashMap的到底是有序还是无序

    万次阅读 多人点赞 2020-06-27 11:18:54
    HashMap的到底是有序还是无序前提问题背景HashMap的一些特性问题分析结论再结论 前提 首先说明:HashMap不保证插入顺序,但是循环遍历时,输出顺序是不会改变的。 代码说明: public class HashMapTest { public ...
  • hashmap的无序和有序

    万次阅读 多人点赞 2018-12-02 17:55:41
    上代码 public static void main(String[] args) { ... map = new HashMap&lt;&gt;(); map.put("3","1"); map.put("4","1"); map.put("1","1&
  • 今天迭代hashmap时,hashmap并不能按照put的顺序,迭代输出值。用下述方法可以: HashMap<String,String> hashmap = new LinkedHashMap<String,String>(); HashSet的内容如何排序 方法一:...
  • HashMap<String, String> map2 = new HashMap<>(map1.size());
  • 1、集合是否有序指的是:存取是否有序。map内保存内容的顺序不一定与放进去顺序一致,这叫无序。内容不变,取出来顺序一定不变,这叫有序。 2、如果集合中的内容有排序的需求,尽量使用有序集合,比如LinkedHashMap...
  • HashMap

    2018-08-11 23:06:50
    1.  Map接口有两个实现类:HashMap TreeMap HashTable(线程安全) ...1. HashMap有序的还是无序的 ? LinkedHashMap? TreeMap? 2. HashMap 容量 还有扩容机制 3. 为什么是线程不安全的? ...
  • 我们知道HashMap这个数据结构根据一个指定的值查找的时间复杂度是O(1),但是有一个问题就是HashMap是无序的比如你放进去第一个值A,但是遍历Map获取到对应的位置可能是第五个位置。那有时候我们会要求能像Map一样直接...
  • HashMap问题汇总

    万次阅读 2019-09-18 09:20:44
    就比如问你:HashMap 是不是有序的? 你回答不是有序的。那面试官就会可能继续问你,有没有有序的Map实现类呢? 你如果这个时候说不知道的话,那这块问题就到此结束了。如果你说有TreeMap和LinkedHashMap。 那么...
  • java有序hashmap

    2017-02-16 15:06:00
    使用LinkedHashmap可以构建一个有序的map   引用:http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html
  • HashMap为什么是无序?   HashMap的数据结构是table[entry],entry是一个链表结构,数据的每个元素是一个链表。不同key,但是具有相同hashcode会落在table[hashcode]的链表上 当使用iterator遍历时,使用如下code...
  • HashMap无序与LinkedHashMap有序

    千次阅读 2011-11-10 16:51:07
    HashMap为什么是无序?   HashMap的数据结构是table[entry],entry是一个链表结构,数据的每个元素是一个链表。不同key,但是具有相同hashcode会落在table[hashcode]的链表上 当使用iterator遍历时,使用如下code...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 84,993
精华内容 33,997
关键字:

hashmap是不是有序的