meta|Java集合面试题看这篇就够了( 四 )

PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据。

PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。

PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。

PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

默认容量是 11 。当数组比较小（小于64 ）的时候每次扩容容量翻倍。当数组比较大（大于等于64 ）的时候每次扩容只增加一半的容量。

PriorityQueue 不是有序的，只有堆顶存储着最小的元素

11.说一下HashSet的实现原理？HashSet 的实现是依赖于 HashMap 的， HashSet 的值都是存储在HashMap中的。在 HashSet 的构造法中会初始化一个HashMap对象， HashSet 不允许值重复。因此， HashSet的值是作为HashMap的key存储在HashMap 中的，当存储的值已经存在时返回false 。
???面试官追问：HashSet有哪些特点？

无序性（存储元素无序）
唯一性（允许使用 null ）本质上， HashSet的值是作为HashMap的key存储在HashMap 中的，因此保证唯一性
HashSet没有提供 get() 方法，同HashMap一样，因为Set内部是无序的，所以只能通过迭代的方式获得

12.HashMap的实现原理/底层数据结构？

JDK1.7：数组 + 链表
JDK1.8：数组 + （链表 | 红黑树）

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。
JDK1.8的hash方法：
static final int hash(Object key) {

int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>:无符号右移，忽略符号位，空位都以0补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

JDK1.7的hash方法：
static int hash(int h) {

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

从源码可以看出JDK 1.8 的 hash 方法相比于 JDK 1.7 hash 方法更加简化，但是原理不变。 JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。
13.HashMap 的长度为什么是 2 的幂次方？

计算索引时效率更高： hash % tab.length ，而计算机中直接求余运算效率不如位移运算。所以源码中做了优化，使用 hash & (tab.length- 1) 来寻找桶位。而实际上 hash % length等于 hash & ( length - 1) 的前提是 length 必须为 2 的 n 次幂
扩容时重新计算索引效率更高：
- 上一页
- 1
- 2
- 3
- 4
- 5
- 6
- 下一页