精华内容
下载资源
问答
  • HashMap实现原理分析

    千次阅读 2017-04-13 12:04:30
    版权声明:本文为博主原创文章,未经博主...HashMap的存取实现 1put2get3null key的存取4确定数组indexhashcode tablelength取模5table初始大小 解决hash冲突的办法再散列rehash过程 1. HashMap的数据结构
     
    

    1. HashMap的数据结构

    数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。

          数组

    数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难

    链表

    链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。

    哈希表

    那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表。哈希表((Hash table既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便。

      哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:




      从上图我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

      HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。

      首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

        /**
         * The table, resized as necessary. Length MUST Always be a power of two.
         */

        transient Entry[] table;

    2. HashMap的存取实现

         既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:

    // 存储时:
    int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
    int index = hash % Entry[].length;
    Entry[index] = value;

    // 取值时:
    int hash = key.hashCode();
    int index = hash % Entry[].length;
    return Entry[index];
     

    1)put

     
    疑问:如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险?

      这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止,HashMap的大致实现,我们应该已经清楚了。

     public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value); //null总是放在数组的第一个链表中
            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;
                //如果key在链表中已存在,则替换为新value
                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;

        }

     

    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); //参数e, 是Entry.next
        //如果size超过threshold,则扩充table大小。再散列
        if (size++ >= threshold)
                resize(2 * table.length);
    }

      当然HashMap里面也包含一些优化方面的实现,这里也说一下。比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?HashMap里面设置一个因子,随着map的size越来越大,Entry[]会以一定的规则加长长度。

    2)get

     public V get(Object key) {
            if (key == null)
                return getForNullKey();
            int hash = hash(key.hashCode());
            //先定位到数组元素,再遍历该元素处的链表
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                    return e.value;
            }
            return null;
    }

     

    3)null key的存取

    null key总是存放在Entry[]数组的第一个元素。

       private V putForNullKey(V value) {
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }
     
        private V getForNullKey() {
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null)
                    return e.value;
            }
            return null;
        }
     
     
     
     

    4)确定数组index:hashcode % table.length取模

    HashMap存取时,都需要计算当前key应该对应Entry[]数组哪个元素,即计算数组下标;算法如下:

       /**
         * Returns index for hash code h.
         */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }
     
    按位取并,作用上相当于取模mod或者取余%。
    这意味着数组下标相同,并不表示hashCode相同。
     

    5)table初始大小

     
      public HashMap(int initialCapacity, float loadFactor) {
            .....
            // Find a power of 2 >= initialCapacity
            int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;
            this.loadFactor = loadFactor;
            threshold = (int)(capacity * loadFactor);
            table = new Entry[capacity];
            init();
        }
     

    注意table初始大小并不是构造函数中的initialCapacity!!

    而是 >= initialCapacity的2的n次幂!!!!

    ————为什么这么设计呢?——

    3. 解决hash冲突的办法

    1. 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
    2. 再哈希法
    3. 链地址法
    4. 建立一个公共溢出区

    Java中hashmap的解决办法就是采用的链地址法。

     

    4. 再散列rehash过程

    当哈希表的容量超过默认容量时,必须调整table的大小。当容量已经达到最大可能值时,那么该方法就将容量调整到Integer.MAX_VALUE返回,这时,需要创建一张新表,将原表的映射到新表中。

       /**
         * Rehashes the contents of this map into a new array with a
         * larger capacity.  This method is called automatically when the
         * number of keys in this map reaches its threshold.
         *
         * If current capacity is MAXIMUM_CAPACITY, this method does not
         * resize the map, but sets threshold to Integer.MAX_VALUE.
         * This has the effect of preventing future calls.
         *
         * @param newCapacity the new capacity, MUST be a power of two;
         *        must be greater than current capacity unless current
         *        capacity is MAXIMUM_CAPACITY (in which case value
         *        is irrelevant).
         */
        void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return;
            }
            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable);
            table = newTable;
            threshold = (int)(newCapacity * loadFactor);

        }

     

        /**
         * Transfers all entries from current table to newTable.
         */
        void transfer(Entry[] newTable) {
            Entry[] src = table;
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) {
                Entry<K,V> e = src[j];
                if (e != null) {
                    src[j] = null;
                    do {
                        Entry<K,V> next = e.next;
                        //重新计算index
                        int i = indexFor(e.hash, newCapacity);
                        e.next = newTable[i];
                        newTable[i] = e;
                        e = next;
                    } while (e != null);
                }
            }

        }

    展开全文
  • 主要介绍了Java HashMap实现原理分析,帮助大家更好的理解和使用Java,感兴趣的朋友可以了解下
  • HashMap实现原理分析及简单实现一个HashMap

    万次阅读 多人点赞 2017-03-20 11:17:41
    HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道HashMap和Hashtable之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考察的深度很深。这题经常...

    HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道HashMap和Hashtable之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考察的深度很深。这题经常出现在高级或中高级面试中。投资银行更喜欢问这个问题,甚至会要求你实现HashMap来考察你的编程能力。ConcurrentHashMap和其它同步集合的引入让这道题变得更加复杂。让我们开始探索的旅程吧!

    先来些简单的问题

    “你用过HashMap吗?” “什么是HashMap?你为什么用到它?”

    几乎每个人都会回答“是的”,然后回答HashMap的一些特性,譬如HashMap可以接受null键值和值,而Hashtable则不能;HashMap是非synchronized;HashMap很快;以及HashMap储存的是键值对等等。这显示出你已经用过HashMap,而且对它相当的熟悉。但是面试官来个急转直下,从此刻开始问出一些刁钻的问题,关于HashMap的更多基础的细节。面试官可能会问出下面的问题:

    “你知道HashMap的工作原理吗?” “你知道HashMap的get()方法的工作原理吗?”

    你也许会回答“我没有详查标准的Java API,你可以看看Java源代码或者Open JDK。”“我可以用Google找到答案。”

    但一些面试者可能可以给出答案,“HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。”这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点,或者错误的认为仅仅只在bucket中存储值的话,你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确,也显示出面试者确实知道hashing以及HashMap的工作原理。但是这仅仅是故事的开始,当面试官加入一些Java程序员每天要碰到的实际场景的时候,错误的答案频现。下个问题可能是关于HashMap中的碰撞探测(collision detection)以及碰撞的解决方法:

    “当两个对象的hashcode相同会发生什么?” 从这里开始,真正的困惑开始了,一些面试者会回答因为hashcode相同,所以两个对象是相等的,HashMap将会抛出异常,或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法,并告诉他们两个对象就算hashcode相同,但是它们可能并不相等。一些面试者可能就此放弃,而另外一些还能继续挺进,他们回答“因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理,虽然有很多种处理碰撞的方法,这种方法是最简单的,也正是HashMap的处理方法。但故事还没有完结,面试官会继续问:

    “如果两个键的hashcode相同,你如何获取值对象?” 面试者会回答:当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket,他给出答案:将会遍历链表直到找到值对象。面试官会问因为你并没有值对象去比较,你是如何确定确定找到值对象的?除非面试者直到HashMap在链表中存储的是键值对,否则他们不可能回答出这一题。

    其中一些记得这个重要知识点的面试者会说,找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。完美的答案!

    许多情况下,面试者会在这个环节中出错,因为他们混淆了hashCode()和equals()方法。因为在此之前hashCode()屡屡出现,而equals()方法仅仅在获取值对象的时候才出现。一些优秀的开发者会指出使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。

    如果你认为到这里已经完结了,那么听到下面这个问题的时候,你会大吃一惊。“如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?”除非你真正知道HashMap的工作原理,否则你将回答不出这道题。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

    如果你能够回答这道问题,下面的问题来了:“你了解重新调整HashMap大小存在什么问题吗?”你可能回答不上来,这时面试官会提醒你当多线程的情况下,可能产生条件竞争(race condition)。

    当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。这个时候,你可以质问面试官,为什么这么奇怪,要在多线程的环境下使用HashMap呢?:)

    热心的读者贡献了更多的关于HashMap的问题:

    1. 为什么String, Interger这样的wrapper类适合作为键? String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。
    2. 我们可以使用自定义的对象作为键吗? 这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。
    3. 我们可以使用CocurrentHashMap来代替Hashtable吗?这是另外一个很热门的面试题,因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。

    我个人很喜欢这个问题,因为这个问题的深度和广度,也不直接的涉及到不同的概念。让我们再来看看这些问题设计哪些知识点:

    • hashing的概念
    • HashMap中解决碰撞的方法
    • equals()和hashCode()的应用,以及它们在HashMap中的重要性
    • 不可变对象的好处
    • HashMap多线程的条件竞争
    • 重新调整HashMap的大小

    总结

    HashMap的工作原理

    HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

    当两个不同的键对象的hashcode相同时会发生什么? 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。

    因为HashMap的好处非常多,我曾经在电子商务的应用中使用HashMap作为缓存。因为金融领域非常多的运用Java,也出于性能的考虑,我们会经常用到HashMap和ConcurrentHashMap。

    简单实现:

    public class CustomHashMap<K, V> {
    
    	private class Entry<K, V> {
    		int hash;
    		K key;
    		V value;
    		Entry<K, V> next;
    
    		Entry(int hash, K key, V value, Entry<K, V> next) {
    			this.hash = hash;
    			this.key = key;
    			this.value = value;
    			this.next = next;
    		}
    	}
    
    	private static final int DEFAULT_CAPACITY = 1 << 4;
    
    	private Entry<K, V>[] table;
    
    	private int capacity;
    
    	private int size;
    
    	public CustomHashMap() {
    		this(DEFAULT_CAPACITY);
    	}
    
    	public CustomHashMap(int capacity) {
    		if (capacity < 0) {
    			throw new IllegalArgumentException();
    		} else {
    			table = new Entry[capacity];
    			size = 0;
    			this.capacity = capacity;
    		}
    	}
    
    	public int size() {
    		return size;
    	}
    
    	public boolean isEmpty() {
    		return size == 0 ? true : false;
    	}
    
    	private int hash(K key) {
    		double tmp = key.hashCode() * (Math.pow(5, 0.5) - 1) / 2;
    		double digit = tmp - Math.floor(tmp);
    		return (int) Math.floor(digit * capacity);
    	}
    
    	public void put(K key, V value) {
    		if (key == null) {
    			throw new IllegalArgumentException();
    		}
    		int hash = hash(key);
    		Entry<K, V> nEntry = new Entry<K, V>(hash, key, value, null);
    		Entry<K, V> entry = table[hash];
    		while (entry != null) {
    			if (entry.key.equals(key)) {
    				entry.value = value;
    				return;
    			}
    			entry = entry.next;
    		}
    		nEntry.next = table[hash];
    		table[hash] = nEntry;
    		size++;
    	}
    
    	public V get(K key) {
    		if (key == null) {
    			throw new IllegalArgumentException();
    		}
    		int hash = hash(key);
    		Entry<K, V> entry = table[hash];
    		while (entry != null) {
    			if (entry.key.equals(key)) {
    				return entry.value;
    			}
    			entry = entry.next;
    		}
    		return null;
    	}
    
    	public static void main(String[] args) {
    		CustomHashMap<String, String> map = new CustomHashMap<String, String>();
    		map.put("1", "11");
    		map.put("1", "22");
    		map.put("3", "33");
    		System.out.println(map.get("1"));
    	}
    
    }




    展开全文
  • 总结HashMap实现原理分析

    万次阅读 多人点赞 2018-03-30 21:40:13
    一、底层数据结构 在JDK1.6,JDK1.7中,HashMap采用位桶+链表实现,即使用链表处理冲突,同一hash值的键值对会被放在同一个位桶里,当桶中元素较多时,通过key值查找的...二、HashMap实现原理: JDK1.7中的Ha...

    一、底层数据结构

    在JDK1.6,JDK1.7中,HashMap采用位桶+链表实现,即使用链表处理冲突,同一hash值的键值对会被放在同一个位桶里,当桶中元素较多时,通过key值查找的效率较低。

    而JDK1.8中,HashMap采用位桶+链表+红黑树实现,当链表长度超过阈值(8),时,将链表转换为红黑树,这样大大减少了查找时间。

    二、HashMap的实现原理:

    JDK1.7中的HashMap

    HashMap底层维护一个数组,数组中的每一项都是一个Entry

    transient Node<k,v>[] table;//存储(位桶)的数组</k,v>  

    我们向 HashMap 中所放置的对象实际上是存储在该数组当中;

    而Map中的key,value则以Entry的形式存放在数组中

    static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;
            int hash;

    而这个Entry应该放在数组的哪一个位置上(这个位置通常称为位桶或者hash桶,即hash值相同的Entry会放在同一位置,用链表相连),是通过key的hashCode来计算的。

    final int hash(Object k) {
            int h = 0;
            h ^= k.hashCode();
    
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

    通过hash计算出来的值将会使用indexFor方法找到它应该所在的table下标:

    static int indexFor(int h, int length) {
            return h & (length-1);//length=2 的整数次幂
        }

    这个方法其实相当于对table.length取模。

    这里哈希值与上(length-1),length=传入的容量是16的话,16-1=15,二进制1111,即对h取低四位,从而对应0-15个位桶
    即无论我们指定的容量为多少,构造方法都会将实际容量设为不小于指定容量的2的次方的一个数,且最大值不能超过2的30次方

    当两个key通过hashCode计算相同时,则发生了hash冲突(碰撞),HashMap解决hash冲突的方式是用链表。

    当发生hash冲突时,则将存放在数组中的Entry设置为新值的next(这里要注意的是,比如A和B都hash后都映射到下标i中,之前已经有A了,当map.put(B)时,将B放到下标i中,A则为B的next,所以新值存放在数组中,旧值在新值的链表上)

    所以当hash冲突很多时,HashMap退化成链表。

    总结一下map.put后的过程:

    当向 HashMap 中 put 一对键值时,它会根据 key的 hashCode 值计算出一个位置, 该位置就是此对象准备往数组中存放的位置。

    如果该位置没有对象存在,就将此对象直接放进数组当中;如果该位置已经有对象存在了,则顺着此存在的对象的链开始寻找(为了判断是否是否值相同,map不允许

    private V putForNullKey(V value) {
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }

    当size大于threshold时,会发生扩容。 threshold等于capacity*load factor

    void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }

    jdk7中resize,只有当 size>=threshold并且 table中的那个槽中已经有Entry时,才会发生resize。即有可能虽然size>=threshold,但是必须等到每个槽都至少有一个Entry时,才会扩容。还有注意每次resize都会扩大一倍容量

    hashmap 原理图如下:
    这里写图片描述
    这里写图片描述

    JDK1.8中的HashMap

    一直到JDK7为止,HashMap的结构都是这么简单,基于一个数组以及多个链表的实现,hash值冲突的时候,就将对应节点以链表的形式存储。

    这样子的HashMap性能上就抱有一定疑问,如果说成百上千个节点在hash时发生碰撞,存储一个链表中,那么如果要查找其中一个节点,那就不可避免的花费O(N)的查找时间,这将是多么大的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下,链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。

    JDK7中HashMap采用的是位桶+链表的方式,即我们常说的散列链表的方式,而JDK8中采用的是位桶+链表/红黑树(有关红黑树请查看红黑树)的方式,也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候,这个链表就将转换成红黑树。

    JDK8中,当同一个hash值的节点数不小于8时,将不再以单链表的形式存储了,会被调整成一颗红黑树(上图中null节点没画)。这就是JDK7与JDK8中HashMap实现的最大区别。

    接下来,我们来看下JDK8中HashMap的源码实现。

    1.位桶数组

    JDK中Entry的名字变成了Node,原因是和红黑树的实现TreeNode相关联。

    transient Node<k,v>[] table;//存储(位桶)的数组</k,v>  

    2.数组元素Node

    //Node是单向链表,它实现了Map.Entry接口  
    static class Node<k,v> implements Map.Entry<k,v> {  
        final int hash;  
        final K key;  
        V value;  
        Node<k,v> next;  
        //构造函数Hash值 键 值 下一个节点  
        Node(int hash, K key, V value, Node<k,v> next) {  
            this.hash = hash;  
            this.key = key;  
            this.value = value;  
            this.next = next;  
        }  
    
        public final K getKey()        { return key; }  
        public final V getValue()      { return value; }  
        public final String toString() { return key + = + value; }  
    
        public final int hashCode() {  
            return Objects.hashCode(key) ^ Objects.hashCode(value);  
        }  
    
        public final V setValue(V newValue) {  
            V oldValue = value;  
            value = newValue;  
            return oldValue;  
        }  
        //判断两个node是否相等,若key和value都相等,返回true。可以与自身比较为true  
        public final boolean equals(Object o) {  
            if (o == this)  
                return true;  
            if (o instanceof Map.Entry) {  
                Map.Entry<!--?,?--> e = (Map.Entry<!--?,?-->)o;  
                if (Objects.equals(key, e.getKey()) &&  
                    Objects.equals(value, e.getValue()))  
                    return true;  
            }  
            return false;  
        }  

    3.红黑树

    //红黑树  
    static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {  
        TreeNode<k,v> parent;  // 父节点  
        TreeNode<k,v> left; //左子树  
        TreeNode<k,v> right;//右子树  
        TreeNode<k,v> prev;    // needed to unlink next upon deletion  
        boolean red;    //颜色属性  
        TreeNode(int hash, K key, V val, Node<k,v> next) {  
            super(hash, key, val, next);  
        }  
    
        //返回当前节点的根节点  
        final TreeNode<k,v> root() {  
            for (TreeNode<k,v> r = this, p;;) {  
                if ((p = r.parent) == null)  
                    return r;  
                r = p;  
            }  
        }  

    三、HashMap加载因子

    加载因子(默认0.75):为什么需要使用加载因子,为什么需要扩容呢?

    因为如果填充比很大,说明利用的空间很多,如果一直不进行扩容的话,链表就会越来越长,这样查找的效率很低,因为链表的长度很大(当然最新版本使用了红黑树后会改进很多),扩容之后,将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置,这样就减少了每个链表的长度,增加查找效率

    如果加载因子越大,对空间的利用更充分,但是查找效率会降低(链表长度会越来越长);如果加载因子太小,那么表中的数据将过于稀疏(很多空间还没用,就开始扩容了),对空间造成严重浪费。如果我们在构造方法中不指定,则系统默认加载因子为0.75,这是一个比较理想的值,一般情况下我们是无需修改的。

    public class HashMap<k,v> extends AbstractMap<k,v> implements Map<k,v>, Cloneable, Serializable {  
        private static final long serialVersionUID = 362498820763181265L;  
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  
        static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量  
        static final float DEFAULT_LOAD_FACTOR = 0.75f;//填充比  
        //当add一个元素到某个位桶,其链表长度达到8时将链表转换为红黑树  
        static final int TREEIFY_THRESHOLD = 8;  
        static final int UNTREEIFY_THRESHOLD = 6;  
        static final int MIN_TREEIFY_CAPACITY = 64;  
        transient Node<k,v>[] table;//存储元素的数组  
        transient Set<map.entry<k,v>> entrySet;  
        transient int size;//存放元素的个数  
        transient int modCount;//被修改的次数fast-fail机制  
        int threshold;//临界值 当实际大小(容量*填充比)超过临界值时,会进行扩容   
        final float loadFactor;//填充比(......后面略)  

    四.HashMap的构造函数

    HashMap的构造方法有4种,主要涉及到的参数有,指定初始容量,指定填充比和用来初始化的Map

    //构造函数1  
    public HashMap(int initialCapacity, float loadFactor) {  
        //指定的初始容量非负  
        if (initialCapacity < 0)  
            throw new IllegalArgumentException(Illegal initial capacity:  +  
                                               initialCapacity);  
        //如果指定的初始容量大于最大容量,置为最大容量  
        if (initialCapacity > MAXIMUM_CAPACITY)  
            initialCapacity = MAXIMUM_CAPACITY;  
        //填充比为正  
        if (loadFactor <= 0 || Float.isNaN(loadFactor))  
            throw new IllegalArgumentException(Illegal load factor:  +  
                                               loadFactor);  
        this.loadFactor = loadFactor;  
        this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值  
    }  
    
    //构造函数2  
    public HashMap(int initialCapacity) {  
        this(initialCapacity, DEFAULT_LOAD_FACTOR);  
    }  
    
    //构造函数3  
    public HashMap() {  
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted  
    }  
    
    //构造函数4用m的元素初始化散列映射  
    public HashMap(Map<!--? extends K, ? extends V--> m) {  
        this.loadFactor = DEFAULT_LOAD_FACTOR;  
        putMapEntries(m, false);  
    }  

    五. 如何获取: get(object key) 方法

    下面简单说下 get(key) 的过程:
    get(key)方法时获取key的hash值,计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)],先判断first(即数组中的那个,看图1)的key是否与参数key相等,不等就遍历后面的链表找到相同的key值返回对应的Value值即可

    public V get(Object key) {  
            Node<K,V> e;  
            return (e = getNode(hash(key), key)) == null ? null : e.value;  
        }  
          /** 
         * Implements Map.get and related methods 
         * 
         * @param hash hash for key 
         * @param key the key 
         * @return the node, or null if none 
         */  
        final Node<K,V> getNode(int hash, Object key) {  
            Node<K,V>[] tab;//Entry对象数组  
            Node<K,V> first,e; //在tab数组中经过散列的第一个位置  
            int n;  
            K k;  
        /*找到插入的第一个Node,方法是hash值和n-1相与,tab[(n - 1) & hash]*/  
        //也就是说在一条链上的hash值相同的  
            if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {  
        /*检查第一个Node是不是要找的Node*/  
                if (first.hash == hash && // always check first node  
                    ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同,key值要相同  
                    return first;  
          /*检查first后面的node*/  
                if ((e = first.next) != null) {  
                    if (first instanceof TreeNode)  
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);  
                    /*遍历后面的链表,找到key值和hash值都相同的Node*/  
                    do {  
                        if (e.hash == hash &&  
                            ((k = e.key) == key || (key != null && key.equals(k))))  
                            return e;  
                    } while ((e = e.next) != null);  
                }  
            }  
            return null;  
        }  

    六、如何存储:put(k,v) 方法

    下面简单说下添加键值对put(key,value)的过程:
    1,判断键值对数组tab[]是否为空或为null,否则以默认大小resize();
    2,根据键值key计算hash值得到插入的数组索引i,如果tab[i]==null,直接新建节点添加,否则转入3
    3,判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理

    疑问:如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险?
      这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素,其它元素都在后面链表。到这里为止,HashMap的大致实现,我们应该已经清楚了。

    public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
     }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab;
        Node<K,V> p; 
        int n, i;
        //如果当前map中无数据,执行resize方法。并且返回n
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
         //如果要插入的键值对要存放的这个位置刚好没有元素,那么把他封装成Node对象,放在这个位置上就完事了
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
        //否则的话,说明这上面有元素
            else {
                Node<K,V> e; K k;
            //如果这个元素的key与要插入的一样,那么就替换一下,也完事。
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
            //1.如果当前节点是TreeNode类型的数据,执行putTreeVal方法
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
            //还是遍历这条链子上的数据,跟jdk7没什么区别
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                //2.完成了操作后多做了一件事情,判断,并且可能执行treeifyBin方法
                            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) //true || --
                        e.value = value;
               //3.
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
        //判断阈值,决定是否扩容
            if (++size > threshold)
                resize();
            //4.
            afterNodeInsertion(evict);
            return null;
        }

    treeifyBin()就是将链表转换成红黑树。

    之前的indefFor()方法消失 了,直接用(tab.length-1)&hash,所以看到这个,代表的就是数组的下角标。

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

    七、HasMap的扩容机制resize()

    构造hash表时,如果不指明初始大小,默认大小为16(即Node数组大小16),如果Node[]数组中的元素达到(填充比*Node.length)重新调整HashMap大小 变为原来2倍大小,扩容很耗时

    /** 
        * Initializes or doubles table size.  If null, allocates in 
        * accord with initial capacity target held in field threshold. 
        * Otherwise, because we are using power-of-two expansion, the 
        * elements from each bin must either stay at same index, or move 
        * with a power of two offset in the new table. 
        * 
        * @return the table 
        */  
       final Node<K,V>[] resize() {  
           Node<K,V>[] oldTab = table;  
           int oldCap = (oldTab == null) ? 0 : oldTab.length;  
           int oldThr = threshold;  
           int newCap, newThr = 0;  
    
    /*如果旧表的长度不是空*/  
           if (oldCap > 0) {  
               if (oldCap >= MAXIMUM_CAPACITY) {  
                   threshold = Integer.MAX_VALUE;  
                   return oldTab;  
               }  
    /*把新表的长度设置为旧表长度的两倍,newCap=2*oldCap*/  
               else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                        oldCap >= DEFAULT_INITIAL_CAPACITY)  
          /*把新表的门限设置为旧表门限的两倍,newThr=oldThr*2*/  
                   newThr = oldThr << 1; // double threshold  
           }  
        /*如果旧表的长度的是0,就是说第一次初始化表*/  
           else if (oldThr > 0) // initial capacity was placed in threshold  
               newCap = oldThr;  
           else {               // zero initial threshold signifies using defaults  
               newCap = DEFAULT_INITIAL_CAPACITY;  
               newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
           }  
    
    
    
           if (newThr == 0) {  
               float ft = (float)newCap * loadFactor;//新表长度乘以加载因子  
               newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
                         (int)ft : Integer.MAX_VALUE);  
           }  
           threshold = newThr;  
           @SuppressWarnings({"rawtypes","unchecked"})  
    /*下面开始构造新表,初始化表中的数据*/  
           Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
           table = newTab;//把新表赋值给table  
           if (oldTab != null) {//原表不是空要把原表中数据移动到新表中      
               /*遍历原来的旧表*/        
               for (int j = 0; j < oldCap; ++j) {  
                   Node<K,V> e;  
                   if ((e = oldTab[j]) != null) {  
                       oldTab[j] = null;  
                       if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置  
                           newTab[e.hash & (newCap - 1)] = e;  
                       else if (e instanceof TreeNode)  
                           ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
    /*如果e后边有链表,到这里表示e后面带着个单链表,需要遍历单链表,将每个结点重*/  
                       else { // preserve order保证顺序  
                    新计算在新表的位置,并进行搬运  
                           Node<K,V> loHead = null, loTail = null;  
                           Node<K,V> hiHead = null, hiTail = null;  
                           Node<K,V> next;  
    
                           do {  
                               next = e.next;//记录下一个结点  
              //新表是旧表的两倍容量,实例上就把单链表拆分为两队,  
                 //e.hash&oldCap为偶数一队,e.hash&oldCap为奇数一对  
                               if ((e.hash & oldCap) == 0) {  
                                   if (loTail == null)  
                                       loHead = e;  
                                   else  
                                       loTail.next = e;  
                                   loTail = e;  
                               }  
                               else {  
                                   if (hiTail == null)  
                                       hiHead = e;  
                                   else  
                                       hiTail.next = e;  
                                   hiTail = e;  
                               }  
                           } while ((e = next) != null);  
    
                           if (loTail != null) {//lo队不为null,放在新表原位置  
                               loTail.next = null;  
                               newTab[j] = loHead;  
                           }  
                           if (hiTail != null) {//hi队不为null,放在新表j+oldCap位置  
                               hiTail.next = null;  
                               newTab[j + oldCap] = hiHead;  
                           }  
                       }  
                   }  
               }  
           }  
           return newTab;  
       }  

    八、JDK1.8使用红黑树的改进

    在java jdk8中对HashMap的源码进行了优化,在jdk7中,HashMap处理“碰撞”的时候,都是采用链表来存储,当碰撞的结点很多时,查询时间是O(n)。

    在jdk8中,HashMap处理“碰撞”增加了红黑树这种数据结构,当碰撞结点较少时,采用链表存储,当较大时(>8个),采用红黑树(特点是查询时间是O(logn))存储(有一个阀值控制,大于阀值(8个),将链表存储转换成红黑树存储)

    问题分析:
    你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候,这些值是存储到一个链表中的。最坏的情况下,所有的key都映射到同一个桶中,这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。

    随着HashMap的大小的增长,get()方法的开销也越来越大。由于所有的记录都在同一个桶里的超长链表内,平均查询一条记录就需要遍历一半的列表。

    JDK1.8HashMap的红黑树是这样解决的

    如果某个桶中的记录过大的话(当前是TREEIFY_THRESHOLD = 8),HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好,是O(logn),而不是糟糕的O(n)。

    它是如何工作的?前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面,这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树,使用哈希值作为树的分支变量,如果两个哈希值不等,但指向同一个桶的话,较大的那个会插入到右子树里。如果哈希值相等,HashMap希望key值最好是实现了Comparable接口的,这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的,不过如果实现了当然最好。如果没有实现这个接口,在出现严重的哈希碰撞的时候,你就并别指望能获得性能提升了。

    九、如何解决hash冲突

    hash定义:

    翻译为“散列”,就是把任意长度的输入,通过散列算法,变成固定长度的输出,该输出就是散列值。
    这种转换是一种压缩映射,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。

    解决hash冲突的办法:

    1)开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)

    开放定址法就是:一旦发生冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。

    查找时:首先散列值所指向的槽,如果没有找到匹配,则继续从该槽遍历hash表,直到:(1)找到相应的元素;(2)找到一个空槽,指示查找的元素不存在,(所以不能随便删除元素);(3)整个hash表遍历完毕(指示该元素不存在并且hash表是满的)

    Hi = (H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列。di可有下列三种取法:

    (1)di=1,2,3,…, m-1,称为线性探测再散列;

    (2)di=1^2, -(1^2), 2^2, -(2^2), 3^2, …, ±(k^2),(k<=m/2),称二为次探测再散列;

    (3)di=伪随机数序列,称为伪随机探测再散列。

    (所谓伪随机数,用同样的随机种子,将得到相同的数列。)

    比如说,我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},表长为12。 我们用散列函数f(key) = key mod l2
    当计算前S个数{12,67,56,16,25}时,都是没有冲突的散列地址,直接存入:
    这里写图片描述
    计算key = 37时,发现f(37) = 1,此时就与25所在的位置冲突。
    于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置:
    这里写图片描述
    2)链地址法 (拉链法)

    将所有哈希地址相同的元素都链接到同一个链表中。

    3)再哈希法(再散列,多重散列)

    产生冲突时,使用第二个,第三个、、、哈希函数计算地址,直到冲突不再发生为止。增加了计算时间。
    Java中hashmap的解决办法就是采用的 链地址法 。

    4)建立一个公共溢出区

    将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表.。

    查找时,对给定key通过散列函数计算出散列地址后,先与基本表的相应位置进行比对,如果相等,则查找成功;如果不相等,则到溢出表进行顺序查找。

    十、hashMap与Hashtable区别

    1、继承的父类不同
    Hashtable继承自Dictionary类,而HashMap继承自AbstractMap类。但二者都实现了Map接口。
    2、线程安全性不同
    Hashtable 线程安全:因为它每个方法中都加入了Synchronize,对整个table加锁
    HashMap是线程不安全的
    HashMap底层是一个Entry数组,当发生hash冲突的时候,hashmap是采用链表的方式来解决的,在对应的数组位置存放链表的头结点。对链表而言,新加入的节点会从头结点加入。
    我们来分析一下多线程访问:
    1)在hashmap做put操作的时候会调用addEntry方法
    现在假如A线程和B线程同时对同一个桶调用addEntry,两个线程会同时得到现在的头结点,然后A写入新的头结点之后,B也写入新的头结点,那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。
    2)**调用删除键值对方法**removeEntryForKey(Object key)
    多个线程对同一个桶操作时,同时得到数组中的头结点,并发访问和修改,会造成修改覆盖
    3)put新的键值对后,若键值对 总数量 超过门限值的时候会调用一个resize操作
    这个操作会新生成一个新的容量的数组,然后对原数组的所有键值对重新进行计算和写入新的数组,之后指向新生成的数组。
    当多个线程同时检测到总数量超过门限值的时候就会同时调用resize操作,各自生成新的数组并rehash后赋给该map底层的数组table,结果最终只有最后一个线程生成的新数组被赋给table变量,其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候,就会用已经被赋值的table作为原始数组,这样也会有问题。
    3、是否提供contains方法
    HashMap把Hashtable的contains方法去掉了,改成containsValue和containsKey,因为contains方法容易让人引起误解。
    Hashtable则保留了contains,containsValue和containsKey三个方法,其中contains和containsValue功能相同。
    4、key和value是否允许null值
    其中key和value都是对象,并且不能包含重复key,但可以包含重复的value。
    通过上面的ContainsKey方法和ContainsValue的源码我们可以很明显的看出:
    HashMap中,null可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为null。当get()方法返回null值时,可能是 HashMap中没有该键,也可能使该键所对应的值为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断。
    Hashtable中,key和value都不允许出现null值。但是如果在Hashtable中有类似put(null,null)的操作,编译同样可以通过,因为key和value都是Object类型,但运行时会抛出NullPointerException异常,这是JDK的规范规定的。

    5、两个遍历方式的内部实现上不同
    HashMap使用 Iterator。
    Hashtable使用Iterator,还使用了Enumeration的方式 。
    6、hash值不同
    HashTable直接使用对象的hashCode。而HashMap重新计算hash值。

    hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值。

    HashMap重新计算了key的hash值,HashMap在求位置索引时,则用与运算,即 hash&(length-1)

    Hashtable计算hash值:直接用key的hashCode(),Hashtable在求hash值对应的位置索引时,用取模运算, 且这里一般先用hash&0x7FFFFFFF后,再对length取模,&0x7FFFFFFF的目的是为了将负的hash值转化为正值,因为hash值有可能为负数,而&0x7FFFFFFF后,只有符号外改变,而后面的位都不变。

    7、内部实现使用的数组初始化和扩容方式不同
    HashTable初始默认容量为11,Hashtable不要求 底层数组的容量一定要为2的整数次幂, Hashtable扩容时,将容量变为原来的2倍加1,
    而HashMap初始默认容量为为16,而HashMap则要求一定为2的整数次幂,而HashMap扩容时,将容量变为原来的2倍。

    十、面试官提问

    1)介绍HashMap
    按照特性来说明一下:储存的是键值对,线程不安全,非Synchronied,储存的比较快,能够接受null。

    按照工作原理来叙述一下:Map的put(key,value)来储存元素,通过get(key)来得到value值,通过hash算法来计算hascode值,用hashCode标识Entry在bucket中存储的位置,储存结构就算哈希表。

    “2)你知道HashMap的工作原理吗?” “你知道HashMap的get()方法的工作原理吗?”
    “HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。
    当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。
    ”这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Entry。
    这一点有助于理解获取对象的逻辑。如果你没有意识到这一点,或者错误的认为仅仅只在bucket中存储值的话,你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确,也显示出面试者确实知道hashing以及HashMap的工作原理。

    3)提问:两个hashcode相同的时候会发生说明?
    hashcode相同,bucket的位置会相同,也就是说会发生碰撞,哈希表中的结构其实有链表(LinkedList),这种冲突通过将元素储存到LinkedList中,解决碰撞。储存顺序是放在表头。

    4)如果两个键的hashcode相同,如何获取值对象?
    如果两个键的hashcode相同,即找到bucket位置之后,我们通过key.equals()找到链表LinkedList中正确的节点,最终找到要找的值对象。
    一些优秀的开发者会指出使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。

    5)如果HashMap的大小超过了负载因子(load factor)定义的容量?怎么办?
    HashMap里面默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

    6)重新调整HashMap大小的话会出现什么问题?
    多线程情况下会出现竞争问题,因为你在调节的时候,LinkedList储存是按照顺序储存,调节的时候回将原来最先储存的元素(也就是最下面的)遍历,多线程就好试图重新调整,这个时候就会出现死循环

    当多线程的情况下,可能产生条件竞争(race condition)。
    当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。

    7)HashMap在并发执行put操作,会引起死循环,为什么?
    是因为多线程会导致hashmap的node链表形成环形链表,一旦形成环形链表,node 的next节点永远不为空,就会产生死循环获取node。从而导致CPU利用率接近100%。

    8)为什么String, Interger这样的wrapper类适合作为键?
    因为他们一般不是不可变的,源码上面final,使用不可变类,而且重写了equals和hashcode方法,避免了键值对改写。提高HashMap性能。

    String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。

    9)使用CocurrentHashMap代替Hashtable?
    可以,但是Hashtable提供的线程更加安全。
    Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。
    10)hashing的概念
    散列法(Hashing)或哈希法是一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法,称为散列法,也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快,这种方法一般用来在数据库中建立索引并进行搜索,同时还用在各种解密算法中。

    11)扩展:为什么equals()方法要重写?
    判断两个对象在逻辑上是否相等,如根据类的成员变量来判断两个类的实例是否相等,而继承Object中的equals方法只能判断两个引用变量是否是同一个对象。这样我们往往需要重写equals()方法。

    我们向一个没有重复对象的集合中添加元素时,集合中存放的往往是对象,我们需要先判断集合中是否存在已知对象,这样就必须重写equals方法。

    怎样重写equals()方法?

    重写equals方法的注意点:
    1、自反性:对于任何非空引用x,x.equals(x)应该返回true。
    2、对称性:对于任何引用x和y,如果x.equals(y)返回true,那么y.equals(x)也应该返回true。
    3、传递性:对于任何引用x、y和z,如果x.equals(y)返回true,y.equals(z)返回true,那么x.equals(z)也应该返回true。
    4、一致性:如果x和y引用的对象没有发生变化,那么反复调用x.equals(y)应该返回同样的结果。
    5、非空性:对于任意非空引用x,x.equals(null)应该返回false。

    参考链接
    http://www.importnew.com/7099.html
    http://www.importnew.com/23164.html
    https://my.oschina.net/xianggao/blog/393990

    展开全文
  • 二、源码分析 1.位桶数组 2.数组元素Node实现了Entry接口,v> 3.HashMap如何put(key,value) 4.HashMap如何getValue值 5.HasMap的扩容机制resize(); 6. JDK1.8使用红黑树的改进 三、再谈ReHash 单线程下...

    目录

    一、HashMap的数据结构

    解决hash冲突的办法

    二、源码分析

    1.  位桶数组

    2. 数组元素Node实现了Entry接口,v>

     3. HashMap如何put(key,value)

    4. HashMap如何getValue值

    5. HasMap的扩容机制resize();

    6. JDK1.8使用红黑树的改进

    三、再谈ReHash

    单线程下的ReHash

    并发下的Rehash


    一、HashMap的数据结构


    数据结构中有 数组 和 链表 来实现对数据的存储,但这两者基本上是两个极端。  (堆砌了别人的文章!呵呵呵)

      数组
    数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;

    链表
    链表存储区间离散(不连续),占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,O(N)。链表的特点是:寻址困难,插入和删除容易。

    哈希表
    那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表。哈希表((Hash table)既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便。

         当链表数组的容量超过初始容量的0.75时,再散列将链表数组扩大2倍,把原链表数组的搬移到新的数组中

    加载因子(默认0.75):为什么需要使用加载因子,为什么需要扩容呢因为如果填充比很大,说明利用的空间很多,如果一直不进行扩容的话,链表就会越来越长,这样查找的效率很低,因为链表的长度很大(当然最新版本使用了红黑树后会改进很多),扩容之后,将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置,这样就减少了每个链表的长度,增加查找效率

    HashMap本来是以空间换时间,所以填充比没必要太大。但是填充比太小又会导致空间浪费。如果关注内存,填充比可以稍大,如果主要关注查找性能,填充比可以稍小。

    即HashMap的原理图是:

      

    解决hash冲突的办法

    1. 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
    2. 再哈希法
    3. 链地址法
    4. 建立一个公共溢出区

         Java中hashmap的解决办法就是采用的链地址法(也称为拉链法)。

    二、源码分析

    1.  位桶数组

      transient Node<K,V>[] table;

    2. 数组元素Node<K,V>实现了Entry接口

    public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable {
    
        private static final long serialVersionUID = 362498820763181265L;
    
        
    
        /**
         * 初始大小 - MUST be a power of two.
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * The maximum capacity
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * 装载因子
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    
        /**
    	 * Node 是单向链表, 实现了 Map.Entry 接口
         */
        static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
            /**
    	     * 构造函数 Hash值、键、值、下一个节点
             */
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
    
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
            /**
    		 * 判断两个node是否相等,若key和value都相等,返回true。可以与自身比较为true  
    		 */
            public final boolean equals(Object o) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }
    }

     3. HashMap如何put(key,value)

    链地址法解决hash 冲突

      

    public V put(K key, V value) {  
            return putVal(hash(key), key, value, false, true);  
        }  
         /** 
    	 *
         */  
    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;  
            /*如果table的在(n-1)&hash的值是空,就新建一个节点插入在该位置*/  
            if ((p = tab[i = (n - 1) & hash]) == null)  
                tab[i] = newNode(hash, key, value, null); 
    			
            /*表示有冲突,开始处理冲突*/  
            else {  
                Node<K,V> e;   
                K k;  
                 /*检查第一个Node,p是不是要找的值*/  
                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);  
                            //如果冲突的节点数已经达到8个,看是否需要改变冲突节点的存储结构,               
                //treeifyBin首先判断当前hashMap的长度,如果不足64,只进行  
                            //resize,扩容table,如果达到64,那么将冲突的存储结构为红黑树  
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                                treeifyBin(tab, hash);  
                            break;  
                        }  
                        /*如果有相同的key值就结束遍历*/  
                        if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))  
                            break;  
                        p = e;  
                    }  
                }  
                /*就是链表上有相同的key值*/  
                 if (e != null) { // existing mapping for key,就是key的Value存在  
                    V oldValue = e.value;  
                    if (!onlyIfAbsent || oldValue == null)  
                        e.value = value;  
                    afterNodeAccess(e);  
                    return oldValue;//返回存在的Value值  
                }  
            }  
            ++modCount;  
         /*如果当前大小大于门限,门限原本是初始容量*0.75*/  
            if (++size > threshold)  
                resize();//扩容两倍  
            afterNodeInsertion(evict);  
            return null;  
        }
    }

    简单说下添加键值对put(key,value)的过程:
    1,判断键值对数组tab[]是否为空或为null,否则以默认大小resize();
    2,根据键值key计算hash值得到插入的数组索引i,如果tab[i]==null,直接新建节点添加,否则转入3
    3,判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理

     

    4. HashMap如何getValue值

    public V get(Object key) {  
            Node<K,V> e;  
            return (e = getNode(hash(key), key)) == null ? null : e.value;  
        }  
          /** 
         * Implements Map.get and related methods 
         * 
         * @param hash hash for key 
         * @param key the key 
         * @return the node, or null if none 
         */  
        final Node<K,V> getNode(int hash, Object key) {  
        Node<K,V>[] tab;//Entry对象数组  
        Node<K,V> first,e; //在tab数组中经过散列的第一个位置  
        int n;  
        K k;  
        /*找到插入的第一个Node,方法是hash值和n-1相与,tab[(n - 1) & hash]*/  
        //也就是说在一条链上的hash值相同的  
            if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {  
                /*检查第一个Node是不是要找的Node*/  
                if (first.hash == hash && // always check first node  
    			    //判断条件是hash值要相同,key值要相同  
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;  
                /*检查first后面的node*/  
                if ((e = first.next) != null) {  
                    if (first instanceof TreeNode)  
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);  
                    /*遍历后面的链表,找到key值和hash值都相同的Node*/  
                    do {  
                        if (e.hash == hash &&  
                            ((k = e.key) == key || (key != null && key.equals(k))))  
                            return e;  
                    } while ((e = e.next) != null);  
                }  
            }  
            return null;  
        }

    get(key)方法时获取key的hash值,计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)],先判断first的key是否与参数key相等,不等就遍历后面的链表找到相同的key值返回对应的Value值即可

    5. HasMap的扩容机制resize();

    构造hash表时,如果不指明初始大小,默认大小为16(即Node数组大小16),如果Node[]数组中的元素达到(填充比*Node.length)重新调整HashMap大小 变为原来2倍大小,扩容很耗时

     

    /** 
        * Initializes or doubles table size.
        */  
       final Node<K,V>[] resize() {  
           Node<K,V>[] oldTab = table;  
           int oldCap = (oldTab == null) ? 0 : oldTab.length;  
           int oldThr = threshold;  
           int newCap, newThr = 0;  
          
    /* 如果旧表的长度不是空 */  
           if (oldCap > 0) {  
               if (oldCap >= MAXIMUM_CAPACITY) {  
                   threshold = Integer.MAX_VALUE;  
                   return oldTab;  
               }  
    /* 把新表的长度设置为旧表长度的两倍,newCap=2*oldCap */  
               else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                        oldCap >= DEFAULT_INITIAL_CAPACITY)  
        /* 把新表的阈值设置为旧表阈值的两倍,newThr=oldThr*2 */  
                   newThr = oldThr << 1; // double threshold  
           }  
        /* 如果旧表的长度的是0,也就是说第一次初始化表 */  
           else if (oldThr > 0) // initial capacity was placed in threshold  
               newCap = oldThr;  
           else {               // zero initial threshold signifies using defaults  
               newCap = DEFAULT_INITIAL_CAPACITY;  
               newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
           }  
          
          
          
           if (newThr == 0) {  
               float ft = (float)newCap * loadFactor;//新表长度乘以加载因子  
               newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
                         (int)ft : Integer.MAX_VALUE);  
           }  
           threshold = newThr;  
           @SuppressWarnings({"rawtypes","unchecked"})  
        /*下面开始构造新表,初始化表中的数据*/  
           Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
           table = newTab;//把新表赋值给table  
           if (oldTab != null) {//原表不是空要把原表中数据移动到新表中      
               /*遍历原来的旧表*/        
               for (int j = 0; j < oldCap; ++j) {  
                   Node<K,V> e;  
                   if ((e = oldTab[j]) != null) {  
                       oldTab[j] = null;  
                       if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置  
                           newTab[e.hash & (newCap - 1)] = e;  
                       else if (e instanceof TreeNode)  
                           ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
                /*如果e后边有链表,到这里表示e后面带着个单链表,需要遍历单链表,将每个结点重*/  
                       else { // preserve order保证顺序  
                    新计算在新表的位置,并进行搬运  
                           Node<K,V> loHead = null, loTail = null;  
                           Node<K,V> hiHead = null, hiTail = null;  
                           Node<K,V> next;  
                          
                           do {  
                               next = e.next;//记录下一个结点  
                 //新表是旧表的两倍容量,实例上就把单链表拆分为两队,  
                 //e.hash&oldCap为偶数一队,e.hash&oldCap为奇数一对  
                               if ((e.hash & oldCap) == 0) {  
                                   if (loTail == null)  
                                       loHead = e;  
                                   else  
                                       loTail.next = e;  
                                   loTail = e;  
                               }  
                               else {  
                                   if (hiTail == null)  
                                       hiHead = e;  
                                   else  
                                       hiTail.next = e;  
                                   hiTail = e;  
                               }  
                           } while ((e = next) != null);  
                          
                           if (loTail != null) {//lo队不为null,放在新表原位置  
                               loTail.next = null;  
                               newTab[j] = loHead;  
                           }  
                           if (hiTail != null) {//hi队不为null,放在新表j+oldCap位置  
                               hiTail.next = null;  
                               newTab[j + oldCap] = hiHead;  
                           }  
                       }  
                   }  
               }  
           }  
           return newTab;  
       }

    6. JDK1.8使用红黑树的改进

    Java jdk8中对HashMap的源码进行了优化,在jdk7中,HashMap处理“碰撞”的时候,都是采用链表来存储,当碰撞的结点很多时,查询时间是O(n)。
    在jdk8中,HashMap处理“碰撞”增加了红黑树这种数据结构,当碰撞结点较少时,采用链表存储,当较大时(>8个),采用红黑树(特点是查询时间是O(logn))存储(有一个阀值控制,大于阀值(8个),将链表存储转换成红黑树存储)

    问题分析:

    你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候,这些值是存储到一个链表中的。最坏的情况下,所有的key都映射到同一个桶中,这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。

     

    随着HashMap的大小的增长,get()方法的开销也越来越大。由于所有的记录都在同一个桶里的超长链表内,平均查询一条记录就需要遍历一半的列表。

     JDK1.8HashMap的红黑树是这样解决的

             如果某个桶中的记录过大的话(当前是TREEIFY_THRESHOLD = 8),HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好,是O(logn),而不是糟糕的O(n)。

            它是如何工作的?前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面,这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树,使用哈希值作为树的分支变量,如果两个哈希值不等,但指向同一个桶的话,较大的那个会插入到右子树里。如果哈希值相等,HashMap希望key值最好是实现了Comparable接口的,这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的,不过如果实现了当然最好。如果没有实现这个接口,在出现严重的哈希碰撞的时候,你就并别指望能获得性能提升了。

     

    三、再谈ReHash

    单线程下的ReHash

    • 用key mod 一下表的大小(也就是数组的长度)。
    • 最上面的是old hash 表,其中的Hash表的size=2, 所以key = 3, 7, 5,在mod 2以后都冲突在table[1]这里了。
    • 接下来的三个步骤是Hash表 resize成4,然后所有的<key,value> 重新rehash的过程

    image

    详细描述可以看下面这张图:

     

    并发下的Rehash

    1. 假设我们有两个线程。我用红色和浅蓝色标注了一下。
    do{
        Entry<K,V> next = e.next;// <--假设线程一执行到这里就被调度挂起了
        inti = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
    }while (e != null);
    

    而我们的线程二执行完成了。于是我们有下面的这个样子。

     

    注意,因为Thread1的 e 指向了key(3),而next指向了key(7),其在线程二rehash后,指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

    1. 线程一被调度回来执行。
    • 先是执行 newTalbe[i] = e;
    • 然后是e = next,导致了e指向了key(7),
    • 而下一次循环的next = e.next导致了next指向了key(3)

     

    1. 线程一继续执行

    把key(7)摘下来,放到newTable[i]的第一个,然后把e和next往下移

     

    1. 环形链接出现

    e.next = newTable[i] 导致 key(3).next 指向了 key(7)
    注意:此时的key(7).next 已经指向了key(3), 环形链表就这样出现了。



    参考:
    https://www.jianshu.com/p/13c650a25ed3
    https://www.cnblogs.com/little-fly/p/7344285.html

    展开全文
  • 主要介绍了java 中HashMap实现原理深入理解的相关资料,需要的朋友可以参考下
  • HashMap实现原理分析
  • Java8之后新增挺多新东西,接下来通过本文给大家介绍Java8 HashMap的实现原理分析,对java8 hashmap实现原理相关知识感兴趣的朋友一起学习吧
  • http://blog.csdn.net/vking_wang/article/details/14166593 http://blog.csdn.net/jbxiaozi/article/details/7290138
  • HashMap实现原理分析(详解)

    千次阅读 2017-08-20 17:30:05
    1. HashMap的数据结构 http://blog.csdn.net/gaopu12345/article/details/50831631  ??看一下   数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。  数组 数组存储区间是...
  • HashMap实现原理分析-resize()详解

    千次阅读 2017-06-29 14:29:28
    介绍resize() 方法前先了解一下Java为什么会有resize()方法,他的作用是什么,我们有一个默认认知是,HashMap的get查找的复杂度是O(1)的,那么如果初始散列表大小是16,加载因子是0.75的话,如果数据量过多(例如256...
  • 1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。  数组 数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点...
  • 主要内容: 1)put 疑问:如果两个key通过hash%Entry[].length得到的index相同,会... 这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。 打...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 71,760
精华内容 28,704
关键字:

hashmap实现原理分析