hashmap 订阅
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。 展开全文
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。
信息
外文名
hashMap
基    于
哈希表的 Map 接口的实现
参    数
初始容量 和加载因子
中文名
哈希映射
同步机制
此实现不是同步的
Hashmap重要参数
HashMap 的实例有两个参数影响其性能:初始容量 和加载因子。容量是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。在Java编程语言中,加载因子默认值为0.75,默认哈希表元为101 [1]  。
收起全文
精华内容
参与话题
问答
  • 10分钟拿下 HashMap

    万次阅读 多人点赞 2018-10-18 11:18:04
    1、什么是 HashMap?什么时候选择HashMap? 2、HashMap 数据结构及其工作原理? 2.1 数据结构 2.2 工作原理 3、HashMap和HashTable 的异同? 4、如何优化 HashMap? 1、什么是 HashMap?什么时候选择HashMap?...

    请相信我,你一定会更优秀!

    备注:jdk版本为 1.7,初识 HashMap(后续会继续带你拿下 1.8+的HashMap)

    目录

    1、什么是 HashMap,什么时候选择 HashMap?

    2、HashMap 数据结构及其工作原理?

    2.1 数据结构

    2.2 工作原理

    3、HashMap和HashTable 的异同?

    4、如何优化 HashMap?


    1、什么是 HashMap,什么时候选择 HashMap?

    说到容器,你肯定会想到 Java中对象存储容器还有ArrayList,LinkedList,HashSet等,HashMap 相对这些容器来说,可以理解为多了一层指向关系,可以用指定Key找到指定Value。

    打个比方

    现在有一个Java Bean 用于存储职员的信息,字段包括(职员姓名,职员年龄,职员身高,职员体重,职员教育程度 ... 等等),我是一名人力资源管理,我需要将员工信息整理好发给老板。

    图示:

    问题:

    这个时候你必须要想到,如果两个人名字一样可咋办,查到的到底是谁的信息呢?前者信息会被覆盖吗?带着问题来学习一下HashMap数据结构及其工作原理。

    2、HashMap 数据结构及其工作原理?

    2.1 数据结构

    HashMap 数据结构为 数组+链表,其中:链表的节点存储的是一个 Entry 对象,每个Entry 对象存储四个属性(hash,key,value,next)

    一张图带你看懂:

    by zhanghaolin

    三句话,说清它的数据结构:

    1. 整体是一个数组;
    2. 数组每个位置是一个链表;
    3. 链表每个节点中的Value即我们存储的Object;

    2.2 工作原理

    首先,初始化 HashMap,提供了有参构造和无参构造,无参构造中,容器默认的数组大小 initialCapacity 为 16,加载因子loadFactor 为0.75。容器的阈(yu)值为 initialCapacity * loadFactor,默认情况下阈值为 16 * 0.75 = 12; 后面会讲到阈值有啥用。

    然后,这里我们拿 PUT 方法来做研究:

    第一步:通过 HashMap 自己提供的hash 算法算出当前 key 的hash 值

    第二步:通过计算出的hash 值去调用 indexFor 方法计算当前对象应该存储在数组的几号位置

    第三步:判断size 是否已经达到了当前阈值,如果没有,继续;如果已经达到阈值,则先进行数组扩容,将数组长度扩容为原来的2倍。

    > 请注意size 是当前容器中已有 Entry 的数量,不是数组长度。

    第四步:将当前对应的 hash,key,value封装成一个 Entry,去数组中查找当前位置有没有元素,如果没有,放在这个位置上;如果此位置上已经存在链表,那么遍历链表,如果链表上某个节点的 key 与当前key 进行 equals 比较后结果为 true,则把原来节点上的value 返回,将当前新的 value替换掉原来的value,如果遍历完链表,没有找到key 与当前 key equals为 true的,就把刚才封装的新的 Entry中next 指向当前链表的始节点,也就是说当前节点现在在链表的第一个位置,简单来说即,先来的往后退

    OK!现在,我们已经将当前的 key-value 存储到了容器中。

    为什么我选择聊 PUT 方法?

    因为 PUT 是操作HashMap的最基础操作,了解了 PUT 的机制后,再去看 API其他方法源码的时候你会有所眉目,你可以带着这种初知去探究 HashMap 的其他方法,你一定会豁然开朗。

    扩容机制:

    HashMap 使用 “懒扩容” ,只会在 PUT 的时候才进行判断,然后进行扩容。

    1. 将数组长度扩容为原来的2 倍
    2. 将原来数组中的元素进行重新放到新数组中

    需要注意的是,每次扩容之后,都要重新计算原来的 Entry 在新数组中的位置,为什么数组扩容了,Entry 在数组中的位置发生变化了呢?所以我们会想到计算位置的 indexFor 方法,为什么呢,我摘出了该方法的源码如下:

     static int indexFor(int h, int length) { // h 为key 的 hash值;length 是数组长度
            return h & (length-1);  
     }

    由源码得知,元素所在位置是和数组长度是有关系的,既然扩容后数组长度发生了变化,那么元素位置肯定是要发生变化了。HashMap 计算元素位置采用的是 &运算,不了解此运算的我在这里给个简单的例子:

    高能:为什么 HashMap使用这种方式计算在数组中位置呢?

    按照我们的潜意识,取模就可以了。hashMap 用与运算主要是提升计算性能。这又带来一个新问题,为什么与运算要用 length -1 呢,回看 hashmap初始化的时候,数组长度 length必须是2的整次幂(如果手动传参数组长度为奇数n,hashMap会自动转换长度为距离n最近的2的整次幂数),只有这样, h & (length-1) 的值才会和 h % length 计算的结果是一样的。这就是它的原因所在。另外,当length是2的整次幂的时候,length-1的结果都是低位全部是1,为后面的扩容做了很好的准备,这里先不扯这个,先理解一下这个意思。

    我们来写个单元测试验证下:

    public static void main(String[] args) {
    	
    	/**
    	 * 定义数组长度为2的整次幂,2^4
    	 */
    	int	length  = 16; 
    	
    	/**
    	 * 定义key,并计算k的hash值
    	 */
    	String k = "China";
    	int h = k.hashCode();
    	
    	/**
    	 * 分别使用两种方式计算在数组中的位置
    	 */
    	int index1 = h % length;
    	int index2 = h & (length - 1);
    	
    	/**
    	 * 验证结果
    	 */
    	System.out.println(index1 == index2);
    	
            /**
             * 结果为 true
             */
    }
    public static void main(String[] args) {
    	
    	/**
    	 * 假设数组长度不是2的整次幂,2^4-1
    	 */
    	int	length  = 15; 
    	
    	/**
    	 * 定义key,并计算k的hash值
    	 */
    	String k = "China";
    	int h = k.hashCode();
    	
    	/**
    	 * 分别使用两种方式计算在数组中的位置
    	 */
    	int index1 = h % length;
    	int index2 = h & (length - 1);
    	
    	/**
    	 * 验证结果
    	 */
    	System.out.println(index1 == index2);
    	
    	/**
    	 * 打印结果:false
    	 */
    	
    }

    捡知识:

    计算 8 & 6 = 0的过程如下:

        1 0 0 0    // 8的二进制数
    &   0 1 1 0    // 6的二进制数
    ___________    // 运算规则:该位置上有一个是0 结果就是0
        0 0 0 0    // 二进制数计算结果

    还记得我们(1)中提到的问题了吗?知道答案了吗?

    答:HashMap 中equals 相同的两个key, 容器中只会保留后进来的key 的value。进入问题中即:我先存储了 Lucy的信息,后来又有一个 Lucy,这个时候再存储 Lucy,容器中保留的是第二个 Lucy 的信息,这种情况,我们可以考虑使用 List<T> 作为 value,把相同名字的职员信息存在 list 中;或者给相同名字的职员编号,使得每个key 都是唯一的。

    3、HashMap和HashTable 的异同?

    1. 二者的存储结构和解决冲突的方法都是相同的。
    2. HashTable在不指定容量的情况下的默认容量为11,而HashMap为16,Hashtable不要求底层数组的容量一定要为2的整数次幂,而HashMap则要求一定为2的整数次幂。
    3. HashTable 中 key和 value都不允许为 null,而HashMap中key和value都允许为 null(key只能有一个为null,而value则可以有多个为 null)。但是如果在 Hashtable中有类似 put( null, null)的操作,编译同样可以通过,因为 key和 value都是Object类型,但运行时会抛出 NullPointerException异常。
    4. Hashtable扩容时,将容量变为原来的2倍+1,而HashMap扩容时,将容量变为原来的2倍
    5. Hashtable计算hash值,直接用key的hashCode(),而HashMap重新计算了key的hash值,Hashtable在计算hash值对应的位置索引时,用 %运算,而 HashMap在求位置索引时,则用 &运算。

    4、如何优化 HashMap?

    初始化 HashMap 的时候,我们可以自定义数组容量加载因子的大小。所以,优化 HashMap 从这两个属性入手,但是,如果你不能准确的判别你的业务所需的大小,请使用默认值,否则,一旦手动配置的不合适,效果将适得其反。

    threshold = (int)( capacity * loadFactor );

    阈值 = 容量 X 负载因子

    初始容量默认为16,负载因子(loadFactor)默认是0.75; map扩容后,要重新计算阈值;当元素个数 大于新的阈值时,map再自动扩容;以默认值为例,阈值=16*0.75=12,当元素个数大于12时就要扩容;那剩下的4个数组位置还没有放置对象就要扩容,造成空间浪费,所以要进行时间和空间的折中考虑;

    loadFactor过大时,map内的数组使用率高了,内部极有可能形成Entry链,影响查找速度;

    loadFactor过小时,map内的数组使用率较低,不过内部不会生成Entry链,或者生成的Entry链很短,由此提高了查找速度,不过会占用更多的内存;所以可以根据实际硬件环境和程序的运行状态来调节loadFactor;

    所以,务必合理的初始化 HashMap

     努力改变自己和身边人的生活。

    特别希望本文可以对您有所帮助,转载请注明出处。感谢大家留言讨论交流。

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

    万次阅读 多人点赞 2013-11-05 15:23:28
    HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。  首先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 initialCapacityfloat 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

    万次阅读 多人点赞 2018-11-02 23:59:41
    深入浅出学Java——HashMap 哈希表(hash table) 也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对java集合框架中...

    深入浅出学Java——HashMap

    哈希表(hash table)
    也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对java集合框架中HashMap的实现原理进行讲解,并对JDK7的HashMap源码进行分析。

    一、什么是哈希表

    在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能

    数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)

    线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)

    二叉树:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。

    哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下(后面会探讨下哈希冲突的情况),仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

    我们知道,数据结构的物理存储结构只有两种:顺序存储结构链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组

    比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。
      
    这个函数可以简单描述为:存储位置 = f(关键字) ,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作:
    插入过程如下图所示
    哈希表数据插入过程

    查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

    哈希冲突

    然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。

    二、HashMap的实现原理

    HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。(其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合)

    //HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂。
    //至于为什么这么做,后面会有详细分析。
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    

    Entry是HashMap中的一个静态内部类。代码如下

        static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
            int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算
    
            /**
             * Creates new entry.
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            } 
    

    所以,HashMap的总体结构如下:
    在这里插入图片描述

    简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

    其他几个重要字段

    /**实际存储的key-value键值对的个数*/
    transient int size;
    
    /**阈值,当table == {}时,该值为初始容量(初始容量默认为16);当table被填充了,也就是为table分配内存空间后,
    threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold,后面会详细谈到*/
    int threshold;
    
    /**负载因子,代表了table的填充度有多少,默认是0.75
    加载因子存在的原因,还是因为减缓哈希冲突,如果初始桶为16,等到满16个元素才扩容,某些桶里可能就有不止一个元素了。
    所以加载因子默认为0.75,也就是说大小为16的HashMap,到了第13个元素,就会扩容成32。
    */
    final float loadFactor;
    
    /**HashMap被改变的次数,由于HashMap非线程安全,在对HashMap进行迭代时,
    如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作),
    需要抛出异常ConcurrentModificationException*/
    transient int modCount;
    

    HashMap有4个构造器,其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数,会使用默认值

    initialCapacity默认为16,loadFactory默认为0.75

    我们看下其中一个

    public HashMap(int initialCapacity, float loadFactor) {
         //此处对传入的初始容量进行校验,最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
            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;
            threshold = initialCapacity;
         
            init();//init方法在HashMap中没有实际实现,不过在其子类如 linkedHashMap中就会有对应实现
        }
    

    从上面这段代码我们可以看出,在常规构造器中,没有为数组table分配内存空间(有一个入参为指定Map的构造器例外),而是在执行put操作的时候才真正构建table数组

    OK,接下来我们来看看put操作的实现

    public V put(K key, V value) {
            //如果table数组为空数组{},进行数组填充(为table分配实际内存空间),入参为threshold,
            //此时threshold为initialCapacity 默认是1<<4(24=16)
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
           //如果key为null,存储位置为table[0]或table[0]的冲突链上
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);//对key的hashcode进一步计算,确保散列均匀
            int i = indexFor(hash, table.length);//获取在table中的实际位置
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            //如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value
                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++;//保证并发访问时,若HashMap内部结构发生变化,快速响应失败
            addEntry(hash, key, value, i);//新增一个entry
            return null;
        }
    

    inflateTable这个方法用于为主干数组table在内存中分配存储空间,通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂,比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

    private void inflateTable(int toSize) {
            int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
            /**此处为threshold赋值,取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值,
            capaticy一定不会超过MAXIMUM_CAPACITY,除非loadFactor大于1 */
            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
            table = new Entry[capacity];
            initHashSeedAsNeeded(capacity);
        }
    

    roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂,Integer.highestOneBit是用来获取最左边的bit(其他bit位为0)所代表的数值.

     private static int roundUpToPowerOf2(int number) {
            // assert number >= 0 : "number must be non-negative";
            return number >= MAXIMUM_CAPACITY
                    ? MAXIMUM_CAPACITY
                    : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
        }
    
    

    hash函数

    /**这是一个神奇的函数,用了很多的异或,移位等运算
    对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/
    final int hash(Object k) {
            int h = hashSeed;
            if (0 != h && k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
    
            h ^= k.hashCode();
    
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }
    

    以上hash函数计算出的值,通过indexFor进一步处理来获取实际的存储位置

    /**
         * 返回数组下标
         */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }
    

    h&(length-1)保证获取的index一定在数组范围内,举个例子,默认容量16,length-1=15,h=18,转换成二进制计算为index=2。位运算对计算机来说,性能更高一些(HashMap中有大量位运算)

    所以最终存储位置的确定流程是这样的:
    HashMap如何确定元素位置

    再来看看addEntry的实现:

    void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);//当size超过临界阈值threshold,并且即将发生哈希冲突时进行扩容
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
    

    通过以上代码能够得知,当发生哈希冲突并且size大于阈值的时候,需要进行数组扩容,扩容时,需要新建一个长度为之前数组2倍的新的数组,然后将当前的Entry数组中的元素全部传输过去,扩容后的新数组长度为之前的2倍,所以扩容相对来说是个耗资源的操作。

    三、为何HashMap的数组长度一定是2的次幂?

    我们来继续看上面提到的resize方法

    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, initHashSeedAsNeeded(newCapacity));
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }
    

    如果数组进行扩容,数组长度发生变化,而存储位置 index = h&(length-1),index也可能会发生变化,需要重新计算index,我们先来看看transfer这个方法

    void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
         //for循环中的代码,逐个遍历链表,重新计算索引位置,将老数组数据复制到新数组中去(数组不存储实际数据,所以仅仅是拷贝引用而已)
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    //将当前entry的next链指向新的索引位置,newTable[i]有可能为空,有可能也是个entry链,如果是entry链,直接在链表头部插入。
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }
    

    这个方法将老数组中的数据逐个链表地遍历,扔到新的扩容后的数组中,我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后,再通过和 length-1进行位运算得到最终数组索引位置。

    HashMap的数组长度一定保持2的次幂,比如16的二进制表示为 10000,那么length-1就是15,二进制为01111,同理扩容后的数组长度为32,二进制表示为100000,length-1为31,二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1,而扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换),个人理解。

    在这里插入图片描述

    还有,数组长度保持2的次幂,length-1的低位都为1,会使得获得的数组索引index更加均匀

    在这里插入图片描述
    我们看到,上面的&运算,高位是不会对结果产生影响的(hash函数采用各种位运算可能也是为了使得低位更加散列),我们只关注低位bit,如果低位全部为1,那么对于h低位部分来说,任何一位的变化都会对结果产生影响,也就是说,要得到index=21这个存储位置,h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。
    在这里插入图片描述
    如果不是2的次幂,也就是低位不是全为1此时,要使得index=21,h的低位部分不再具有唯一性了,哈希冲突的几率会变的更大,同时,index对应的这个bit位无论如何不会等于1了,而对应的那些数组位置也就被白白浪费了。

    get方法

     public V get(Object key) {
         //如果key为null,则直接去table[0]处去检索即可。
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
     }
    

    get方法通过key值返回对应value,如果key为null,直接去table[0]处检索。我们再看一下getEntry这个方法

    final Entry<K,V> getEntry(Object key) {
                
            if (size == 0) {
                return null;
            }
            //通过key的hashcode值计算hash值
            int hash = (key == null) ? 0 : hash(key);
            //indexFor (hash&length-1) 获取最终数组索引,然后遍历链表,通过equals方法比对找出对应记录
            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 != null && key.equals(k))))
                    return e;
            }
            return null;
        }    
    

    可以看出,get方法的实现相对简单,key(hashcode)–>hash–>indexFor–>最终索引位置,找到对应位置table[i],再查看是否有链表,遍历链表,通过key的equals方法比对查找对应的记录。要注意的是,有人觉得上面在定位到数组位置之后然后遍历链表的时候,e.hash == hash这个判断没必要,仅通过equals判断就可以。其实不然,试想一下,如果传入的key对象重写了equals方法却没有重写hashCode,而恰巧此对象定位到这个数组位置,如果仅仅用equals判断可能是相等的,但其hashCode和当前对象不一致,这种情况,根据Object的hashCode的约定,不能返回当前对象,而应该返回null,后面的例子会做出进一步解释。

    四、重写equals方法需同时重写hashCode方法

    最后我们再聊聊老生常谈的一个问题,各种资料上都会提到,“重写equals时也要同时覆盖hashcode”,我们举个小例子来看看,如果重写了equals而不重写hashcode会发生什么样的问题

    
    public class MyTest {
        private static class Person{
            int idCard;
            String name;
    
            public Person(int idCard, String name) {
                this.idCard = idCard;
                this.name = name;
            }
            @Override
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()){
                    return false;
                }
                Person person = (Person) o;
                //两个对象是否等值,通过idCard来确定
                return this.idCard == person.idCard;
            }
    
        }
        public static void main(String []args){
            HashMap<Person,String> map = new HashMap<Person, String>();
            Person person = new Person(1234,"乔峰");
            //put到hashmap中去
            map.put(person,"天龙八部");
            //get取出,从逻辑上讲应该能输出“天龙八部”
            System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
        }
    }
    
    实际输出结果:null
    

    如果我们已经对HashMap的原理有了一定了解,这个结果就不难理解了。尽管我们在进行get和put操作的时候,使用的key从逻辑上讲是等值的(通过equals比较是相等的),但由于没有重写hashCode方法,所以put操作时,key(hashcode1)–>hash–>indexFor–>最终索引位置 ,而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置,由于hashcode1不等于hashcode2,导致没有定位到一个数组位置而返回逻辑上错误的值null(也有可能碰巧定位到一个数组位置,但是也会判断其entry的hash值是否相等,上面get方法中有提到。)

    所以,在重写equals的方法的时候,必须注意重写hashCode方法,同时还要保证通过equals判断相等的两个对象,调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象,其hashCode可以相同(只不过会发生哈希冲突,应尽量避免)。

    五、JDK1.8中HashMap的性能优化

    假如一个数组槽位上链上数据过多(即拉链过长的情况)导致性能下降该怎么办?
    JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表超过8时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。
    关于这方面的探讨我们以后的文章再做说明。
    附:HashMap put方法逻辑图(JDK1.8)
    在这里插入图片描述

    展开全文
  • 深入理解HashMap(精华必看)

    万次阅读 多人点赞 2017-01-13 12:00:07
     Hashmap是一种非常常用的、应用广泛的数据类型,最近研究到相关的内容,就正好复习一下。网上关于hashmap的文章很多,但到底是自己学习的总结,就发出来跟大家一起分享,一起讨论。  1、hashmap的数据结构  ...

         原文地址:http://www.iteye.com/topic/539465


        Hashmap是一种非常常用的、应用广泛的数据类型,最近研究到相关的内容,就正好复习一下。网上关于hashmap的文章很多,但到底是自己学习的总结,就发出来跟大家一起分享,一起讨论。 


    1、hashmap的数据结构 
    要知道hashmap是什么,首先要搞清楚它的数据结构,在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,hashmap也不例外。Hashmap实际上是一个数组和链表的结合体(在数据结构中,一般称之为“链表散列“),请看下图(横排表示数组,纵排表示数组元素【实际上是一个链表】)。 


    从图中我们可以看到一个hashmap就是一个数组结构,当新建一个hashmap的时候,就会初始化一个数组。我们来看看java代码: 


    Java代码  收藏代码
    1. /** 
    2.      * The table, resized as necessary. Length MUST Always be a power of two. 
    3.      *  FIXME 这里需要注意这句话,至于原因后面会讲到 
    4.      */  
    5.     transient Entry[] table;  
    Java代码  收藏代码
    1. static class Entry<K,V> implements Map.Entry<K,V> {  
    2.         final K key;  
    3.         V value;  
    4.         final int hash;  
    5.         Entry<K,V> next;  
    6. ..........  
    7. }  


           上面的Entry就是数组中的元素,它持有一个指向下一个元素的引用,这就构成了链表。 
      当我们往hashmap中put元素的时候,先根据key的hash值得到这个元素在数组中的位置(即下标),然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了,那么在同一个位子上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。从hashmap中get元素时,首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到,如果每个位置上的链表只有一个元素,那么hashmap的get效率将是最高的,但是理想总是美好的,现实总是有困难需要我们去克服,哈哈~ 

    2、hash算法 
        我们可以看到在hashmap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合,所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表。 

    所以我们首先想到的就是把hashcode对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,能不能找一种更快速,消耗更小的方式那?java中时这样做的, 

    Java代码  收藏代码
    1. static int indexFor(int h, int length) {  
    2.        return h & (length-1);  
    3.    }  


        首先算得key得hashcode值,然后跟数组的长度-1做一次“与”运算(&)。看上去很简单,其实比较有玄机。比如数组的长度是2的4次方,那么hashcode就会和2的4次方-1做“与”运算。很多人都有这个疑问,为什么hashmap的数组初始化大小都是2的次方大小时,hashmap的效率最高,我以2的4次方举例,来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。 

        看下图,左边两组是数组长度为16(2的4次方),右边两组是数组长度为15。两组的hashcode均为8和9,但是很明显,当它们和1110“与”的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8和9会被放到同一个链表上,那么查询的时候就需要遍历这个链表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hashcode的值会与14(1110)进行“与”,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率! 


       

        所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。 
        说到这里,我们再回头看一下hashmap中默认的数组大小是多少,查看源代码可以得知是16,为什么是16,而不是15,也不是20呢,看到上面annegu的解释之后我们就清楚了吧,显然是因为16是2的整数次幂的原因,在小数据量的情况下16比15和20更能减少key之间的碰撞,而加快查询的效率。 

        所以,在存储大容量数据的时候,最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话,也会以大于且最接近指定值大小的2次幂来初始化的,代码如下(HashMap的构造方法中): 

    且最接近指定值大小的2次幂来初始化的,代码如下(HashMap的构造方法中): 

    Java代码  收藏代码
    1. // Find a power of 2 >= initialCapacity  
    2.         int capacity = 1;  
    3.         while (capacity < initialCapacity)   
    4.             capacity <<= 1;  

    3、hashmap的resize 
           当hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对hashmap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作,很多人对它的性能表示过怀疑,不过想想我们的“均摊”原理,就释然了,而在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。 

             那么hashmap什么时候进行扩容呢?当hashmap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。比如说,我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适,不过上面annegu已经说过,即使是1000,hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的,因为0.75*1000 < 1000, 也就是说为了让0.75 * size >1000, 我们必须这样new HashMap(2048)才最合适,既考虑了&的问题,也避免了resize的问题。 


    4、key的hashcode与equals方法改写 
    在第一部分hashmap的数据结构中,annegu就写了get方法的过程:首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。所以,hashcode与equals方法对于找到对应元素是两个关键方法。 

    Hashmap的key可以是任何类型的对象,例如User这种对象,为了保证两个具有相同属性的user的hashcode相同,我们就需要改写hashcode方法,比方把hashcode值的计算与User对象的id关联起来,那么只要user对象拥有相同id,那么他们的hashcode也能保持一致了,这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素,还需要用key的equals方法在对应位置的链表中找到需要的元素,所以只改写了hashcode方法是不够的,equals方法也是需要改写滴~当然啦,按正常思维逻辑,equals方法一般都会根据实际的业务内容来定义,例如根据user对象的id来判断两个user是否相等。 
    在改写equals方法的时候,需要满足以下三点: 
    (1) 自反性:就是说a.equals(a)必须为true。 
    (2) 对称性:就是说a.equals(b)=true的话,b.equals(a)也必须为true。 
    (3) 传递性:就是说a.equals(b)=true,并且b.equals(c)=true的话,a.equals(c)也必须为true。 
    通过改写key对象的equals和hashcode方法,我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要)。 

    总结: 
        本文主要描述了HashMap的结构,和hashmap中hash函数的实现,以及该实现的特性,同时描述了hashmap中resize带来性能消耗的根本原因,以及将普通的域模型对象作为key的基本要求。尤其是hash函数的实现,可以说是整个HashMap的精髓所在,只有真正理解了这个hash函数,才可以说对HashMap有了一定的理解。 


    展开全文
  • HashMap底层实现和原理(源码解析)

    万次阅读 多人点赞 2019-06-15 10:14:34
    Note:文章的内容基于JDK1.7进行分析,1.8做的改动文章末尾进行...HashMap基于Map接口实现,元素以键值对的方式存储,并且允许使用null 建和null 值, 因为key不允许重复,因此只能有一个键为null,另外HashMap不...
  • Map集合类——HashMap

    千次阅读 2019-05-21 16:08:31
    Map集合的实现类:HashTable、LinkedHashMap、HashMap、TreeMap 1、HashMap 1.1、基础了解: 1、键不可以重复,值可以重复; 2、底层使用哈希表实现; 3、线程不安全; 4、允许key为null,但只允许有一条记录为...
  • Java技术栈www.javastack.cn优秀的Java技术公众号一、什么是哈希表在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能数组采用一段连续的存储单...
  • 轻松理解 Java HashMap 和 ConcurrentHashMap

    千次阅读 2018-08-23 14:03:11
    本篇主要想讨论 ConcurrentHashMap 这样一个并发容器,在正式开始之前我觉得有必要谈谈 HashMap,没有它就不会有后面的 ConcurrentHashMap。 HashMap 众所周知 HashMap 底层是基于 数组 + 链表 组成的,不过在 ...
  • 【java】HashMap 一遍就懂!!!!

    万次阅读 多人点赞 2019-07-28 11:18:15
    HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和...
  • 什么是HashMap

    万次阅读 多人点赞 2018-05-22 01:36:15
    接下来写的内容是看过众多大神的文章后,自己总结的一些心得体会,主要是为了让大家快速理解HashMap,应付面试百分百足矣。当然讲HashMap之前必须先讲一些必备知识(等你回答完面试官问题,再深入问下去的时候,这些...
  • java提高篇(二三)-----HashMap

    万次阅读 多人点赞 2014-01-15 21:41:46
     HashMap也是我们使用非常多的Collection,它是基于哈希表的 Map 接口的实现,以key-value的形式存在。在HashMap中,key-value总是会当做一个整体来处理,系统会根据hash算法来来计算key-value的存储位置,我们总是...
  • HashMap原理深入理解

    万次阅读 多人点赞 2018-04-23 00:35:41
    hashing(散列法或哈希法)的概念 散列法(Hashing)是一种将字符组成的字符串转换为固定长度(一般是更短长度)的...HashMap概念和底层结构 HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映...
  • HashMap底层实现原理及面试问题

    万次阅读 多人点赞 2018-08-29 11:00:56
    HashMap的工作原理 HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取...
  • HashMap底层实现原理

    万次阅读 多人点赞 2018-09-21 17:14:18
    HashMap实现原理及源码分析  哈希表(hash table)也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,而HashMap实现原理也...
  • Java中HashMap底层实现原理(JDK1.8)源码分析

    万次阅读 多人点赞 2016-06-05 11:13:44
    这几天学习了HashMap底层实现,但是发现好几个版本的,代码不一,而且看了Android包的HashMap和JDK中的HashMap的也不是一样,原来他们没有指定JDK版本,很多文章都是旧版本JDK1.6.JDK1.7的。现在我来分析一哈最新的...
  • 【JAVA】HashMap底层实现原理浅谈

    万次阅读 2018-10-07 17:28:35
    HashMap底层实现原理浅谈 不论是实习还是正式工作,HashMap的底层实现原理一直是问地频率最高的一个内容,今天记录一下自己对HashMap的理解,如有不当之处,还请各位大佬指正。 一、前置名词解释 (1)哈希表 ...
  • 面试题 HashMap底层实现原理

    千次阅读 2019-04-20 17:30:04
    HashMap实现了Map接口,Map接口对键值对进行映射。Map接口的两个基本实现HashMap和TreeMap。TreeMap保证了对象的排列次序,而HashMap是无序的。HashMap的键和值可以赋值为null。HashMap是非synchronized的,可以...
  • HashMap底层实现原理 扩容机制

    万次阅读 热门讨论 2019-02-26 16:58:25
    实现原理HashMap本质是一个一定长度的数组,数组中存放的是链表。 它是一个Entry类型的数组,Entry的源码: static class Entry&lt;K,V&gt; implements Map.Entry&lt;K,V&gt; { final K ...
  • JAVA里面有HashMap、HashTable、HashSet三种常用的Hash集合,由于经常性的使用,所以想了解一下三种集合的底层实现以及区别,在这里进行总结:一:HashMap和HashTable的区别1.HashTable是线程安全的,而HashMap是...
  • HashMap的工作原理 HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来...
  • 下面介绍基于jdk1.8深入了解HashMap底层原理。 HashMap数据结构 HashMap实际是一种“数组+链表”数据结构。在put操作中,通过内部定义算法寻止找到数组下标,将数据直接放入此数组元素中,若通过算法得到的该数组...
  • HashMap 底层实现原理及常见面试题

    千次阅读 2019-07-29 09:46:48
    文章目录hashmap的特性hashmap的工作原理两个对象的hashcode相同会发生什么?造成hash冲突的原因如何解决hash碰撞如何减少hash碰撞为什么String, Interger这样的wrapper类适合作为键?重新调整HashMap的大小你可能会...
  • hashmap算法优劣标准 1.分布均匀 2.尽量避免冲突 关于hashMap的几个问题 1、hashing的概念 这个是一个hash算法,将Key对象通过hashing的到需要存储值对象的位置bucket。 2、HashMap中解决碰撞的方法 根据key...
  • https://segmentfault.com/a/1190000021928659 https://baijiahao.baidu.com/s?id=1645429373049393021&wfr=spider&for=pc
  • Java面试绕不开的问题: Java中HashMap底层实现原理(JDK1.8)源码分析
  • 首先HashMap是Map的一个实现类,而Map存储形式是键值对(key,value)的。可以看成是一个一个的Entry。Entry所存放的位置是由key来决定的。 Map中的key是无序的且不可重复的,所有的key可以看成是一个set集合,如果...
  • HashMap的工作原理 HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取...
  • hashMap实现原理

    万次阅读 多人点赞 2019-07-31 18:35:50
     HashMap是基于哈希表的Map接口的非同步实现(Hashtable跟HashMap很像,唯一的区别是Hashtalbe中的方法是线程安全的,也就是同步的)。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的...
  • HashMap底层原理

    2019-09-28 11:52:32
    HashMap底层原理
  • HashMap底层实现原理

    千次阅读 2018-10-16 09:49:52
    最近做的几个项目都是用Map来存储的数据 ,虽然用得挺顺手,但是对HashMap底层原理却只知甚少,今天便来简单学习和整理一下。  数据结构中有数组和链表这两个结构来存储数据。  数组存储区间是连续的,占用...

空空如也

1 2 3 4 5 ... 20
收藏数 656,105
精华内容 262,442
关键字:

hashmap