【部分内容来自网络，侵删】
集合框架
在集合框架的类继承体系中，最顶层有两个接口：
- Collection表示一组纯数据
- Map表示一组key-value对
Collection框架
cc.jpg
Map框架
ss.jpg
List
List是一个接口,用于保存一系列数据。List表示允许有重复元素的集合。
ArrayList
底层通过数组实现，查询快，插入慢
public class Demo2 {
public static void main(String[] args) {
List<String> array = new ArrayList<String>();
array.add("aaa");
array.add("bbb");
array.add("ccc");
array.add("ddd");
array.add("eee");
array.add("fff");
array.add("ggg");
array.add("hhh");
array.add("iii");
array.add("jjj");
array.add("kkk");
array.add("lll");
array.add("mmm");
System.out.println(array.get(10));
array.remove(12);
System.out.println(array);
Iterator<String> iter = array.iterator();
while(iter.hasNext()){
System.out.println(iter.next());
}
System.out.println(array.contains("aaaa"));
}
}
LinkedList
底层通过链表实现，插入快，查找慢
public class Demo2 {
public static void main(String[] args) {
List<String> array = new LinkedList<String>();
array.add("aaa");
array.add("bbb");
array.add("ccc");
array.add("ddd");
array.add("eee");
array.add("fff");
array.add("ggg");
array.add("hhh");
array.add("iii");
array.add("jjj");
array.add("kkk");
array.add("lll");
array.add("mmm");
System.out.println(array.get(10));
array.remove(12);
System.out.println(array);
Iterator<String> iter = array.iterator();
while(iter.hasNext()){
System.out.println(iter.next());
}
System.out.println(array.contains("aaaa"));
}
}
Set
Set是一个接口,用于保存一系列数据。Set表示不允许有重复元素的集合。
HashSet
无序set，底层通过hash表实现。Set通过hashCode和equals方法来保证对象是同一个。
hash表结构如下，
hh.gif
public class Demo2 {
public static void main(String[] args) {
Set<String> set = new HashSet<String>();
set.add("aaaa");
set.add("bbb");
set.add("aaaa");
set.add("cccc");
set.add("eeee");
set.add("fff");
for(String s: set){
System.out.println(s+ " " + s.hashCode());
}
Set<User> set2 = new HashSet<User>();
set2.add(new User("sjl", 12));
set2.add(new User("sjl", 14));
set2.add(new User("sjl", 12));
set2.add(new User("song", 12));
set2.add(new User("song", 15));
for(User s: set2){
System.out.println(s + " " + s.hashCode());
}
}
}
class User {
String name;
int age;
public User(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
User other = (User) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
@Override
public String toString() {
return "User [name=" + name + ", age=" + age + "]";
}
}
LinkedHashSet
相比较于HashSet，LinkedHashSet是有序的。数据将按照插入顺序进行存放。
LinkedHashMap源码分析
/*
*
*before和after这两个字段，是用来给迭代时使用的，相当于一个双向链表，
*before：指向前一个entry元素。after：指向后一个entry元素
*
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
ll.png
public class Demo2 {
public static void main(String[] args) {
Set<String> set = new LinkedHashSet<String>();
set.add("aaaa");
set.add("bbb");
set.add("aaaa");
set.add("cccc");
set.add("eeee");
set.add("fff");
for(String s: set){
System.out.println(s+ " " + s.hashCode());
}
}
}
TreeSet
TreeSet将数据按照自然顺序进行存放。底层使用树进行实现(红黑树，一种自平衡的二叉树)。
二叉树的遍历方法
-
前序遍历 按照中->左->右进行遍历
qq.jpg -
中序遍历 按照左->中->右进行遍历
zz.jpg -
后序遍历 按照左->右->中进行遍历
hh.jpg -
层次遍历(广度优先)
bb.jpg
前序遍历，中序遍历，后序遍历均可以使用递归的方式实现，这种方式代码逻辑最简单，此外还可以使用左路径压栈的方式进行遍历。
首先看下二叉查找树，满足：
- 空树是一个二叉搜索树
- 左子树所有节点的值均小于根节点的值
- 右子树所有节点的值均大于根节点的值
- 左右子树都是二叉搜索树
- 中序遍历序列为升序
如下就是一颗二叉搜索树：
12.jpg
二叉搜索树的查找原理：
1、从根结点开始查找，如果树为空，就返回NULL。
2、如果树不空，就让数据X和根结点的数据Data作比较。
3、如果X的值大于根结点的Data，就往右子树中进行搜索；如果X的值小于根结点的Data，就往左子树中进行搜索。
4、如果X的值等于Data，就表示查找完成，返回该结点。
二叉搜索树的插入原理与查找原理类似：
将要插入的结点x，与根节点进行比较，若小于则去到左子树进行比较，若大于则去到右子树进行比较，重复以上操作直到找到一个空位置用于放置该新节点
二叉搜索树的删除原理：
假如要删除某节点f的子节点p，
-
如果p是叶子节点，直接删除
-
如果p只有左子树或右子树，则直接用p.left或者p.right替换
-
p既有左子树left，又有右子树right，找到右子树的最小节点，用该节点替换p的值。再根据前面两种情况，删除右子树的最小节点即可
极端情况下的二叉搜索树会退化为链表，存在性能问题。
AVL树是一种自平衡的二叉树，满足如下特征：
- AVL树是一个二叉搜索树
- AVL的左右子树高度差的绝对值不超过1
- 空树，AVL的左右子树都是AVL树。
可以通过旋转操作来保持输的平衡，可以参考这篇文章
https://blog.csdn.net/qq_25806863/article/details/74755131
| 插入方式 | 描述 | 旋转方式 |
|---|---|---|
| LL | 在a的左子树根节点的左子树上插入节点而破坏平衡 | 右旋转 |
| RR | 在a的右子树根节点的右子树上插入节点而破坏平衡 | 左旋转 |
| LR | 在a的左子树根节点的右子树上插入节点而破坏平衡 | 先左旋后右旋 |
| RL | 在a的右子树根节点的左子树上插入节点而破坏平衡 | 先右旋后左旋 |
-
LL
ll.png
//原7的左孩子5变为父结点，7变为其右孩子，而原5的右子树变为7的左子树
private BinaryNodeInterface<T> rotateRight(BinaryNodeInterface<T> nodeN){
BinaryNodeInterface<T> nodeL = nodeN.getLeftChild();//获取7的左孩子也就是5
nodeN.setLeftChild(nodeL.getRightChild());//原节点5的右孩子设为7的左孩子
nodeL.setRightChild(nodeN);//将7设为节点5的右孩子
return nodeL;//返回节点5
}
-
RR
rr.png
//原10右孩子13变为父结点，10变为其左孩子，而原13的左子树将变为10的右子树
private BinaryNodeInterface<T> rotateLeft(BinaryNodeInterface<T> nodeN){
BinaryNodeInterface<T> nodeR = nodeN.getRightChild();//获取10的右孩子也就是13
nodeN.setRightChild(nodeR.getLeftChild());//将10的左孩子设为13的右孩子
nodeR.setLeftChild(nodeN);//将10设为13的左孩子
return nodeR;//返回节点13
}
-
LR
LR.png
//在5节点按照RR型向左旋转一次之后，二叉树在7节点仍然不能保持平衡，这时还需要再向右旋转一次。
private BinaryNodeInterface<T> rotateLeftRight(BinaryNodeInterface<T> nodeN){
BinaryNodeInterface<T> nodeL = nodeN.getLeftChild();//获取7的左节点5
nodeN.setLeftChild(rotateLeft(nodeL));//将5节点左旋并返回子树的新的根节点6，将6设为7的左节点
return rotateRight(nodeN);//将7节点进行右旋
}
-
RL
RL.png
//在13节点按照RR型向右旋转一次之后，二叉树在10节点仍然不能保持平衡，这时还需要再向左旋转一次
private BinaryNodeInterface<T> rotateRightLeft(BinaryNodeInterface<T> nodeN){
BinaryNodeInterface<T> nodeR = nodeN.getRightChild();//获取10的右节点13
nodeN.setRightChild(rotateRight(nodeR));//将13节点进行右旋，并返回子树的新的根节点11，将11设为10的右节点
return rotateLeft(nodeN);//将10节点进行左旋
}
红黑树是是一个自平衡的二叉搜索树，满足如下性质：
- 红黑树是一个平衡二叉树
- 节点是红色或黑色
- 根节点是黑色，NULL节点是黑的
- 每个叶节点是黑色的。
- 每个红色节点的两个子节点都是黑色
- 从根节点到每个叶子结点的所有路径都包含相同数目的黑色节点
红黑树不像AVL树一样，永远保持绝对平衡，而是一种相对平衡，查询效率略低于AVL树，但插入，删除要高于AVL树
理解红黑树的关键在于下面两个函数（TreeMap源码）：
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;//只能插入红色节点
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
以上就是TreeSet的底层实现，TreeSet默认按照数据的自然序进行排序，但也可以指定自定义的comparator或者让类实现Comparable接口
public class Demo2 {
public static void main(String[] args) {
Set<Integer> set = new TreeSet<Integer>();
set.add(142);
set.add(129);
set.add(23);
set.add(67);
set.add(17);
set.add(321);
set.add(66);
System.out.println(set);
}
}
指定自定义排序如下：
public class Demo2 {
public static void main(String[] args) {
Set<String> set = new TreeSet<String>(new MyComparator());
set.add("fortran");
set.add("Hello");
set.add("Spring");
set.add("DjangoWeb");
set.add("zip");
set.add("C++");
set.add("web server");
System.out.println(set);
}
}
class MyComparator implements Comparator<String>{
public int compare(String o1, String o2) {
if(o1.length() != o2.length()){
return o1.length() - o2.length();
} else {
return o1.compareTo(o2);
}
}
}
Iterator和ListIterator主要区别
- iterator()方法在set和list接口中都有定义，但是ListIterator（）仅存在于list接口中（或实现类中）；
- ListIterator有add()方法，可以向List中添加对象，而Iterator不能
- ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。
- ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。
- 都可实现删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改。
以上介绍的都是单路查找树，下面所要给的是多路查找树
1、2-3树
- 2节点包含一个元素和2个孩子(或者没有孩子)
- 3节点包含一大一小两个元素和三个孩子(或者没有孩子)，两个元素按照大小顺序排列好
-
2-3树的所有叶子结点都在同一层次
23.jpg
231.png
2、2-3-4树
- 2节点包含一个元素和2个孩子(或者没有孩子)
- 3节点包含一大一小两个元素和三个孩子(或者没有孩子)，两个元素按照大小顺序排列好
- 4节点包含小中大三个元素和四个孩子(或者没有孩子)
-
2-3-4树的所有叶子结点都在同一层次
234.png
3、B树
2-3树和2-3-4树都是B树的特例，B树是一种多路平衡查找树，如果B中节点最大的孩子数目为m，称为m阶树
- 树中每个结点最多有m棵子树，即最多m-1个关键字
- 若根结点不是终端节点，则至少有两棵子树
- 除根节点之外的所有非叶节点至少有[m/2]棵子树
-
所有非叶结点的结构如下
111.jpg -
所有的叶子结点出现在同一层次上
bb.png
B树的查找原理：
- 首先将关键字key和节点中的关键字比较，如果等于某个关键字则查找成功
-
如果和所有关键字都不相等，则看key处于哪个范围内，然后去对应的指针所指向的子树中查找
b1.jpg
B树的插入原理：
c1.jpg
c2.jpg
c3.jpg
c4.jpg
4、B+树
B+树是Ｂ树的变种，有着比Ｂ树更高的查询效率。与B树相比有如下的不同：
- 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据
都保存在叶子节点。 - 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小
自小而大顺序链接。 - 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
111111.jpg
关于B树和B+树的区别及在数据库中的应用可以查看这篇文章https://blog.csdn.net/zhuanzhe117/article/details/78039692
集合的三种遍历方法
class Test {
public static void main(String[] args) {
Set<String> set = new HashSet<String>();
set.add("Hello");
set.add("World");
set.add("Java");
//1. iterator遍历
Iterator<String> iter = set.iterator();
while(iter.hasNext()){
System.out.println(iter.next());
}
//2. for
List<String> list = new ArrayList<String>();
list.add("C++");
list.add("Python");
list.add("go");
System.out.println(list instanceof RandomAccess);
for(int i = 0; i < list.size(); i++){
System.out.println(list.get(i));
}
//3. for-each
System.out.println(set instanceof RandomAccess);
for(String s:set){
System.out.println(s);
}
}
}
Map
Map用户存放一系列无序k-v对的集合。
HashMap
底层采用hash表实现，原理见HashSet
LinkedHashMap
底层采用hash表+链表实现，原理见LinkedHashSet
TreeMap
底层采用红黑树实现，原理见TreeSet
class Test {
public static void main(String[] args) {
Map<Integer, String> map = new HashMap<Integer, String>();
map.put(1, "Hello");
map.put(2, "Java");
map.put(3, "Spring");
map.put(4, "JavaScript");
map.put(5, "Python");
}
}
map的两种遍历方法
class Test {
public static void main(String[] args) {
Map<Integer, String> map = new HashMap<Integer, String>();
map.put(1, "Hello");
map.put(2, "Java");
map.put(3, "Spring");
map.put(4, "JavaScript");
map.put(5, "Python");
//1. Entity
Set<Map.Entry<Integer, String>> entry = map.entrySet();
for(Map.Entry<Integer, String> e:entry){
System.out.println("key="+e.getKey() + ", value="+e.getValue());
}
//2. key
Set<Integer> keySet = map.keySet();
for(int k:keySet){
System.out.println("key=" + k + ", value=" + map.get(k));
}
}
}
可变参数
class Test {
public static void main(String[] args) {
testMutableArgs(1,2,3,4,5);
}
public static void testMutableArgs(int... nums){
for(int i = 0; i < nums.length; i++){
System.out.println(i);
}
}
}
