Java常用类库与技巧-集合

一 数据结构常见问题

• 数组和链表的区别;
• 链表的操作,如反转,链表环路检测,双向链表,循环链表相关操作;
• 队列,栈的应用;
• 二叉树的遍历方式及其递归和非递归的实现;
• 红黑树的旋转;

---

二 算法常见问题

1 内部排序 : 如递归排序 交换排序(冒泡 快排) 选择排序 插入排序;
2 外部排序 : 应掌握如何利用有限的内存配合海量的外部存储来处理超大的数据集;

---

三 数据结构和算法扩展问题

• 哪些排序是不稳定的,稳定意味着什么?
• 不同数据集,各种排序最好或最差的情况?
• 如何优化算法?

---

四 Java集合框架概览

---

五 List和Set

---

六 集合之Map

1. 概览

2. Hashmap HashTable ConccurentHashMap的区别

 1. HashMap:数组+链表 jdk8以后 数组+链表+红黑树
 2. HashTable: 早期Java类库提供的哈希表的实现;涉及到修改
HashTable的方法,使用synchronized修饰,创兴华的方式运行,性能较差;
 3. ConcurrentHashMap使用CAS + synchronized支持并发操作;
 4. HashMap的key value均可为null,而其他两个类不支持;

3. put 方法逻辑

1. 如果HashMap未被初始化过,则初始化;
2. 对key求Hash值,然后在计算下标;
3. 如果没有碰撞,直接放入桶中;
4. 如果碰撞了,以链表的方式链接到后边;
5. 如果链表长度超过阈值,就把链表转成红黑树;
6. 如果链表长度低于6, 就把红黑树转回链表;
7. 如果节点已经存在就替换旧值;
8. 如果桶满了(容量16*加载因子0.75),就需要resize(扩容2倍后重排);

4. 如何有效的减少碰撞

1. 扰动函数 : 促使元素位置分布均匀,减少碰撞几率;
2. 使用final对象,并采用合适的equals()和hashCode()方法;

5. HashMap的Hash方法原理

6. HashMap 扩容问题

1. 扩容会重新调整容量大小;
2. 多线程环境下 : 调整大小会存在条件竞争,容易造成死锁;
3. rehashing是一个比较耗时的过程;

7. 如何优化HashTable?

锁细粒度化,将整个对象锁拆成多个锁;

8. ConcurrentHashMap : put方法的逻辑

1. 判断Node[]数组是否初始化,没有则进行初始化操作;
2. 通过hash定位数组的索引坐标,是否有Node节点,如果没有则使用CAS进行添加(链表的头节点),添加失败则进入下次循环.
3. 检查到内部正在扩容,就帮助它一块扩容.
4. 如果f!=null,则使用synchronized锁住f元素;
    4.1 如果是Node则执行链表的添加操作;
    4.2 如果是TreeNode则执行树添加操作;
5. 判断链表长度已经达到临界值8,当节点超过这个值就需要把链表转换为树结构;