精华内容
下载资源
问答
  • HashMap源码分析 —— HashMap为什么是无序的?

    千次阅读 多人点赞 2019-06-13 23:49:50
    HashMap源码解析HashMap为什么是无序的?问题:为什么说HashMap无序的?但是某种情况下看起来却好像是有序的?原因(源码分析):数据结构:功能实现最后,我们应该知道为什么HashMap无序的了吗?最后再次感谢...

    HashMapd的put方法为什么是无序的?

    参考:https://blog.csdn.net/login_sonata/article/details/76598675 (有删改和补充)

    题外话:最近有朋友问我一个问题,也是我曾经初学HashMap时问过老师的问题。所以我打算写一篇博客来回答,以前看过不少博客,但是没想过写。初次尝试,请多指教。

    问题:为什么说HashMap 是无序的?但是某种情况下看起来却好像是有序的?

    某种情况指的是下面这种情况:

    HashMap<Integer,Integer> hashMap = new HashMap<>();
         hashMap.put(1,1);
         hashMap.put(2,2);
         hashMap.put(3,3);
         hashMap.put(4,4);
         hashMap.put(5,5);
         hashMap.put(6,6);
    
     for (Integer s: hashMap.keySet()) {
        System.out.print(hashMap.get(s) + " ");
     }
    

    如果按照上面的方式向HashMap中添加数据,那输出结果肯定是:

    1 2 3 4 5 6
    

    看到这个输出结果, 有人就会对HashMap的无序产生怀疑了,这里为什么是有序的呢?
    (你也可以改变添加数据的顺序,比如先添加 “2” 再添加 “1”,最后结果还是这样)

    带着这个疑问我们再来看一个例子:

    HashMap<Integer,Integer> hashMap = new HashMap<>();
        hashMap.put(1,1);
        hashMap.put(2,2);
        hashMap.put(3,3);
        hashMap.put(4,4);
        hashMap.put(5,5);
        hashMap.put(6,6);
        hashMap.put(65536,65536);
        
    for (Integer s: hashMap.keySet()) { 
       System.out.print(hashMap.get(s) + " ");
    }
    

    我们思考一下,你觉得会输出什么? 还会是1 2 3 4 5 6 65536这样的顺序吗?

    运行结果是:1 65536 2 3 4 5 6

    看完这个例子之后,很显然HashMap是无序的,因为它有自己的一套算法。

    那我们回过来想,为什么在第一个例子中会出现HashMap有序的情况呢?

    想要知道答案就来分析HashMap源码吧。

    原因(源码分析):

    数据结构源码实现 两个方面来讲解(以JDK 1.8为例)

    数据结构:

    HashMap的数据结构由 数组 + 链表 + 红黑树(JDK 1.8版本才加入的红黑树)
    在这里插入图片描述
    我们看这幅图应该需要明白两个问题:

    1. 数据底层具体存储的元素是什么(就是上图中的小黑点是什么)?
      从源码中(HashMap类第395行)可以看到一个字段 Node[] table(即Hash桶数组),
      这个字段就是上图中的数组, Node 类型就是小黑点, Node之间通过 next字段链接成链
      表。下面是Node类型的具体代码:
     static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; // 用来定义数组索引位置
        final K key;
        V value;
        Node<K,V> next; // 链表中下一个Node
    
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
     }
    
    1. 这样存储的方式有什么优点?
      HashMap是使用哈希表来存储的,为了解决Hash冲突使用的是链地址法(相关文档: Hash讲解)。链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash(就是调用源码中的hash方法,在 源码的第337行)后,得到被扰乱的hash值,然后通过位与运算获取数组下标(调用 源码的第630行进行位与运算操作得到数组下标),最后把数据放在该数组下标链表上。

    例如程序执行下面代码:

         hashMap.put(65536,65536);
    

    系统将调用 “65536” 这个 keyhashCode() 方法得到其 hash值 (该方法适用于每个Java对象),然后再通过Hash算法的后两步运算(高位运算和取模运算,下文有介绍)来定位该键值对的存储在数组中的位置,有时两个key会定位到数组中相同的位置,表示发生了Hash碰撞(碰撞之后就会生成链表)。当然Hash算法计算结果在越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。

    如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组(Node[] table)的大小,并在此基础上设计好的hash算法减少Hash碰撞。所以好的Hash算法和扩容机制至关重要。

    在理解Hash和扩容流程之前,我们得先了解下HashMap的几个字段
    从HashMap的默认构造函数源码可知,构造函数就是对下面几个字段进行初始化:

    	int threshold;             // 扩容阈值 
    	final float loadFactor;    // 负载因子
    	transient int modCount;  // 出现线程问题时,负责及时抛异常
    	transient int size;     // HashMap中实际存在的Node数量
    

    首先,Node[] table的初始化长度length(默认值是16),Load factor为负载因子(默认值是0.75),threshold是HashMap所能容纳的最大数据量的Node(键值对)个数threshold = length * Load factor
    也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。

    结合负载因子的定义公式可知,threshold就是在此Load factorlength(数组长度)对应下允许的最大元素数目,超过这个数目就重新resize(扩容),扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,比如内存空间很多而又对时间效率要求很高,可以降低负载因子Load factor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。

    size这个字段其实很好理解,就是HashMap中实际存在的键值对数量。注意和table的长度length容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数。强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

    在HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),这是一种非常规的设计,常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数,具体证明可以参考 为什么一般hashtable的桶数会取一个素数

    这里存在一个问题,即使负载因子和Hash算法设计的再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响HashMap的性能。于是,在JDK1.8版本中,对数据结构做了进一步的优化,引入了红黑树。而当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能。

    功能实现

    HashMap的内部功能实现很多,本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入讲解。

    1. 确定哈希桶数组索引位置
      不管增加、删除、查找键值对,定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些,当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,不用遍历链表,大大优化了查询的效率。HashMap定位数组索引位置,直接决定了hash方法的离散性能。先看看源码的实现(方法一 + 方法二):
    	// 方法一,jdk1.8 & jdk1.7都有:
    	static final int hash(Object key) { 
    		int h; 
    		return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
    	} 
    
    
    	// 方法二,jdk1.7有,jdk1.8没有这个方法,把这个取消了,置换成了一行代码。
    	static int indexFor(int h, int length) {
     		return h & (length-1); 
    	}
    
    这里的Hash算法本质上就是三步:
    (1)取key的hashCode值,h = key.hashCode();
    (2) 高位参与运算,h ^ (h >>> 16);
    (3) 取模运算,h & (length-1)。

    对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,模运算的消耗还是比较大的,在HashMap中是这样做的:调用方法二来计算该对象应该保存在table数组的哪个索引处

    这个方法非常巧妙,它通过h & (table.length -1)来得到该对象的保存位,而HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

    在JDK1.8的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

    下面举例说明下,ntable[]的长度:
    在这里插入图片描述

    1. 分析HashMap的put方法
      HashMap的put方法执行过程可以通过下图来理解,自己有兴趣可以去对比源码更清楚地研究学习,源码在本文最后可以找到。
      在这里插入图片描述

    2. 扩容机制

    HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组

    首先举个例子直观感受下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。其中的哈希桶数组table的size=2, 所以key = 3、7、5,put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1,即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4,然后所有的Node重新rehash的过程。
    在这里插入图片描述

    简单说就是换一个更大的数组重新映射。下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现,我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果
    在这里插入图片描述

    元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:
    在这里插入图片描述

    因此,我们在扩充HashMap的时候,只需要看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:
    在这里插入图片描述
    这个设计省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了

    最后,我们应该知道为什么HashMap是无序的了吗?

    总而言之,就是出现了哈希冲突所以才导致无序。

    感谢我所参考文档的提供者们。

    展开全文
  • 最近遇到的一个坑-HashMap(为什么HashMap无序的) 1. 缘起-简单的demo 最近使用HashMap时候遇到一个问题 ,就是HashMap本身是无序的,怎么理解呢,可以拿如下代码来进行测试 Map<Integer, String> map = new...

    1. 缘起-简单的demo

    最近使用HashMap时候遇到一个问题 ,就是HashMap本身是无序的,怎么理解呢,可以拿如下代码来进行测试

      		Map<Integer, String> map = new HashMap<>();
            for (int i = 0; i < 10; i++) {
                map.put(i, "value");
            }
            map.forEach(((integer, value) -> {
                System.out.println(integer);
            }));
    

    看起来没问题吧,输出结果

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    

    你可能会说 ,这不正常么

    2. 缘生-意外的结果

    我们把代码稍作修改

      			Map<Integer, String> map = new HashMap<>();
            for (int i = 0; i < 10; i++) {
                map.put(10-i, "value");
            }
            map.forEach(((integer, value) -> {
                System.out.println(integer);
            }));
    

    这下在看下结果

    在我意料中应改是10 9 8 …1 ,没错吧 ,我想的是这样,但是实际上呢

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    

    很奇怪吧,HashMap是无序的, 为什么会有这种情况呢

    3. 缘解-探索为什么HashMap无序

    (debug过程,

    1. 搜索HashMap.的put方法,
    2. 点进putVal方法,
    3. 可以顺带看下put中的对key的处理过程hash()
    4. 然后就可以看到下面罗列的代码了)

    盲猜一下,HashMap在增加数据的时候,自己给数据增加了排序,所以才不是我们想要的结果了

    /**
         * Associates the specified value with the specified key in this map.
         * If the map previously contained a mapping for the key, the old
         * value is replaced.
         *
         * @param key key with which the specified value is to be associated
         * @param value value to be associated with the specified key
         * @return the previous value associated with <tt>key</tt>, or
         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with <tt>key</tt>.)
         */
        public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    
    

    看下HashMap的put方法 ,可以看出来,存储的时候会对key进行hash

    稍等片刻…等我debug找下原因

    进入putVal()方法

     /**
         * Implements Map.put and related methods.
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent if true, don't change existing value
         * @param evict if false, the table is in creation mode.
         * @return previous value, or null if none
         */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    

    可以看出map其实是一个 Node<K,V>[] tab 的数组对象

    而这边数组对象肯定是有顺序的,

    在上面代码的第而得else中可以看出

    tab[i = (n - 1) & hash])

    数组的索引是 根据 (n - 1) & hash进行计算的

    所以这个时候,其实数据在存储到HashMap的时候由于对key的hash值不同,在存储的时候时候顺序就不是固定的了

    而对key的hash算法如下(尽管我看不懂,但是我还是要贴一下代码)

    static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    

    额代码就是上面个代码

    所以说, 这样hash值不同,在存储到tab的时候顺序就不是固定的,所以综上所述,HashMap不是有序的

    4. 怎么避免想要一个有序的map

    这个时候可以使用LinkedHashMap

    LinkedHashMap在我使用的时候是有序的,毕竟其包含链表么, 链表就是,数据之间会有顺序,无论是单向链表还是双向链表,都包含,所指向的下一个节点,这次踩坑就到此为止了,下次在用Map在出现这种顺序问题,我就自己起锅炖了自己

    展开全文
  • HashMap无序

    2020-04-12 12:23:24
    HashMap无序的 一、说明 HashMap是基于哈希表Map的实现。HashMap的设计初衷主要是为了解决键值(key-value)对应的关联的,HashMap的优势是可以很快的根据键(key)找到该键对应的值(value),但是我们在使用...

                      HashMap无序,无序hashset与hashmap让其有序

     

    一、   说明

    HashMap是基于哈希表Map的实现。HashMap的设计初衷主要是为了解决键值(key-value)对应的关联的,HashMap的优势是可以很快的根据键(key)找到该键对应的值(value),但是我们在使用的过程中需要注意一下,HashMap是一种无序的存储结构。HashMap的实现是假定元素是放在一个圆形的环上,每次put进来的元素根据其hashCode计算该元素在圆环上索引,把该元素放到合适的位置。

    二、   Put和get关键方法

    public V put(K key, V value) {

        if (key == null)

               returnputForNullKey(value);

        当传入的key为null时,则直接调用putForNullKey方法,在索引为0的位置压入该value值,这也就是HashMap为什么支持压入null值。

    int hash = hash(key.hashCode());

           int i = indexFor(hash, table.length);

        这两个方法是很牛X的地方,第一个方法是根据key的hashCode利用hash方法生成一个hash值,然后通过indexFor函数获取table的索引值。

        是的,没错,HashMap就是通过table的结构来存储数据的。HashMap最牛X的地方是能根据hash值计算出正确的索引,比较深奥。下面是put的整个方法:   

    public V put(K key, V value) {
    
            if (key == null)
    
                return putForNullKey(value);
    
            int hash = hash(key.hashCode());
    
            int i = indexFor(hash, table.length);
    
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    
                Object k;
    
                if (e.hash == hash && ((k = e.key) == key ||  key.equals(k))) {
    
                    V oldValue = e.value;
    
                    e.value = value;
    
                    e.recordAccess(this);
    
                    return oldValue;
    
                }
    
            } 
    
            modCount++; 
    
            addEntry(hash, key, value, i); 
    
            return null; 
    
        } 

     

    实际上,如果插入的数据在HashMap中已经存在,则调用put函数的时候会返回oldValue。当我们在使用get函数的时候,同样是根据key的hashCode,从table中的对应索引位置提取该值并返回。

        到这里,我们可以看到HashMap是通过key的hashCode来计算索引的,与元素放入的先后顺序没有什么关系,所以我们在使用HashMap的时候,千万不要寄希望于HashMap中的数据与我们压入的数据的先后顺序一致。如果要保证压入的顺序一致,可以使用LinkedHashMap对象。

    三、   HashMap与HashTable的区别

    1.  HashMap允许put进来一个null元素,HashTable则不允许,put进来null值后抛异常

    2.  HashMap的一些操作(如put)没有同步,而HashTable的很多操作都是加上同步操作(增加了synchronized关键字)

    无序hashset与hashmap让其有序

    今天迭代hashmap时,hashmap并不能按照put的顺序,迭代输出值。用下述方法可以:

    HashMap<String,String> hashmap = new LinkedHashMap<String,String>();

    方法一:

    把HashSet保存在ArrayList里,再用Collections.sort()方法比较

    private void doSort(){  
      
            final HashSet<Integer> va = new HashSet<Integer>();  
      
            va.add(2007111315);  
      
            va.add(2007111314);  
      
            va.add(2007111318);  
      
            va.add(2007111313);  
      
            final List<Integer> list = new ArrayList<Integer>();  
      
            for(final Integer value : va){  
      
                list.add(value);  
      
            }  
      
            Collections.sort(list);  
      
            System.out.println(list);  
      
        }  
    1. 方法二:

      把这个HashSet做为构造参数放到TreeSet中就可以排序了

    2. final TreeSet ts = new TreeSet(va);  
        
             ts.comparator();  
        
             System.out.println(ts); 
       

      HashSet和TreeSet 

      1. HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key

      2. Map的key和Set都有一个共同的特性就是集合的唯一性.TreeMap更是多了一个排序的功能.

      3. hashCode和equal()是HashMap用的, 因为无需排序所以只需要关注定位和唯一性即可.

       a. hashCode是用来计算hash值的,hash值是用来确定hash表索引的.

       b. hash表中的一个索引处存放的是一张链表, 所以还要通过equal方法循环比较链上的每一个对象 才可以真正定位到键值对应的Entry.

       c. put时,如果hash表中没定位到,就在链表前加一个Entry,如果定位到了,则更换Entry中的value,并返回旧value

      4. 由于TreeMap需要排序,所以需要一个Comparator为键值进行大小比较.当然也是用Comparator定位的.

       a. Comparator可以在创建TreeMap时指定

       b. 如果创建时没有确定,那么就会使用key.com

    Java中ArrayList和Vector的区别

    是的, 这是一个太多太多人遇到过, 讨论过, 解释过的问题.
    为了加深自己的记忆, 还是决定写一篇来记录下他.

    首先想说的是:
    Vector是在Collections API之前就已经产生了的, 而ArrayList是在JDK1.2的时候才作为Collection framework的一部分引入的.  它们都是在内部用一个Obejct[]来存储元素的.

    ok, 现在来说他们的差别:
    1. 线程安全
    Vector是同步的, 而ArrayList不是.
    因为Vector是同步的, 所以它是线程安全的.
    同样, 因为Vecotr是同步的, 所以他需要额外的开销来维持同步锁, 所以它要比ArrayList要慢.(理论上来说)

    当然, 如果你对ArrayList有偏好, 你也可以用Collection.synchronizedList(List)来得到一个线程安全的List.

    2. 容量增长
    Vector允许用户设置capacityIncrement这样在每次需要扩充数组的size的时候, Vector会尝试按照预先设置的capacityIncrement作为增量来设置, 而ArrayList则会把数组的大小扩大一倍.

    比如现在同样一个长度为10的Vector和ArrayList, 我们把Vector的capacityIncrement设为1
    那么我们在插入第11个对象的时候, Vector会将长度变成11, 然后分配空间, 然后将对象添加进去, 而ArrayList则会分配20个对象的空间, 然后将对象添加进去.

    如果capacityIncrement设为0或者负值, Vector就会做和ArrayList一样, 每次都将数组大小扩大一倍.

    3. 性能比较
    刚刚在上面已经说过了, 由于Vector是同步的, 而ArrayList不是, 所以Vector的性能要比ArrayList要稍第一点, 用性能换安全嘛.

    不过, 据Jack ShiraziOnJava上的一篇文章来看, 似乎这并不是什么问题, 他认为对于现在的JVM来说, 这两个类在同步这个问题上的性能差异, 甚至还不如每次跑测试的时候环境变化引起的差异大.
    Consequently Vector is thread-safe, and ArrayList isn't. This makes ArrayList faster than Vector. For some of the latest JVMs the difference in speed between the two classes is negligible: strictly speaking, for these JVMs the difference in speed between the two classes is less than the variation in times obtained from tests comparing the performance of these classes. ---- The Performance of Java's Lists

    这样看来, 性能上的差别应该不大.

    So, as a conclusion.
    结论和网上大多数人得到的结论一样:
    在一般情况下, 还是鼓励用ArrayList的, 如果你有同步控制的需要, 那就用Vector吧, 也懒得用Collection.synchronizedList(List)再去转一次了, 除非非这样不可.. 不然还是顺应潮流, 毕竟, 代码是写给人看的. 在无伤大雅的情况下, 按照common的法则来写, 无疑会让看代码的人更快理解. :)

     

    java中hashmap和hashtable的区别

    1、  继承和实现区别

    Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现。

    2、  线程安全不同

    HashTable的方法是同步的,HashMap是未同步,所以在多线程场合要手动同步HashMap。

    3、  对null的处理不同

    HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。即HashTable 不允许null值其实在编译期不会有任何的不一样,会照样执行,只是在运行期的时候Hashtable中设置的话回出现空指针异常。HashMap允许 null值是指可以有一个或多个键所对应的值为null。当get()方法返回null值时,即可以表示 HashMap中没有该键,也可以表示该键所对应的值为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键,而应该用containsKey()方法来判断。

    4、  方法不同

    HashTable有一个contains(Object value),功能和containsValue(Object value)功能一样。
    5、HashTable使用Enumeration,HashMap使用Iterator。

    6、HashTable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。
    7、哈希值的使用不同,HashTable直接使用对象的hashCode,代码是这样的:
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    而HashMap重新计算hash值,而且用与代替求模:
    int hash = hash(k);
    int i = indexFor(hash, table.length);
    static int hash(Object x) {
      int h = x.hashCode();
      h += ~(h << 9);
      h ^= (h >>> 14);
      h += (h << 4);
      h ^= (h >>> 10);
      return h;
    }
    static int indexFor(int h, int length) {
      return h & (length-1);
    }

     

    区别

    Hashtable

    Hashmap

    继承、实现

    Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable,Serializable

    HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable,Serializable

     

    线程同步

    已经同步过的可以安全使用

    未同步的,可以使用Colletcions进行同步Map Collections.synchronizedMap(Map m)

    对null的处理

     

    Hashtable table = new Hashtable();

    table.put(null, "Null");

    table.put("Null", null);

    table.contains(null);

    table.containsKey(null);

    table.containsValue(null);

    后面的5句话在编译的时候不会有异常,可在运行的时候会报空指针异常具体原因可以查看源代码

    public synchronized V put(K key, V value) {

         // Make sure the value is not null

      if (value == null) {

             throw new NullPointerException();

    }

    HashMap map = new HashMap();

    map.put(null, "Null");

    map.put("Null", null);

    map.containsKey(null);

    map.containsValue(null);

    以上这5条语句无论在编译期,还是在运行期都是没有错误的.

    在HashMap中,null可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为null。当get()方法返回null值时,即可以表示 HashMap中没有该键,也可以表示该键所对应的值为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键,而应该用containsKey()方法来判断。

    增长率

       protected void rehash() {

          int oldCapacity = table.length;

          Entry[] oldMap = table;

          int newCapacity = oldCapacity * 2 + 1;

          Entry[] newMap = new Entry[newCapacity];

          modCount++;

          threshold = (int)(newCapacity * loadFactor);

          table = newMap;

          for (int i = oldCapacity ; i-- > 0 ;) {

              for (Entry<K,V> old = oldMap[i] ; old != null ; ) {

               Entry<K,V> e = old;

               old = old.next;

               int index = (e.hash & 0x7FFFFFFF) % newCapacity;

               e.next = newMap[index];

               newMap[index] = e;

              }

          }

        }

     

    void addEntry(int hash, K key, V value, int bucketIndex) {

          Entry<K,V> e = table[bucketIndex];

            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

            if (size++ >= threshold)

                resize(2 * table.length);

        }

     

    哈希值的使用

    HashTable直接使用对象的hashCode,代码是这样的:

    public synchronized booleancontainsKey(Object key) {

          Entry tab[] = table;

          int hash = key.hashCode();

          int index = (hash & 0x7FFFFFFF) % tab.length;

          for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {

              if ((e.hash == hash) && e.key.equals(key)) {

               return true;

              }

          }

          return false;

        }

    HashMap重新计算hash值,而且用与代替求模

          public boolean containsKey(Object key) {

                  Object k = maskNull(key);

                  int hash = hash(k.hashCode());

                  int i = indexFor(hash, table.length);

                  Entry e = table[i];

                  while (e != null) {

                      if (e.hash == hash && eq(k, e.key))

                          return true;

                      e = e.next;

                  }

                  return false;

              }

     

     

    参考:https://www.iteye.com/blog/xiaowei-qi-epro-com-cn-1989541

    展开全文
  • HashMap无序的测试

    2021-03-20 17:19:21
    HashMap无序的,无序的,无序的 我们在做测试的时候有时候会出现, 我创建一个HashMap, 但打印的时候,好像它是按照key来排序了一样,如下例 HashMap<Integer, String> ihm = new HashMap<>(); ihm.put...

    HashMap是无序的,无序的,无序的
    我们在做测试的时候有时候会出现, 我创建一个HashMap, 但打印的时候,好像它是按照key来排序了一样,如下例

    	    HashMap<Integer, String> ihm = new HashMap<>();
            ihm.put(3,"haha");
            ihm.put(8,"hehe");
            ihm.put(1,"gege");
            ihm.put(7,"meme");
            ihm.put(6,"gaga");
            Set<Integer> iss = ihm.keySet();
            Set<Map.Entry<Integer, String>> entries = ihm.entrySet();
            for (Map.Entry<Integer, String> entry : entries) {
                System.out.println(entry.getKey()+"----"+entry.getValue());
            }
    
    		打印结果是这样的
    		1----gege
    		3----haha
    		6----gaga
    		7----meme
    		8----hehe
    

    上面好像是有序的, 但是这只是一种巧合, 我们不能就简单的认为它是的序的, 下面我们对上面的代码做一点修改, 我们再增加一些key-value, 就可以看出问题了

            HashMap<Integer, String> ihm = new HashMap<>();
            ihm.put(3,"haha");
            ihm.put(8,"hehe");
            ihm.put(1,"gege");
            ihm.put(7,"meme");
            ihm.put(6,"gaga");
            ihm.put(333,"eke");
            ihm.put(88,"lll");
            ihm.put(66,"mmm");
            Set<Integer> iss = ihm.keySet();
            Set<Map.Entry<Integer, String>> entries = ihm.entrySet();
            for (Map.Entry<Integer, String> entry : entries) {
                System.out.println(entry.getKey()+"----"+entry.getValue());
            }
    		
    		打印结果是下面的样子了
    		1----gege
    		66----mmm
    		3----haha
    		6----gaga
    		7----meme
    		8----hehe
    		88----lll
    		333----eke
    

    可以看到,并不是我们想象的那种顺序了, 所以记得结论, HashMap 是无序的

    展开全文
  • HashMap无序序列

    2014-10-10 20:11:40
    HashMap的设计初衷主要是为了解决键值(key-value)对应的关联的,HashMap的优势是可以很快的根据键(key)找到该键对应的值(value),但是我们在使用的过程中需要注意一下,HashMap是一种无序的存储结构。HashMap...
  • hashmap无序的但是实际输出有序?

    千次阅读 2020-01-14 21:16:34
    但是HashMap存值的时候会根据key的hashCode()来计算存储的位置(位置是散列的,所以无序); 你使用的key是String类型,String重写的hashCode()计算出的位置,遍历的时候恰好是"001","003","005"的顺序; PS:...
  • 说hashmap遍历出来的是随机无序的。 我自己试验了一下。每次都是有序的啊。 添加的顺序如下: Map map1=new HashMap(); map1.put("5","str5"); map1.put("3","str3"); map1.put("1","str1"); map1....
  • 但是为什么HashMap还是会按照key的值进行排序呢? 如下:明明key的值的输入顺序是 2 3 1,HashMap内部存储的顺序却是 1 2 3. **原因就是:**这里的无序和我们理解的无序不一样,这里所谓无序的意思就是,不按照你...
  • HashMap无序的,插入的顺序和最后遍历输出的顺序不同。实验代码如下: import javax.xml.bind.SchemaOutputResolver; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Map; import ...
  • 由于map集合时无序的,我们接触到最多的集合中只有List集合时有序的.通过查了查,发现有一种map(LinkedHashMap)集合时有序的,可以做到按照用户放入集合的顺序取出集合中的元素. LinkedHashMap介绍: 简单的介绍...
  • 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源码分析,为什么是无序的?

    千次阅读 2017-01-17 22:51:54
    疑问:HashMap无序的,怎么做到的?先看一个现象Map, Integer> m = new HashMap(); for(int i=0; i; i++) { m.put("key"+i, i); } System.out.println(m);结果{key1=1, key2=2, key0=0, key5=5, key6=6, key3=3,...
  • HashMap无序性与LinkedHashMap的有序性

    千次阅读 2019-11-26 12:17:00
    HashMap存储元素是无序的,在通过Iterator遍历元素时也是无序的。 LinkedHashMap LinkedHashMap存储元素是无序的,在通过Iterator遍历元素时是有序的;put数据的顺序和输出顺序是一致的。 LinkedHashMap遍历...
  • 最近在跟进码表功能,由于在某些场景(如:下拉列表)下需要获取有序的数据集合,而负责详细设计的同学并没有将排序功能纳入详细设计。ID、CREATE_TIME考虑到新增、删除等操作不...调整 LinkedHashMap ,结果显示正常。
  • 今天学习Map集合时书上说HashMap无序的,TreeMap是有序的(有序无序是针对key的),但是实际去敲的时候发现不是这样,有时HashMap是有序的,有时TreeMap是无序的。于是就做了以下测试来探究: 测试代码: //第一...
  • HashMap的put方法为什么无序

    千次阅读 2018-05-04 11:04:01
    HashMap的put方法为什么无序 参考文章 [1]https://blog.csdn.net/qq_34908167/article/details/79269488 [2]https://www.cnblogs.com/liujinhong/p/6576543.html [3]...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,246
精华内容 20,098
关键字:

为什么说hashmap是无序的