腾讯-Java开发面经(一)

扶摇就业

共 4582字,需浏览 10分钟

 ·

2021-07-17 19:42

点击蓝字关注我们,获取更多面经








HashMap与HashTable





1、继承的父类不同

HashMap继承自AbstractMap类。但二者都实现了Map接口。

Hashtable继承自Dictionary类,Dictionary类是一个已经被废弃的类(见其源码中的注释)。父类都被废弃,自然而然也没人用它的子类Hashtable了。


2、HashMap线程不安全,HashTable线程安全

  javadoc中关于hashmap的一段描述如下:此实现不是同步的。如果多个线程同时访问一个哈希映射,**而其中至少一个线程从结构上修改了该映射**,则它必须保持外部同步。

  Hashtable 中的方法大多是Synchronize的,而HashMap中的方法在一般情况下是非Synchronize的。在多线程并发的环境下,可以直接使用Hashtable,不需要自己为它的方法实现同步,但使用HashMap时就必须要自己增加同步处理。HashTable实现线程安全的代价就是效率变低,因为会锁住整个HashTable,而ConcurrentHashMap做了相关优化,因为ConcurrentHashMap使用了分段锁,并不对整个数据进行锁定,效率比HashTable高很多。

  **HashMap底层是一个Entry数组,当发生hash冲突的时候,hashmap是采用链表的方式来解决的,在对应的数组位置存放链表的头结点。对链表而言,新加入的节点会从头结点加入。**

  HashMap的put方法:

void addEntry(int hash, K key, V value, int bucketIndex) { //新增Entry,将“key-value”插入指定位置,bucketIndex是位置索引。        Entry<K,V> e = table[bucketIndex];  保存“bucketIndex”位置的值到“e”中        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);         if (size++ >= threshold)       // 若HashMap的实际大小 不小于 “阈值”,则调整HashMap的大小2倍            resize(2 * table.length);    }


在hashmap的put方法调用addEntry()方法,假如A线程和B线程同时对同一个数组位置调用addEntry,两个线程会同时得到现在的头结点,然后A写入新的头结点之后,B也写入新的头结点,那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。

故解决方法就是使用 使用ConcurrentHashMap。

这里要说一下 就是HashMap的迭代器(Iterator)是fail-fast迭代器,故当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException异常,而Hashtable的enumerator迭代器不是fail-fast的。但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。


3.包含的contains方法不同

HashMap是没有contains方法的,而包括containsValue和containsKey方法;hashtable则保留了contains方法,效果同containsValue,还包括containsValue和containsKey方法。


4.是否允许null值

Hashmap是允许key和value为null值的,用containsValue和containsKey方法判断是否包含对应键值对;HashTable键值对都不能为空,否则包空指针异常。


5.计算hash值方式不同

为了得到元素的位置,首先需要根据元素的 KEY计算出一个hash值,然后再用这个hash值来计算得到最终的位置。


①:HashMap有个hash方法重新计算了key的hash值,因为hash冲突变高,所以通过一种方法重算hash值的方法:

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


注意这里计算hash值,先调用hashCode方法计算出来一个hash值,再将hash与右移16位后相异或,从而得到新的hash值。

**②:Hashtable通过计算key的hashCode()**来得到hash值就为最终hash值。


它们计算索引位置方法不同:

HashMap在求hash值对应的位置索引时,index = (n - 1) & hash。将哈希表的大小固定为了2的幂,因为是取模得到索引值,故这样取模时,不需要做除法,只需要做位运算。位运算比除法的效率要高很多。


HashTable在求hash值位置索引时计算index的方法:


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


&0x7FFFFFFF的目的是为了将负的hash值转化为正值,因为hash值有可能为负数,而&0x7FFFFFFF后,只有符号位改变,而后面的位都不变。


6.扩容方式不同(容量不够)

当容量不足时要进行resize方法,而resize的两个步骤:

①扩容;

②rehash:这里HashMap和HashTable都会会重新计算hash值而这里的计算方式就不同了(看5);

HashMap 哈希扩容必须要求为原容量的2倍,而且一定是2的幂次倍扩容结果,而且每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入;

而Hashtable扩容为原容量2倍加1;


7.解决hash冲突方式不同(地址冲突)

先看jdk8之前:


查找时间复杂度慢慢变高;

Java8,HashMap中,当出现冲突时可以:


1.如果冲突数量小于8,则是以链表方式解决冲突。

2.而当冲突大于等于8时,就会将冲突的Entry转换为**红黑树进行存储。**

3.而又当数量小于6时,则又转化为链表存储。


而在HashTable中, 都是以链表方式存储。






网络I/O模型




阻塞与非阻塞

  阻塞就是卡在那儿什么也不做,双方之间也没有信息沟通。

  非阻塞就是即使对方不能马上完成请求,双方之间也有信息的沟通。


同步与异步

  同步就是一件事件只由一个过程处理完成,不论阻塞与非阻塞,最后完成这个事情的都是同一个过程

  异步就是一件事由两个过程完成,前面一个过程通知,后面一个过程接受返回的结果。


异步和事件驱动(multi IO)

  异步是指数据准备好并且已经拷贝到用户空间,在通知用户来取数据

       事件驱动理解为准备好数据了但是没有拷贝到用户空间,这个时候去通知用户,用户再去取数据,经过拷贝过程取得数据。 



5种常见的网络I/O模型


blocking I/O  -- 阻塞类型的I/O

nonblocking I/O -- 非阻塞类型的I/O

 I/O Multiplexing -- 多路复用型I/O 

 Signal-Driven I/O -- 信号驱动型I/O

 Asynchronous I/O -- 异步I/O 

   



1. blocking I/O  -- 阻塞类型的I/O


  流程图如下:

    

  linux下socket默认是阻塞的,阻塞模式在准备数据和拷贝数据两个过程都是阻塞的,在这期间客户端一直卡着,双方也没有数据交流。


2.nonblocking I/O -- 非阻塞类型的I/O


  流程图:


     linux下使用fcntl方法将socket设置为非阻塞模式 


    flags = fcntl(sockfd, F_GETFL, 0);                        //获取文件的flags值。

              fcntl(sockfd, F_SETFL, flags | O_NONBLOCK);   //设置成非阻塞模式;


  非阻塞模式下,如果数据还没有准备好,服务端会返回error,客户端根据这个error判断后,再次发起recv,直到数据准备好,这个过程虽然客户端也在这里卡着了,但是这期间一直和服务有着信息交换。

 


3.I/O Multiplexing -- 多路复用型I/O


  流程图:


  多路复用型IO,有的也称为事件驱动型IO,常用select,poll,epoll来处理多个IO连接状态。当某个IO连接的数据准备好了,select返回,通知用户进行read操作,这种IO的好处是一次可以监听多个连接,坏处是要两次调用,两次返回,单个连接和非阻塞IO没有多大的性能提升。


    在多路复用模型中,对于每一个socket,一般都设置成为non-blocking,但是,如上图所示,整个用户的process其实是一直被block的。只不过process是被select这个函数block,而不是被socket IO给block。因此select()与非阻塞IO类似。


 

4.Signal-Driven I/O -- 信号驱动型I/O


  流程图:


  首先我们允许套接口进行信号驱动I/O,并安装一个信号处理函数,进程继续运行并不阻塞。当数据准备好时,进程会收到一个SIGIO信号,可以在信号处理函数中调用I/O操作函数处理数据。


 


5.Asynchronous I/O -- 异步I/O


   流程图:

    

  当一个异步过程调用发出后,调用者不能立刻得到结果。实际处理这个调用的部件在完成后,通过状态、通知和回调来通知调用者的输入输出操作








更多面经





京东-Java开发面经(一)

阿里-Java开发面经(一)


    扫描二维码

   获取更多面经

  扶摇就业  


浏览 14
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报