精华内容
下载资源
问答
  • HashMap面试题

    2021-01-22 00:23:04
    HashMap面试题: 1)JDK1.7与JDK1.8HashMap有什么区别和联系 2)用过HashMap没?说说HashMap的结构(底层数据结构 + put方法描述) 3)说说HashMap的扩容过程 4)HashMap中可以使用自定义类型作为其key和...

    1、JDK1.7与JDK1.8HashMap有什么区别和联系

    区别:
    JDK1.7下:
    1)底层所采用的是数组加链表的结构
    2)采用头插法
    3)扩容方式:直接用其hash值和需要扩容的二进制数进行&(这里的扩容时必须是2的幂次方,因为只有这样其二进制的最后一位才会是1,用来减少哈希冲突),(hash&table.length-1),另其是在插入后进行扩容
    4)会先对数组进行初始化,然后进行put
    JDK1.8下:
    1)底层采用的是数组+链表+红黑树,当链表长度大于8并且数组长度大于64时,会形成红黑树。
    红黑树的特点:
    每个节点只有两种颜色,红色或是黑色,根节点必须为黑
    每个叶子结点都是黑色的空结点
    从根结点到叶子结点时不能出现两个连续的红色结点
    从任意结点出发,到它下边的子结点的路径包=包含的黑色结点数目相同
    2)采用尾插法,原因是在JDK1.7时单链表进行的纵向延伸,当采用头插法时会容易出现逆序且环形链表死循环问题,而1.8下的尾插法可以解决这个问题
    3)扩容方式:计算hash的方法yuJDK1.7有所不同,另其是在插入前进行扩容
    4)会先进行put方法,如哦没有初始化,则在put方法内进行初始化

    2.说说HashMap的结构(底层数据结构 + put方法描述)

    HashMap的底层是由数组+链表+红黑树。
    数组在给定下标的查找的时间复杂度为O(1),增添、删除的时间复杂度为O(n)。链表的查找的时间复杂度为O(n),增添删除的时间复杂度为O(1)。哈希表在没有哈希冲突的情况下的查找、增添、删除的时间复杂度为O(1)。
    HashMap的主体是一个Entry数组,主干数组的长度一定为2的幂次方。
    对于HashMap中的put方法来说,首先可以得到一个index,判断table[index]是否为空,为空则new一个Node放进去,如果不为空则判断其的key值与所要添加的key值是否相同,如果相同则新值替换旧值,如果不同则判断其是否为TreeNode,如果是则进行红黑树的添加,如果不是则进行链表的遍历,比较其key值,如果key值相同则新值覆盖旧值,如果key不同则new一个Node利用尾插法插入链表中,最后判断其长度是否大于8,大于转化为红黑树,不大于则比较++size和threshold的值,如果size>threshold,则需要扩容。
    在这里插入图片描述

    3.说说HashMap的扩容过程

    HashMap只有在内部数组无法装载更多对象时,即size>threshold时需要对数组进行二倍扩容。
    对原数组中的数据进行重新rehash。
    rehash的结果,该值在原数组和新数组的位置相同或该值在新数组中的位置等于该值在原数组中的位置加上原数组的长度。

    4.HashMap中可以使用自定义类型作为其key和value吗?

    可以
    如果是自定义的比较器时需要重写equals()方法和hashCode()方法。

    5.HashMap中table.length为什么需要是2的幂次方

    例如:给定值为8,在数组长度为4的表中
    hash&length-1
    0000 1000 & 0000 0011 =0000 0000 index=0
    hash&length
    0000 1000 & 0000 0100 =0000 0000 index=0
    给定值为4
    hash&length-1
    0000 0100 &0000 0011 =0000 0100 index=4
    hash&length
    0000 0100 &0000 0100 =0000 0100 index

    6.HashMap与HashTable的区别和联系?

    • 相同点:
      都实现了Map接口,保存了Key-Value(键值对)
    • 不同点:
      1.HashMap继承AbstractMap类,而HashTable继承Dictionary类。
      2.HashMap是线程不安全的,是非Synchronize(同步)的,而HashTable是线程安全的,是Synchronize的。
      3.HashTable中key和value都不允许为null,HashMap中空值可以作为Key,也可以有一个/多个Key的值为空值。
      4.HashMap的hash数组默认长度大小为16,扩容方式为2的指数,HashTable的hash数组默认长度大小为11,扩容方式为两倍加一。

    7.HashMap与WeakHashMap的区别和联系?

    相同点:
    1)HashMap和WeakHashMap都继承AbstractMap
    2)HashMap和WeakHashMap都实现了Map接口
    3)HashMap和WeakHashMap都保存了key-value键值对
    4)HashMap和WeakHashMap一般用于单线程中,是非线程安全的
    5)HashMap和WeakHashMap最多只允许一条key为Null,允许多条value为Null
    6)HashMap和WeakHashMap添加、删除操作时间复杂度都是O(1)。
    7)HashMap和WeakHashMap都是非Synchronize(同步)的
    不同点:
    1)HashMap的键是"强键",weakHashMap中的键是"弱键"(当弱键被垃圾回收GC回收时,其对应的键值也会从WeakHashMap中删除)
    2)

    8.HashMap和LinkedHashMap的区别与联系?

    相同点:
    1)HashMap和LinkedHashMap添加、删除操作时间复杂度都是O(1)
    2)HashMap和LinkedHashMap最多只允许一条key为Null,允许多条value为Null
    不同点:
    1)HashMap继承AbstractMap,LinkedHashMap继承HashMap
    2)HashMap基于Key-Value的散列表,LinkedHashMap是基于双向链表散列
    3)HashMap在遍历时是无序的,LinkedHashMap遍历时按照插入的顺序或者访问的顺序进行遍历

    9.HashMap和TreeMap的区别与联系?

    相同点:
    1)HashMap(JDK1.8下)和TreeMap都是基于数组加链表实现的
    2)HashMap和TreeMap都是非线程安全的
    不同点:
    1)HashMap继承于抽象类AbstractMap,并且实现Map接口,TreeMap实现SortedMap接口
    2)HashMap遍历时,取得的数据完全是随机的,TreeMap默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的
    3)HashMap添加、删除操作时间复杂度都是O(1),TreeMap添加、删除操作时间复杂度都是O(log(n))
    4)HashMap最多只允许一条key为Null,允许多条value为Null,TreeMap只允许value为Null,key不能为Null

    展开全文
  • HashMap面试题.pdf

    2021-01-27 13:43:10
    HashMap面试题
  • hashmap面试题.png

    2019-07-07 11:13:49
    hashmap面试题.png
  • hashmap相关的面试题
  • HashMap面试题汇总

    2019-04-16 17:18:35
    HashMap面试题汇总 1,HashMap底层存储结构 HashMap在Jdk1.7的时候采用的是数组加链表的数据结构,jdk1.8之后采用了数组加链表加红黑树的数据结构。观察源码可知HashMap类中有一个非常重要的字段就是Node[] table,...

    HashMap面试题汇总

    1,HashMap底层存储结构

    HashMap在Jdk1.7的时候采用的是数组加链表的数据结构,jdk1.8之后采用了数组加链表加红黑树的数据结构。观察源码可知HashMap类中有一个非常重要的字段就是Node[] table,即哈希桶数组。而Node是HashMap的一个内部类,实现了Map.Entry接口,本身就是一个键值对。

    2,解决Hash冲突的方法,HashMap采用了什么方法解决Hash冲突?

    HashMap使用哈希表来存储数据的,当然哈希表不可避免的就会遇到hash冲突问题,解决hash冲突的方法大致有两种:1,开放地址法。2,链地址法。

    1,开放地址法:当地址发生冲突时,按着某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。

    2,链地址法:链地址法就是数组加链表的结合,在每一个数组元素上都有一个链表结构,当地址发生冲突时就讲数据存放在链表中。

    而HashMap就是采用链地址法进行解决hash冲突的。

    3,jdk1.8的HashMap中的链表达到多少个时会生成红黑树?

    HashMap用链地址法解决hash冲突,则当链表里的长度太长就会严重影响HashMap的性能。于是在jdk1.8里,对数据结构做了进一步优化,引入了红黑树,当链表长度大于8的时候,链表就会转成红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。

    3,HashMap初始值的大小和负载因子的大小?

    hashMap初始长度就是16,负载因子是0.75。HashMap所容纳的最大数据量为:长度*负载因子。即当长度达到这个值的时候就会发生扩容。

    4,HashMap扩容机制

    扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。底层是resize方法中的transfer方法将原有的Entry数组的元素拷贝到新的Entry数组里,扩容都是以2的N次幂进行扩容 一般是2倍。

    5,HashMap线程安全问题 HashTable ConcurrentHashMap

    HashMap是线程不安全的,多个线程同时写HashMap可能会导致数据的不一致。如果需要满足线程安全可以用ConcurrentHashMap,还有一个HashTable。但是HashTable是继承自Dictionary类,HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下,HashTable的效率非常低下,ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成,采用segment分段锁来保证线程安全。

    HashTable无论key或value都不能为null,HashMap只能允许一个key为null,可以运行多个value为null。而且HashTable是线程安全的,HashMap是线程不安全的。

    6,HashMap链表成环

    由于HashMap线程不安全的,至于为何不安全,什么时候会出现问题,这里来讨论一下:

    当有多个线程共同操作hashMap的put方法时,这个时候hashMap容量不够了,两个线程都去扩容执行resize方法,在这个时候cpu切换资源的话,会造成链表成环问题,死循环问题。

    展开全文
  • 一.hashMap面试题

    2021-04-23 14:58:40
    一.hashMap面试题 1.hashMap的特点 hashMap采用数组加链表的结构实现。 hashMap是线程不安全的。对应线程安全的hashTable。但是官方推荐使用ConcurrentHashMap hahMap可以key值和value都可以存储null. ...

    一.hashMap面试题

    1.hashMap的特点

       hashMap采用数组加链表的结构实现。

       hashMap是线程不安全的。对应线程安全的hashTable。但是官方推荐使用ConcurrentHashMap

       hahMap可以key值和value都可以存储null.

       hashMap的默认容量是16,加载因子为0.75(默认).

    2.hashMap的put操作

    当执行put操作时,会对key进行hashCode运算((h = key.hashCode()) ^ (h >>> 16))然后取余,来找到数组中的位置。判断数组中是否存在,存在则把链表拿出来,判断链表中是否有相同的key,如果有,则替换旧值,如果没有,则add在链表末端。

    当阀值>容量*加载因子0.75时,hashMap则会进行2倍的扩容

    3.jdk1.8hashMap采用数组+链表+红黑树实现,当链表长度大于8时,则会将数组链表结构转换为数组加红黑树。

    好处:红黑树的查询性能为log(n),而链表的的查询性能为(n))

     

    二.ConcurrentHashMap面试题

     

     

     

     

    展开全文
  • 源码解析不会通篇解析,会通过面试题整理来针对性地解析其中的关键点主要的几个面试题HashMap的底层原理是什么?线程安全么?HashMap中put是如何实现的?谈一下hashMap中什么时候需要进行扩容,扩容resize()又是...

    源码解析不会通篇解析,会通过面试题整理来针对性地解析其中的关键点

    主要的几个面试题:

    HashMap的底层原理是什么?线程安全么?

    HashMap中put是如何实现的?

    谈一下hashMap中什么时候需要进行扩容,扩容resize()又是如何实现的?

    什么是哈希碰撞?怎么解决?

    HashMap和HashTable的区别

    HashMap中什么时候需要进行扩容,扩容resize()是如何实现的?

    hashmap concurrenthashmap原理

    arraylist和hashmap的区别,为什么取数快?

    1. HashMap的底层原理是什么?线程安全么?

    HashMap的底层原理是链表的数组, 通过hash算法计算出 key的hash值再根据数组长度取模得到index 如果index相同,那么就排在同一个链表中。链表中根据key的hash值大小有序排列方便查找

    2858fbee58be

    内部结构

    jdk 1.8 之后 androidsdk 24 之后 hashmap 的内部实现有链表改为 链表加红黑树实现,当一个链表的长度大于 8之后将会在后续添加的时候转变为红黑树

    2858fbee58be

    红黑树

    get: 先通过hash算法计算出key的hash值 然后再通过hash根据 链表数组的长度取模 获得index。根据index去循环链表或者红黑树取到相应的value。

    put: 先通过hash算法计算出key的hash值 然后再通过hash根据 链表数组的长度取模 获得index,再根据排列顺序将 entry放到链表或者红黑树中。

    线程不安全,当多个线程操作的时候可能使读取的数据为错误数据。

    2. HashMap中put是如何实现的?

    简单过程:先通过hash算法计算出key的hash值 然后再通过hash根据 链表数组的长度取模 获得index,再根据排列顺序将 entry放到链表或者红黑树中。

    看代码:

    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[] tab; Node p; int n, i;

    if ((tab = table) == null || (n = tab.length) == 0)

    n = (tab = resize()).length;

    // Step 1 获取hashmap中链表数组的长度(其中包含了一个重要的步骤 resize 之后在沟通)

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

    // 此处 p指向了tab数值中对应index元素链表的头结点

    tab[i] = newNode(hash, key, value, null);

    // Step 2 对key值的hash对 长度取模 ( (n - 1) & hash 等价于 hash % n ,此处采用位运算是为了性能考虑)得到i。

    // 再检查数组i元素是否存在,如果不存在将node 赋值

    else {

    Node e; K k;

    if (p.hash == hash &&

    ((k = p.key) == key || (key != null && key.equals(k))))

    // Step 3 如果key相同 用e标记,指向p,后面将会把新的value 赋值给p节点

    e = p;

    else if (p instanceof TreeNode)

    // 如果链表开始就是 树结构的 那么用树结构的逻辑将节点保存

    e = ((TreeNode)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;

    }

    展开全文
  • 21 个刁钻的 HashMap 面试题
  • HashMap面试题知识大全

    千次阅读 多人点赞 2020-04-13 15:13:39
    HashMap常见面试题: 1.HashMap的底层数据结构? 2. HashMap的存取原理? 3. Java7和Java8的区别? 4. 为啥会线程不安全? 5. 有什么线程安全的类代替么? 6. 默认初始化大小是多少?为啥是这么多?为啥大小都是2的幂...
  • 别急HashMap面试题,看这一篇就够了 序言 在后端的日常开发工作中,集合是使用频率相当高的一个工具,而其中的HashMap,则更是我们用以处理业务逻辑的好帮手,同时HashMap的底层实现和原理,也成了面试题中的常客。...
  • HashMap面试题总结

    千次阅读 2020-07-03 11:21:44
    文章目录HashMap简介问题集合问点一:你了解HashMap的底层数据结构吗?问点二:为什么JDK 7使用数组+链表?JDK8中为什么要使用红黑树?哈希冲突是怎么回事?HashMap又是怎么解决的?问点三:HashMap的扩容机制是怎么...
  • 面试造飞机系列:用心整理的HashMap面试题,以后都不用担心了
  • HashMap面试题,看这一篇解决所有疑惑 转载:https://www.toutiao.com/a6765818992150970884/?timestamp=1575474656&app=news_article&group_id=6765818992150970884&req_id=...
  • HashMap面试题:90%的人回答不上来 2017年11月06日 21:54:26 阅读数:870 标签: 面试题 java hashmap实现原理 更多 个人分类: 程序人生 版权声明:本文为博主原创文章,转载请注明出处。 ...
  • java HashMap 面试题

    2020-05-21 00:15:54
    hashMap 底层数据结构 1.数组+链表,链表长度大于8 转红黑树 hashmap 算法优化 . hashcode计算优化 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>...
  • Java中简单易懂的HashMap面试题(面试必备)

    千次阅读 多人点赞 2020-05-29 12:06:23
    HashMap的底层是数组+链表,(很多人应该都知道了) JDK1.7的是数组+链表 (1.7只是一个例子,以前的话也是这样后面就以1.7为例子了) 首先是一个数组,然后数组的类型是链表 元素是头插法 JDK1.8的是数组+链表 或者...
  • HashMap的工作原理是近年...几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考察的深度很深。这题经常出现在高级...
  • 史上最全HashMap面试题汇总

    千次阅读 多人点赞 2020-07-13 19:44:14
    1.HashMap的数据结构? 哈希表结构(链表散列:数组+链表)实现,结合数组和链表的优点。当链表长度超过8时,链表转换为红黑树。 2.HashMap的工作原理? HashMap底层是hash数组和单向链表实现,数组中的每个元素都是链表,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 66,623
精华内容 26,649
关键字:

hashmap面试题