【javase08~集合框架及其内部原理】

作者: 昵称该起什么好呢 | 来源:发表于2019-01-17 03:25 被阅读0次

【部分内容来自网络，侵删】

集合框架

在集合框架的类继承体系中，最顶层有两个接口：

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);  
        }
        
    }
}