腾讯-Java开发面经(一)
共 4582字,需浏览 10分钟
·
2021-07-17 19:42
点击蓝字关注我们,获取更多面经
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中, 都是以链表方式存储。
阻塞与非阻塞
阻塞就是卡在那儿什么也不做,双方之间也没有信息沟通。
非阻塞就是即使对方不能马上完成请求,双方之间也有信息的沟通。
同步与异步
同步就是一件事件只由一个过程处理完成,不论阻塞与非阻塞,最后完成这个事情的都是同一个过程
异步就是一件事由两个过程完成,前面一个过程通知,后面一个过程接受返回的结果。
异步和事件驱动(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
流程图:
当一个异步过程调用发出后,调用者不能立刻得到结果。实际处理这个调用的部件在完成后,通过状态、通知和回调来通知调用者的输入输出操作
更多面经
扫描二维码
获取更多面经
扶摇就业