java集合框架Map

DBC 688 0

1.集合框架里面基础Map面试题

了解Map吗?用过哪些Map的实现

温馨提示

答:HashMap、Hashtable、LinkedHashMap、TreeMap、ConcurrentHashMap

说下 HashMap和Hashtable 的区别

温馨提示

答:

HashMap:底层是基于数组+链表,非线程安全的,默认容量是16、允许有空的健和值
Hashtable:基于哈希表实现,线程安全的(加了synchronized),默认容量是11,不允许有null的健和值

2.对象的比较、排重 hashcode和equals经常需要重写,也是map和set里面常用知识

介绍下对象的 hashCode()和equals(),使用场景

温馨提示

hashcode
顶级类Object里面的方法,所有的类都是继承Object,返回是一个int类型的数
根据一定的hash规则(存储地址,字段,长度等),映射成一个数组,即散列值

equals
顶级类Object里面的方法,所有的类都是继承Object,返回是一个boolean类型
根据自定义的匹配规则,用于匹配两个对象是否一样,一般逻辑如下
//判断地址是否一样
//非空判断和Class类型判断
//强转
//对象里面的字段一一匹配

使用场景:对象比较、或者集合容器里面排重、比较、排序

代码实战: 编写一个User对象,重写里面的hashcode和equal方法

import java.util.Date;
import java.util.Objects;

public class User {
    private int age;
    private String name;
    private Date time;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Date getTime() {
        return time;
    }

    public void setTime(Date time) {
        this.time = time;
    }

    @Override
    public int hashCode() {
        //int code = age/name.length()+time.hashCode();
        //return code
        //推荐下面这个
        return Objects.hash(age, name, time);
    }

    @Override
    public boolean equals(Object obj) {

        if (this == obj) return true;

        if (obj == null || getClass() != obj.getClass()) return false;

        User user = (User) obj;
        return
                age == user.age &&
                Objects.equals(name,user.name)&&
                Objects.equals(time,user.time);
    }
}

3.Map 相关基础知识掌握情况

HashMap和TreeMap应该怎么选择,使用场景

温馨提示

hashMap: 散列桶(数组+链表),可以实现快速的存储和检索,但是确实包含无序的元素,适用于在map中插入删除和定位元素

treeMap:使用存储结构是一个平衡二叉树->红黑树,可以自定义排序规则,要实现Comparator接口
能便捷的实现内部元素的各种排序,但是一般性能比HashMap差,适用于安装自然排序或者自定义排序规则
(写过微信支付签名工具类就用这个类)

Set和Map的关系

温馨提示

核心就是不保存重复的元素,存储一组唯一的对象
set的每一种实现都是对应Map里面的一种封装,
HashSet对应的就是HashMap,treeSet对应的就是treeMap

常见Map的排序规则是怎样的?

温馨提示

按照添加顺序使用LinkedHashMap,按照自然排序使用TreeMap,自定义排序 TreeMap(Comparetor c)

4.集合框架里面基础Map面试题进阶

如果需要线程安全,且效率高的Map,应该怎么做?

温馨提示

答案:多线程环境下可以用concurrent包下的ConcurrentHashMap, 或者使用Collections.synchronizedMap(),

ConcurrentHashMap虽然是线程安全,但是他的效率比Hashtable要高很多

为什么Collections.synchronizedMap后是线程安全的?

温馨提示

答案:使用Collections.synchronizedMap包装后返回的map是加锁的

5.深入底层HashMap实现原理

看过HashMap源码吗,介绍下你了解的HashMap

温馨提示

答案:
看过源码

HashMap底层(数组+链表+红黑树 jdk8才有红黑树)

数组中每一项是一个链表,即数组和链表的结合体

Node<K,V>[] table 是数组,数组的元素是Entry(Node继承Entry),Entry元素是一个key-value的键值对,它持有一个指向下个Entry的引用,table数组的每个Entry元素同时也作为当前Entry链表的首节点,也指向了该链表的下个Entry元素

在JDK1.8中,链表的长度大于8,链表会转换成红黑树

java集合框架Map插图

能否解释下什么是Hash碰撞?常见的解决办法有哪些,hashmap采用哪种方法

温馨提示

答:
hash碰撞的意思是不同key计算得到的Hash值相同,需要放到同个bucket中

常见的解决办法:链表法、开发地址法、再哈希法等

HashMap采用的是链表法

补充知识

链表法

链表法解决冲突问题构造的哈希表/LRU缓存淘汰算法

链表法

开放地址法

开放地址法

这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – 1))
其中: H ( key ) 为关键字 key 的直接哈希地址, m 为哈希表的长度, di 为每次再探测时的地址增量。
采用这种方法时,首先计算出元素的直接哈希地址 H ( key ) ,如果该存储单元已被其他元素占用,则继续查看地址为 H ( key ) + d 2 的存储单元,如此重复直至找到某个存储单元为空时,将关键字为 key 的数据元素存放到该单元。
增量 d 可以有不同的取法,并根据其取法有不同的称呼:
( 1 ) d i = 1 , 2 , 3 , …… 线性探测再散列;
( 2 ) d i = 1^2 ,- 1^2 , 2^2 ,- 2^2 , k^2, -k^2…… 二次探测再散列;
( 3 ) d i = 伪随机序列 伪随机再散列;

例1设有哈希函数 H ( key ) = key mod 7 ,哈希表的地址空间为 0 ~ 6 ,对关键字序列( 32 , 13 , 49 , 55 , 22 , 38 , 21 )按线性探测再散列和二次探测再散列的方法分别构造哈希表。
解:
( 1 )线性探测再散列:
32 % 7 = 4 ; 13 % 7 = 6 ; 49 % 7 = 0 ;
55 % 7 = 6 发生冲突,下一个存储地址( 6 + 1 )% 7 = 0 ,仍然发生冲突,再下一个存储地址:( 6 + 2 )% 7 = 1 未发生冲突,可以存入。
22 % 7 = 1 发生冲突,下一个存储地址是:( 1 + 1 )% 7 = 2 未发生冲突;
38 % 7 = 3 ;
21 % 7 = 0 发生冲突,按照上面方法继续探测直至空间 5 ,不发生冲突,所得到的哈希表对应存储位置:
下标: 0 1 2 3 4 5 6
49 55 22 38 32 21 13
( 2 )二次探测再散列:
下标: 0 1 2 3 4 5 6
49 22 21 38 32 55 13
注意:对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时需要谨慎,不能直接地删除,因为这样将会截断其他具有相同哈希地址的元素的查找地址,所以,通常采用设定一个特殊的标志以示该元素已被删除。 

再哈希法

再哈希法

再哈希法其实很简单,就是再使用哈希函数去散列一个输入的时候,输出是同一个位置就再次哈希,直至不发生冲突位置

缺点:每次冲突都要重新哈希,计算时间增加。

总结

一、拉链法

HashMap,HashSet其实都是采用的拉链法来解决哈希冲突的,就是在每个位桶实现的时候,我们采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)。首先来看使用拉链法解决哈希冲突的几个操作:

①插入操作:在发生哈希冲突的时候,我们输入域的关键字去映射到位桶(实际上是实现位桶的这个数据结构,链表或者红黑树)中去的时候,我们先检查带插入元素x是否出现在表中,很明显,这个查找所用的次数不会超过装载因子(n/m:n为输入域的关键字个数,m为位桶的数目),它是个常数,所以插入操作的最坏时间复杂度为O(1)的。

②查询操作:和①一样,在发生哈希冲突的时候,我们去检索的时间复杂度不会超过装载因子,也就是检索数据的时间复杂度也是O(1)的

③删除操作:如果在拉链法中我们想要使用链表这种数据结构来实现位桶,那么这个链表一定是双向链表,因为在删除一个元素x的时候,需要更改x的前驱元素的next指针的属性,把x从链表中删除。这个操作的时间复杂度也是O(1)的。

拉链法的优点

与开放定址法相比,拉链法有如下几个优点:

①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

 

拉链法的缺点

指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

使用例子:

HashMap

二、开发地址法

开放地址法有个非常关键的特征,就是所有输入的元素全部存放在哈希表里,也就是说,位桶的实现是不需要任何的链表来实现的,换句话说,也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法(探查序列),去寻找下一个地址,若发生冲突再去寻找,直至找到一个为空的地址为止。所以这种方法又称为再散列法。

有几种常用的探查序列的方法:

①线性探查

dii=1,2,3,…,m-1;这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

(使用例子:ThreadLocal里面的ThreadLocalMap)

②二次探查

di=12,-12,22,-22,…,k2,-k2 ( k<=m/2 );这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

③ 伪随机探测

di=伪随机数序列;具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),生成一个位随机序列,并给定一个随机数做起点,每次去加上这个伪随机数++就可以了。

三、再哈希法

再哈希法其实很简单,就是再使用哈希函数去散列一个输入的时候,输出是同一个位置就再次哈希,直至不发生冲突位置

缺点:每次冲突都要重新哈希,计算时间增加。

以上总结内容转载自:解决哈希冲突的三种方法(拉链法、开放地址法、再哈希法)
https://blog.csdn.net/qq_32595453/article/details/80660676

立即前往

6.深入底层HashMap实现原理

你说HashMap底层是 数组+链表+红黑树,为什么要用这几类结构呢?

解析

答案:
数组 Node<K,V>[] table ,根据对象的key的hash值进行在数组里面是哪个节点

链表的作用是解决hash冲突,将hash值一样的对象存在一个链表放在hash值对应的槽位

红黑树 JDK8使用红黑树来替代超过8个节点的链表,主要是查询性能的提升,从原来的O(n)到O(logn),
通过hash碰撞,让HashMap不断产生碰撞,那么相同的key的位置的链表就会不断增长,当对这个Hashmap的相应位置进行查询的时候,就会循环遍历这个超级大的链表,性能就会下降,所以改用红黑树

java集合框架Map插图

为啥选择红黑树而不用其他树,比如二叉查找树,为啥不一直开始就用红黑树,而是到8的长度后才变换

温馨提示

答案:二叉查找树在特殊情况下也会变成一条线性结构,和原先的链表存在一样的深度遍历问题,查找性能就会慢,
使用红黑树主要是提升查找数据的速度,红黑树是平衡二叉树的一种,插入新数据后会通过左旋,右旋、变色等操作来保持平衡,解决单链表查询深度的问题

数据量少的时候操作数据,遍历线性表比红黑树所消耗的资源少,且前期数据少 平衡二叉树保持平衡是需要消耗资源的,所以前期采用线性表,等到一定数之后变换到红黑树

java集合框架Map插图2

7.是否掌握HashMap的底层实现,put、get流程

说下hashmap的put和get的核心逻辑(JDK8以上版本)

put核心流程

转载自小滴课堂

java集合框架Map插图4

get核心流程

 final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //获取首节点,hash碰撞概览小,通常链表第一个节点就是值,没必要去循环遍历,处于效率
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //如果不止一个节点,就需要循环遍历,存在多个hash碰撞    
            if ((e = first.next) != null) {
                //判断是否是红黑树,如果是则调用树的查找
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //链表结构,则循环遍历获取节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

8.是否掌握并发包下的ConcurrentHashMap基础和原理

了解ConcurrentHashMap吗?为什么性能比hashtable高,说下原理

温馨提示

ConcurrentHashMap线程安全的Map, hashtable类基本上所有的方法都是采用synchronized进行线程安全控制
高并发情况下效率就降低

ConcurrentHashMap是采用了分段锁的思想提高性能,锁粒度更细化

jdk1.7和jdk1.8里面ConcurrentHashMap实现的区别有没了解

温馨提示

JDK8之前,ConcurrentHashMap使用锁分段技术,将数据分成一段段存储,每个数据段配置一把锁,即segment类,这个类继承ReentrantLock来保证线程安全
技术点:Segment+HashEntry

JKD8的版本取消Segment这个分段锁数据结构,底层也是使用Node数组+链表+红黑树,从而实现对每一段数据就行加锁,也减少了并发冲突的概率,CAS(读)+Synchronized(写)
技术点:Node+Cas+Synchronized

9.解读并发包里面ConcurrentHashMap核心Put源码

说下ConcurrentHashMap的put的核心逻辑(JDK8以上版本)

温馨提示

spread(key.hashCode()) 重哈希,减少碰撞概率
tabAt(i) 获取table中索引为i的Node元素
casTabAt(i) 利用CAS操作获取table中索引为i的Node元素


put的核心流程
1、key进行重哈希spread(key.hashCode())
2、对当前table进行无条件循环
3、如果没有初始化table,则用initTable进行初始化
4、如果没有hash冲突,则直接用cas插入新节点,成功后则直接判断是否需要扩容,然后结束
5、(fh = f.hash) == MOVED 如果是这个状态则是扩容操作,先进行扩容
6、存在hash冲突,利用synchronized (f) 加锁保证线程安全
7、如果是链表,则直接遍历插入,如果数量大于8,则需要转换成红黑树
8、如果是红黑树则按照红黑树规则插入
9、最后是检查是否需要扩容addCount()

推荐资料:

https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html

https://www.jianshu.com/p/5dbaa6707017

发表评论 取消回复
表情 图片 链接 代码

分享