2018年阿里一面面试题整理集合1
需积分: 0 111 浏览量
2022-08-08
20:56:37
上传
评论
收藏 78KB DOCX 举报
更多技术干货
关注公众号：【IT 技术思维】
## 数据结构
1. HashMap 的原理，内部数据结构？
- 底层使用哈希表（数组 + 链表），当链表过长会将链表转成 红黑树以实现 O(logn) 时间
复杂度内查找
2. 讲一下 HashMap 中 put 方法过程？
1. 对 Key 求 Hash 值，然后再计算 下标。
1. 如果没有碰撞，直接放入桶中，
1. 如果碰撞了，以链表的方式链接到后面，
1. 如果链表长度超过阀值（TREEIFY_THRESHOLD == 8），就把链表转成红黑树。
1. 如果节点已经存在就替换旧值
1. 如果桶满了（容量 * 加载因子），就需要 resize。
3. HashMap 中 hash 函数怎么是是实现的？ 还有哪些 hash 的实现方式？
1. 高 16bit 不变，低 16bit 和高 16bit 做了一个异或
1. （n - 1） & hash --> 得到下标
1. 还 有 哪 些 Hash 实 现 方 式 ： 可 以 参 考 之 前 的 博 客 [Effective Java 学 习 笔 记 --
hashCode()](../reading-notes/Effective-Java.md)
4. HashMap 怎样解决冲突，讲一下扩容过程，假如一个值在原数组中，现在移动了新数组，
位置肯定改变了，那是什么定位到在这个值新数组中的位置，
- 将新节点加到链表后，
- 容量扩充为原来的两倍，然后对每个节点重新计算哈希值。
- 这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为 <原下标+原容量>
的位置。
5. 抛开 HashMap，hash 冲突有那些解决办法？
- 开放定址，链地址法
1. 针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？
- 将链表转为红黑树， JDK1.8 已经实现了。
1. 数组和 ArrayList 的区别；
1. 数组可以包含基本类型和对象类型，ArrayList 只能包含对象类型
1. 数组大小固定，ArrayList 大小可以动态变化
1. ArrayList 提供了更多的特性（`addAll`、`removeAll`）。
1. Arraylist 如何实现排序
- `Collections.sort(List<T> list)`;
- `sort(List<T> list, Comparator<? super T> c)`;
剩余15页未读，继续阅读
评论0